Tim N. van der Leeuw wrote: > 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?
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)) ) -- http://mail.python.org/mailman/listinfo/python-list