New tail recursion decorator

[Duncan Booth]

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)) )