tail-rec decorator, well still blows the stack...
ssecorp
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?
ssecorp
because this doesn't blow the stack:
#!/usr/bin/env python2.4
# This program shows off a python decorator(
# which implements tail call optimization. It
# does this by throwing an exception if it is
# it's own grandparent, and catching such
# exceptions to recall the stack.
import sys
class TailRecurseException:
def __init__(self, args, kwargs):
self.args = args
self.kwargs = kwargs
def tail_call_optimized(g):
"""
This function decorates a function with tail call
optimization. It does this by throwing an exception
if it is it's own grandparent, and catching such
exceptions to fake the tail call optimization.
This function fails if the decorated
function recurses in a non-tail context.
"""
def func(*args, **kwargs):
f = sys._getframe()
if f.f_back and f.f_back.f_back \
and f.f_back.f_back.f_code == f.f_code:
raise TailRecurseException(args, kwargs)
else:
while 1:
try:
return g(*args, **kwargs)
except TailRecurseException, e:
args = e.args
kwargs = e.kwargs
func.__doc__ = g.__doc__
return func
@tail_call_optimized
def factorial(n, acc=1):
"calculate a factorial"
if n == 0:
return acc
return factorial(n-1, n*acc)
print factorial(10000)
# prints a big, big number,
# but doesn't hit the recursion limit.
@tail_call_optimized
def fib(i, current = 0, next = 1):
if i == 0:
return current
else:
return fib(i - 1, next, current + next)
print fib(10000)
# also prints a big number,
# but doesn't hit the recursion limit.
David Wahler
Python does not perform tail-call elimination, and there are currently
no plans to make it do so. See
http://mail.python.org/pipermail/python-dev/2004-July/046171.html and
the ensuing discussion for an explanation.
Terry Reedy
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
ssecorp
def fib(n):
a, b = 1, 0
while n:
a, b, n = b, a+b, n-1
return b
I know the example is not the way to write pythonic code, I was just
learning about decorators and then I saw this example and tried it
out.
but thanks now i understand why it didn't work.