New tail recursion decorator

[Duncan Booth]

Kay Schluehr wrote:

> 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])
> 
Very clever, although simulating a stack isn't exactly eliminating 
recursion.

Any idea how long I have to wait to find ack(4,1)?