Guest User

tail recursion elimination for python by mokrates

a guest
Feb 18th, 2012
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.25 KB | None | 0 0
  1. # tailrec
  2. # tail-recursion-support by mokrates
  3. # use like this:
  4. #
  5. # @tailrecursive
  6. # def tailrecursive_function(foo, bar): ...
  7. #
  8. # the tail-recursive call
  9. # return tailrecursive_function(foo, bar)
  10. # translates to
  11. # return tailresult(tailrecursive_function, foo, bar)
  12. #
  13. # functions given to tailresult MUST be decorated @tailrecursive
  14.  
  15. class tailresult:
  16.         def __init__(self, f, *args, **kwargs):
  17.                 self.f = f
  18.                 self.args = args
  19.                 self.kwargs = kwargs
  20.  
  21.         def __repr__(self):
  22.                 return "<tailresult(%s,%s,%s)>" % (repr(self.f), repr(self.args), repr(self.kwargs))
  23.  
  24. def tailrecursive(f):
  25.         def taildecorator(*args, **kwargs):
  26.                 res = f(*args, **kwargs)
  27.                 while isinstance(res, tailresult):
  28.                         res = res.f.f(*res.args, **res.kwargs)
  29.  
  30.                 return res
  31.  
  32.         taildecorator.f = f
  33.         return taildecorator
  34.  
  35. if __name__ == '__main__':
  36.         def fak(x):
  37.                 if (x==1): return 1
  38.                 else: return fak(x-1)*x
  39.  
  40.         @tailrecursive
  41.         def tr_fak(x,y):
  42.                 if y==0: return x
  43.                 else: return tailresult(tr_fak, x*y, y-1)
  44.  
  45.         print tr_fak(1,1000)
Advertisement
Add Comment
Please, Sign In to add comment