New tail recursion decorator
Tim N. van der Leeuw
tim.leeuwvander at nl.unisys.com
Fri May 12 15:49:59 CEST 2006
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
More information about the Python-list
mailing list