New tail recursion decorator
Duncan Booth
duncan.booth at invalid.invalid
Fri May 12 16:02:53 EDT 2006
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)?
More information about the Python-list
mailing list