How can I rewrite this Python code using iteration?

Question

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__()

That is certainly a mess. Some documentation about what the purpose of the function is would be helpful. — John Lyon, Feb 25 '13 at 04:33
Depending on exactly what you are doing, it *might not* be possible to write this iteratively at all. Tail recursion is always translatable to iteration, but you recurse several times throughout the function - and the links between these are non-obvious since you rely on the side effects of a mutable default argument (this also probably makes your code buggy - if you duplicate the last line, it will give a different answer). Writing it iteratively is likely to require a rethink of your entire algorithm, which can't be done without some understanding of what it achieves. — lvc, Feb 25 '13 at 04:43
@lvc, you can still write it iteratively, you just need to explicitly store all the state that you usually leave on the stack. It's not very convenient though. — John La Rooy, Feb 25 '13 at 04:56

score 2 · Accepted Answer · edited May 23 '17 at 10:24

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))

Along with fixing the list as a default, OP would need to pass `r` in explicitly to the recursive calls, as well as reassign the result of them back to `r`: `r = fun(x1,y1,x3,y3, n-1, r)`. Or, since `r` doesn't figure into any of the calculations, `r.extend(fun(x1,y1,x3,y3,n-1)` which potentially removes the need for `r` to be an argument in the first place. — lvc, Feb 25 '13 at 04:52

How can I rewrite this Python code using iteration?

1 Answers1