recursion vs iteration (was Re: reduce()--what is it good for?)
Alex Martelli
aleaxit at yahoo.com
Sun Nov 9 01:36:06 CET 2003
Anton Vredegoor wrote:
...
> find a better example of recursive functions that memoize and which
> cannot be made iterative.
>
> This would generate an important precedent for me because I have
> believed for a long time that every recursive function can be made
> iterative, and gain efficiency as a side effect.
Well, without stopping to ponder the issue deeply, I'd start with:
def Ack(M, N, _memo={}):
try: return _memo[M,N]
except KeyError: pass
if not M:
result = N + 1
elif not N:
result = Ack(M-1, 1)
else:
result = Ack(M-1, Ack(M, N-1))
_memo[M,N] = result
return result
M>=0 and N>=0 (and M and N both integers) are preconditions of the Ack(M, N)
call.
There is a substantial body of work on this function in computer science
literature, including work on a technique called "incrementalization" which,
I believe, includes partial but not total iterativization (but I am not
familiar with the details). I would be curious to examine a totally
iterativized and memoized version, and comparing its complexity, and
performance on a few typical (M,N) pairs, to both this almost-purest
recursive version, and an incrementalized one.
Alex
More information about the Python-list
mailing list