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

[Anton Vredegoor]

Alex Martelli <aleaxit at yahoo.com> wrote:

>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.

Defined as above the number of recursions is equal to the return
value, because there is only one increment per call.

Have a look at the paper about the ackerman function at:

http://www.dur.ac.uk/martin.ward/martin/papers/

(the 1993 paper, halfway down the list, BTW, there's also something
there about automatically translating assembler to C-code, maybe it
would also be possible to automatically translate C-code to Python?
Start yet another subthread :-)

Another thing is that long integers cannot be used to represent the
result values because the numbers are just too big. 

It seems possible to make an iterative version that computes the
values more efficiently, but it suffers from the same number
representation problem. 

Maybe Bengt can write a class for representing very long integers as
formulas. For example an old post by François Pinard suggests that:

ackerman(4, 4) == 2 ** (2 ** (2 ** (2 ** (2 ** (2 ** 2))))) - 3

Anton