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