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

[Bengt Richter]

On Sun, 09 Nov 2003 21:07:31 +0100, anton at vredegoor.doge.nl (Anton Vredegoor) wrote:

>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
Thanks Anton ;-)
>formulas. For example an old post by François Pinard suggests that:
>
>ackerman(4, 4) == 2 ** (2 ** (2 ** (2 ** (2 ** (2 ** 2))))) - 3
>
If they are too big to represent, they are probably also too big to arrive at
in practical time counting by one ;-)

It is interesting to trace the composition of the args to successive calls and
label which recursive calls they were due to, though I don't know
what to make of it ;-)  A quick hack (I may have goofed) shows:

>>> sAck(2,2)
2 2 root: M N
2 1 M&N argev: M (N-1)
2 0 M&N argev: M ((N-1)-1)
1 1 not N: (M-1) 1
1 0 M&N argev: (M-1) (1-1)
0 1 not N: ((M-1)-1) 1
0 2 M&N: ((M-1)-1) (1+1)
1 3 M&N: (M-1) ((1+1)+1)
1 2 M&N argev: (M-1) (((1+1)+1)-1)
1 1 M&N argev: (M-1) ((((1+1)+1)-1)-1)
1 0 M&N argev: (M-1) (((((1+1)+1)-1)-1)-1)
0 1 not N: ((M-1)-1) 1
0 2 M&N: ((M-1)-1) (1+1)
0 3 M&N: ((M-1)-1) ((1+1)+1)
0 4 M&N: ((M-1)-1) (((1+1)+1)+1)
1 5 M&N: (M-1) ((((1+1)+1)+1)+1)
1 4 M&N argev: (M-1) (((((1+1)+1)+1)+1)-1)
1 3 M&N argev: (M-1) ((((((1+1)+1)+1)+1)-1)-1)
1 2 M&N argev: (M-1) (((((((1+1)+1)+1)+1)-1)-1)-1)
1 1 M&N argev: (M-1) ((((((((1+1)+1)+1)+1)-1)-1)-1)-1)
1 0 M&N argev: (M-1) (((((((((1+1)+1)+1)+1)-1)-1)-1)-1)-1)
0 1 not N: ((M-1)-1) 1
0 2 M&N: ((M-1)-1) (1+1)
0 3 M&N: ((M-1)-1) ((1+1)+1)
0 4 M&N: ((M-1)-1) (((1+1)+1)+1)
0 5 M&N: ((M-1)-1) ((((1+1)+1)+1)+1)
0 6 M&N: ((M-1)-1) (((((1+1)+1)+1)+1)+1)
(7, '((((((1+1)+1)+1)+1)+1)+1)')

Is there a fast formula for computing results, ignoring the representation problem?

Regards,
Bengt Richter