|
|
 |
|
Title: New Tail Recursion Decorator
Submitter: kay schluehr
(other recipes)
Last Updated: 2007/08/21
Version no: 1.7
Category:
Algorithms
|
|
 4 vote(s)
|
|
|
|
Description:
A new tail recursion decorator that eliminates tail calls for recursive functions is introduced.
Source: Text Source
import sys
def tail_recursion_with_stack_inspection(g):
'''
Version of tail_recursion decorator using stack-frame inspection.
'''
loc_vars ={"in_loop":False,"cnt":0}
def result(*args, **kwd):
if not loc_vars["in_loop"]:
loc_vars["in_loop"] = True
while 1:
tc = g(*args,**kwd)
try:
qual, args, kwd = tc
if qual == 'continue':
continue
except TypeError:
loc_vars["in_loop"] = False
return tc
else:
f = sys._getframe()
if f.f_back and f.f_back.f_back and \
f.f_back.f_back.f_code == f.f_code:
return ('continue',args, kwd)
return g(*args,**kwd)
return result
def tail_recursion(g):
'''
Version of tail_recursion decorator using no stack-frame inspection.
'''
loc_vars ={"in_loop":False,"cnt":0}
def result(*args, **kwd):
loc_vars["cnt"]+=1
if not loc_vars["in_loop"]:
loc_vars["in_loop"] = True
while 1:
tc = g(*args,**kwd)
try:
qual, args, kwd = tc
if qual == 'continue':
continue
except (TypeError, ValueError):
loc_vars["in_loop"] = False
return tc
else:
if loc_vars["cnt"]%2==0:
return ('continue',args, kwd)
else:
return g(*args,**kwd)
return result
@tail_recursion
def factorial(n, acc=1):
"calculate a factorial"
if n == 0:
return acc
res = factorial(n-1, n*acc)
return res
Discussion:
It is about 2 months ago that Crutcher Dunnavant published a cute tail recursion decorator that eliminates tail calls for recursive functions in Python i.e. turning recursion into iteration [1]. The new one gets rid of catching exceptions and is faster. The source code shows two versions. The first one uses stack frame inspections just like Crutchers decorator, the second one abandones those and runs twice as fast.
[1] http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/474088
Warning: the optimization comes at its price. The dumbed down lookup procedure causes brittleness in certain cases and different @tail_recursion decorators can interfere as in the following counter example:
@tail_recursion
def even(n):
if n == 0:
return True
else:
return odd(n-1)
@tail_recursion
def odd(n):
if n == 0:
return False
else:
return even(n-1)
Commenting out one of these decorators let it work again. Crutchers decorator works in both cases and shows the expected bounded sized stack behaviour.
Note also that these decorators are not optimizing and for small argument values they are actually far slower.
|
|
Add comment
|
|
Number of comments: 2
This decorator is a bit fragile, Duncan Booth, 2006/05/10
You need to add some error handling to the code. If a call to the decorated function ever raises an exception then all subsequent calls to the function will return garbage. e.g.
>>> factorial(3)
6
>>> factorial('a')
Traceback (most recent call last):
File "<pyshell#5>", line 1, in -toplevel-
factorial('a')
File "<pyshell#1>", line 12, in result
tc = g(*args,**kwd)
File "<pyshell#3>", line 6, in factorial
res = factorial(n-1, n*acc)
TypeError: unsupported operand type(s) for -: 'str' and 'int'
>>> factorial(3)
('continue', (3,), {})
Add comment
This version is more robust against exceptions, Michele Simionato, 2006/05/15
class tail_recursive(object):
CONTINUE = object() # sentinel
def __init__(self, func):
self.func = func
self.firstcall = True
def __call__(self, *args, **kwd):
try:
if self.firstcall: # start looping
self.firstcall = False
while True:
result = self.func(*args, **kwd)
if result is self.CONTINUE: # update arguments
args, kwd = self.argskwd
else: # last call
break
else: # return the arguments of the tail call
self.argskwd = args, kwd
return self.CONTINUE
except: # reset and re-raise
self.firstcall = True
raise
else: # reset and exit
self.firstcall = True
return result
Add comment
|
|
|
|
|
|
|
