recursion vs iteration (was Re: reduce()--what is it good for?)

[Alex Martelli]

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