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
