K
D
Diez B. Roggisch
Kay said:
Neat.
Diez
K
Kay Schluehr
Diez said:
Hi Diez,
for all those who already copied and pasted the original solution and
played with it I apologize for radical changes in the latest version (
the recipe is on version 1.5 now ! ). The latest implementation is
again a lot faster than the previous one. It does not only get rid of
exceptions but also of stack-frame inspection.
Regards,
Kay
D
Duncan Booth
I'm not convinced by this. You have to recognise that the function is usingKay said:
tail recursion, and then you have to modify the code to know that it is
using tail recursion. This is not always trivial. For example, the given
example is:
@tail_recursion
def factorial(n, acc=1):
"calculate a factorial"
if n == 0:
return acc
res = factorial(n-1, n*acc)
return res
but a more common way to write the function would be:
@tail_recursion
def factorial(n):
"calculate a factorial"
if n == 0:
return 1
return n * factorial(n-1)
which won't work because it isn't actually tail recursion, but it looks
sufficiently close to tail recursion that it would probably mislead a lot
of people into expecting it will work. If you are going to have to rewrite
functions in a stilted manner, and they use simple tail recursion, then why
not just factor out the tail recursion in the first place.
My other problem with this is that the decorator is very fragile although
this may be fixable. e.g. (using the published example) an exception
thrown inside the function makes future calls return garbage:
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'('continue', (3,), {})
M
Michele Simionato
Kay said:
This is spectacular!!
I would rewrite it as follows:
CONTINUE = object() # sentinel value returned by iterfunc
def tail_recursive(func):
"""
tail_recursive decorator based on Kay Schluehr's recipe
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496691
"""
var = dict(in_loop=False, cont=True, argkw='will be set later')
# the dictionary is needed since Python closures are read-only
def iterfunc(*args, **kwd):
var["cont"] = not var["cont"]
if not var["in_loop"]: # start looping
var["in_loop"] = True
while True:
res = func(*args,**kwd)
if res is CONTINUE:
args, kwd = var["argkw"]
else:
var["in_loop"] = False
return res
else:
if var["cont"]:
var["argkw"] = args, kwd
return CONTINUE
else:
return func(*args,**kwd)
return iterfunc
Using my decorator module 'tail_recursive' can even be turned in a
signature-preserving
decorator. I think I will add this great example to the documentation
of the next version
of decorator.py!
Michele Simionato
M
Michele Simionato
F
Felipe Almeida Lessa
Em Ter, 2006-05-09 Ã s 23:30 -0700, Kay Schluehr escreveu:
Is it thread safe?
Is it thread safe?
C
Carl Banks
Michele said:
CONTINUE could be put inside tail_recursive, couldn't it? And to
squeeze a little more speed out of it, var could be a list (saves a
hash lookup).
Cool decorator.
Carl Banks
T
Tim N. van der Leeuw
[...]
Hi Duncan,
I don't know why it wouldn't work this way, or why it isn't
tail-recursion?
I tried the tail_recursion decorator from the cookbook-recipe with both
definitions of factorial, and I tried both definitions of the factorial
function with and without tail_recursion decorator.
In all four cases I get the same results, so it does work with both
definitions of factorial(), even if (according to you) the second
definition is not proper tail-recursion.
Using the tail-recursion decorator (the version that does not inspect
the stackframes) I get a small performance-increase over using the
factorial-function undecorated.
However, calculating factorial(1000) with the factorial-function as
defined in the cookbook-recipe is much much faster than calculating the
same factorial(1000) with the factorial-function you gave!
I cannot yet explain why the first function has so much better
performance than the second function - about a factor 10 difference,
in both python2.4.3 and python 2.5a2
Cheers,
--Tim
[...]
Hi Duncan,
I don't know why it wouldn't work this way, or why it isn't
tail-recursion?
I tried the tail_recursion decorator from the cookbook-recipe with both
definitions of factorial, and I tried both definitions of the factorial
function with and without tail_recursion decorator.
In all four cases I get the same results, so it does work with both
definitions of factorial(), even if (according to you) the second
definition is not proper tail-recursion.
Using the tail-recursion decorator (the version that does not inspect
the stackframes) I get a small performance-increase over using the
factorial-function undecorated.
However, calculating factorial(1000) with the factorial-function as
defined in the cookbook-recipe is much much faster than calculating the
same factorial(1000) with the factorial-function you gave!
I cannot yet explain why the first function has so much better
performance than the second function - about a factor 10 difference,
in both python2.4.3 and python 2.5a2
Cheers,
--Tim
M
Michele Simionato
Tim said:
For me factorial(1001) with the second definition does not work, I get
the recursion limit (which is what I expect). I suppose the recursion
limit is higher on your system, but definitely you should reach it at
some point with the non tail-recursive version of factorial.
It is because the decorator is doing is job (converting a long
recursion in a loop)
only with the first function, which is properly tail recursive. Just as
Duncan said.
Michele Simionato
T
Tim N. van der Leeuw
Hi Michele,
I'm sorry, but you misunderstood me.
There are two definitions of the factorial() function, one given by the
OP and the other given by Duncan.
I tested both factorial() definitions with, and without the
tail_recursion decorator (the version of the OP). So I had 4
factorial-functions defined in my test-file:
@tail_recursion
def factorial(n, acc=1):
# do the stuff
pass
def factorial_r(n, acc=1):
# do the stuff
pass
@tail_recursion
def factorial2(n):
# do the stuff
pass
def factorial2_r(n):
# do the stuff
pass
All four functions give the same output for the tests I did (n=120, and
n=1000).
Using timeit, both factorial(1000) and factorial2(1000) are somewhat
faster than factorial_r(1000) respectively factorial2_r(1000).
However, factorial(1000) and factorial_r(1000) are both 10x faster than
factorial2(1000) and factorial2_r(1000).
It's the latter performance difference which I do not understand.
The other thing I do not understand, due to my limited understanding of
what is tail-recursion: factorial2 (Duncan's definition) is not proper
tail-recursion. Why not? How does it differ from 'real' tail recursion?
And if it's not proper tail-recursion and therefore should not work,
then how comes that the tests I do show it to work? And I seemed to
consistently get a slightly better performance from factorial2(1000)
than from factorial2_r(1000).
NB: Regarding the recursion limits, I don't know what would be the
stacklimit on my system (Python 2.4.3 on WinXP SP2). I already
calculated the factorial of 500000 using the recursive (non-decorated)
function...
Cheers,
--Tim
I'm sorry, but you misunderstood me.
There are two definitions of the factorial() function, one given by the
OP and the other given by Duncan.
I tested both factorial() definitions with, and without the
tail_recursion decorator (the version of the OP). So I had 4
factorial-functions defined in my test-file:
@tail_recursion
def factorial(n, acc=1):
# do the stuff
pass
def factorial_r(n, acc=1):
# do the stuff
pass
@tail_recursion
def factorial2(n):
# do the stuff
pass
def factorial2_r(n):
# do the stuff
pass
All four functions give the same output for the tests I did (n=120, and
n=1000).
Using timeit, both factorial(1000) and factorial2(1000) are somewhat
faster than factorial_r(1000) respectively factorial2_r(1000).
However, factorial(1000) and factorial_r(1000) are both 10x faster than
factorial2(1000) and factorial2_r(1000).
It's the latter performance difference which I do not understand.
The other thing I do not understand, due to my limited understanding of
what is tail-recursion: factorial2 (Duncan's definition) is not proper
tail-recursion. Why not? How does it differ from 'real' tail recursion?
And if it's not proper tail-recursion and therefore should not work,
then how comes that the tests I do show it to work? And I seemed to
consistently get a slightly better performance from factorial2(1000)
than from factorial2_r(1000).
NB: Regarding the recursion limits, I don't know what would be the
stacklimit on my system (Python 2.4.3 on WinXP SP2). I already
calculated the factorial of 500000 using the recursive (non-decorated)
function...
Cheers,
--Tim
D
Duncan Booth
Tim said:
Tail recursion is when a function calls itself and then immediately returns
the result of that call as its own result. So long as nothing except
returning the result needs to be done it is possibly to avoid the recursive
call altogether.
This function is tail recursive:
@tail_recursion
def factorial(n, acc=1):
"calculate a factorial"
if n == 0:
return acc
res = factorial(n-1, n*acc)
return res
but this one isn't:
@tail_recursion
def factorial2(n):
"calculate a factorial"
if n == 0:
return 1
return n * factorial2(n-1)
because when the inner call to factorial2() returns the function still has
to do some work (the multiplication).
I don't understand your comments about speed differences. If you try to run
factorial2() as defined above then it simply throws an exception: there
are no results to compare. My guess is that when you wrote:
@tail_recursion
def factorial2(n):
# do the stuff
pass
your 'do the stuff' actually had an erroneous call to 'factorial'. If you
are going to rename the function you have to rename the recursive calls as
well. (At least, that's what I forgot to do when I first tried it and
couldn't understand why it gave me an answer instead of crashing.)
The decorator also fails for functions which are tail-recursive but which
contain other non-tail recursive calls within themselves. For example I
would be pretty sure you couldn't write a working implementation of
Ackermann's function using the decorator:
def Ack(M, N):
if (not M):
return( N + 1 )
if (not N):
return( Ack(M-1, 1) )
return( Ack(M-1, Ack(M, N-1)) )
T
Tim N. van der Leeuw
[...]Duncan said:
Duncan,
You're totally right. Somehow, I had managed to completely overlook
this. Oops!
My apologies!
--Tim
K
Kay Schluehr
Duncan said:
Definitely. The translation into a proper tail-recursive form is
non-trivial but nevertheless possible as demonstrated by the following
Ackermann implementation:
@tail_recursion
def ack(m,n,s=[0]): # use a stack-variable s as "accumulator"
if m==0:
if s[0] == 1:
return ack(s[1]-1,n+1,s[2])
elif s[0] == 0:
return n+1
elif n==0:
return ack(m-1,1,s)
else:
return ack(m,n-1,[1,m,s])
Regards,
Kay
A
Alexander Schmolck
Duncan Booth said:
I think the definition is broader than that so that these two functions would
also be tail-recursive (i.e. the tail call doesn't have to be a self-tail
call; I might be mistaken, don't have a good reference at hand; however
"properly tail recursive" certainly refers to being able to do the below
without exhausting the stack even for large n, not just transforming self-tail
calls to a loop, which is sort of limited usefulness anyway):
def even(n):
return n == 0 or not odd(n-1)
def odd(n):
return n == 1 or not even(n-1)
'as
T
Terry Reedy
Which means that the value returned by the base case is returned unchanged
to the original caller through the stack of returns. Which means that the
return stack can potentially be compressed to just one return.
No, these are not even mutually tail-recursive, assuming that that would
make sense. You are calling the not operator function on the results of
the recursive calls before returning them. The following *is*
tail-recursive:
def even(n):
assert n >= 0
if n >=2: return even(n-2)
return bool(n)
The recursive call is effectively a goto back to the top of the function,
with n reduced by 2. This looping continues until n < 2. So in Python, we
would usually write
def even(n):
assert n >= 0
while n >= 2: n -=2
return bool(n)
Terry Jan Reedy
to the original caller through the stack of returns. Which means that the
return stack can potentially be compressed to just one return.
No, these are not even mutually tail-recursive, assuming that that would
make sense. You are calling the not operator function on the results of
the recursive calls before returning them. The following *is*
tail-recursive:
def even(n):
assert n >= 0
if n >=2: return even(n-2)
return bool(n)
The recursive call is effectively a goto back to the top of the function,
with n reduced by 2. This looping continues until n < 2. So in Python, we
would usually write
def even(n):
assert n >= 0
while n >= 2: n -=2
return bool(n)
Terry Jan Reedy
D
Duncan Booth
Very clever, although simulating a stack isn't exactly eliminatingKay said:
recursion.
Any idea how long I have to wait to find ack(4,1)?
C
Casey Hawthorne
Your examples are not tail recursive because an extra step is needed
before returning from the function call and that step cannot be thrown
away!
before returning from the function call and that step cannot be thrown
away!
C
Casey Hawthorne
Tail Call Optimization and Recursion are separate concepts!
M
Michele Simionato
Duncan said:
This version should be more robust against exceptions:
class tail_recursive(object):
"""
tail_recursive decorator based on Kay Schluehr's recipe
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496691
"""
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