tail-rec decorator, well still blows the stack...
Terry Reedy
tjreedy at udel.edu
Tue Jul 22 01:35:11 EDT 2008
ssecorp wrote:
> http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496691
>
> so I try it and when I run:
> @Decorators.tail_recursion
> def fibtr(n):
> def fibt(a, b, n):
> if n <= 1:
> return b
> else:
> return fibt(b, a + b, n - 1)
> if n == 0:
> return 0
> else:
> return fibt(0, 1, n);
>
> it still blows the stack. so what is the point? is it impossible to
> get "real" tail-recursion in Python?
As you have used it, the decorator wraps the *outer* non-recursive
function which is just called once anyway. Useless. Try wrapping fibt
instead.
That said, this recipe significantly increases the running time by
multiplying the number of function calls by about three. I do not
regard it as removing the recursion, but, rather, as making it indirect
(via two other calls) so as to remove the unneeded stack frames (and the
space problem) in between recursive calls. Much simpler is the trivial
rewrite with while to do 'in frame recursion', or iteration. This also
removes the need for outer and inner function.
rearrange fibt as
def fibt(a,b,n):
if n > 1:
return fibt(b, a+b, n-1)
else:
return b
and rewrite as
def fibi(a,b,n):
while n > 1:
a,b,n = b,a+b,n-1
return b
by directly binding the new arguments to the parameters.
Move the initialization inside the function (and delete the outer
wrapper) to get
def fib(n):
if n==0:
return 0
else:
a,b = 0,1
while n > 1:
a,b,n = b,a+b,n-1
return b
and even turn the induction back a step and simplify to
def fib(n):
a,b = 1,0
while n:
a,b,n = b,a+b,n-1
return b
Why do some people fight writing efficient beautiful code like this that
works with Python's design to instead write less efficient and uglier
code that works against Python's design?
If you do not want function calls (and runtime name resolution), do not
write them!
Terry Jan Reedy
More information about the Python-list
mailing list