New tail recursion decorator
Kay Schluehr
kay.schluehr at gmx.net
Fri May 12 18:42:49 CEST 2006
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
More information about the Python-list
mailing list