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 -- http://mail.python.org/mailman/listinfo/python-list