CODEWITHSUNDEEP
pythonrecursioniteration
matrix42
matrix42

Reputation: 289

How can I rewrite this Python code using iteration?

The code shown below works. I think using recursion is not effective in Python. How can I convert it to for loop version?

def fun(x1, y1, x2, y2, n, r=[]):
    if n<1 :
        return
    r.append( [[x1,y1],[x2,y2]])
    x3=(x1+x2)/2.0
    y3=(y1+y2)/2.0
    fun(x1,y1,x3,y3, n-1)
    fun(x3,y3,x2,y2,n-1)

    x4=(x2+y2-y3-x3)*0.7+x3;
    y4 = (y2 - x2 + x3 - y3)*0.7 + y3;
    fun(x3, y3, x4, y4, n - 1);

    x3 = (3* x1 + x2)/4;
    y3 = (3* y1 + y2)/4;
    x2 = (3*x2 + x1)/4;
    y2 = (3*y2 + y1)/4;
    x4 = (x2*1.7 - y2 + 2*x3 - x3*1.7 + y3)/2;
    y4 = (x2 + y2*1.7 - x3 + 2*y3 - 1.7*y3)/2;
    fun(x3, y3, x4, y4, n - 1);
    return r

print fun(200, 400, 200, 0, 9).__len__()

Upvotes: 0

Views: 142

Answers (1)

Ric
Ric

Reputation: 8805

You may want to consider something like memoize to speed up recursive functions by using more memory. Essentially it stores the results of any call in a cache.

Add the following code

import collections
import functools

class memoized(object):
   '''Decorator. Caches a function's return value each time it is called.
   If called later with the same arguments, the cached value is returned
   (not reevaluated).
   '''
   def __init__(self, func):
      self.func = func
      self.cache = {}
   def __call__(self, *args):
      if not isinstance(args, collections.Hashable):
         # uncacheable. a list, for instance.
         # better to not cache than blow up.
         return self.func(*args)
      if args in self.cache:
         return self.cache[args]
      else:
         value = self.func(*args)
         self.cache[args] = value
         return value
   def __repr__(self):
      '''Return the function's docstring.'''
      return self.func.__doc__
   def __get__(self, obj, objtype):
      '''Support instance methods.'''
      return functools.partial(self.__call__, obj)

Then decorate your function like this

@memoized
def fun(x1, y1, x2, y2, n, r=[]):
    ...

Also be careful with your optional parameter. The list created by r = [] will actually be shared across all calls of f with an r. It is better to do something like this so a new list is created every time.

def fun(x1, y1, x2, y2, n, r=None):
    r = [] if r is None else r

A more Pythonic way of getting the length is like this

print len(fun(200, 400, 200, 0, 9))

Upvotes: 2

Related Questions