New tail recursion decorator

[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