3 views

Skip to first unread message

Jul 21, 2008, 11:01:35 PM7/21/08

to

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?

Jul 21, 2008, 11:06:44 PM7/21/08

to

I my function not proper tail-recursion?

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.

Jul 22, 2008, 12:24:01 AM7/22/08

to ssecorp, pytho...@python.org

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.

Jul 22, 2008, 1:35:11 AM7/22/08

to pytho...@python.org

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

Jul 22, 2008, 2:15:32 AM7/22/08

to

thanks i already have perfect iterative versions of fibonacci.

def fib(n):

a, b = 1, 0

while n:

a, b, n = b, a+b, n-1

return b

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.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu