New tail recursion decorator

[Kay Schluehr]

Duncan Booth wrote:

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

Definitely. The translation into a proper tail-recursive form is
non-trivial but nevertheless possible as demonstrated by the following
Ackermann implementation:

@tail_recursion
def ack(m,n,s=[0]):   # use a stack-variable s as "accumulator"
    if m==0:
    	if s[0] == 1:
        	return ack(s[1]-1,n+1,s[2])
        elif s[0] == 0:
        	return n+1
    elif n==0:
    	return ack(m-1,1,s)
    else:
    	return ack(m,n-1,[1,m,s])

Regards,
Kay