Ackermann Function Understanding

Question

I'm finding it difficult to understand how the Ackermann Function works. I think my understanding of recursion is flawed?

Here is the code in Python:

  def naive_ackermann(m, n):
    global calls
    calls += 1
    if m == 0:
        return n + 1
    elif n == 0:
        return naive_ackermann(m - 1, 1)
    else:
        return naive_ackermann(m - 1, naive_ackermann(m, n - 1))

If I do the function call of naive_ackermann(3,4), how and why do I end up getting 125?

Comments will be appreciated.

Thanks

Solution 1

The computation of A(3,4) is not as easy or short as it might appear at first from the small values of the arguments. The complexity (# of iteration steps) of the Ackermann function grows very rapidly with its arguments, as does the computed result.

Here is the definition of the Ackermann function from Wikipedia:

As you can see, at every iteration, the value of m decreases until it reaches 0 in what will be the last step, at which point the final value of n (+1) gives you the answer. So for the answer, you only need to trace how n changes as you go through the recursive iterations. For why the Ackermann function grows so rapidly, you can take a look at this subsection of the wiki.

As Joran Beasley has already mentioned, A(3,4) is indeed 125, as written in Wikipedia. However, the process to get to this result is not very short. In fact, as I found out, it is required to compute by recursion 315 Ackermann function values to get A(3,4), the number of iterations required being roughly proportional to that.

If you still wish to visualize how this result is arrived at, you can take a look at this page, which animates the calculation of every recursion step. Be warned, though, that A(3,4) will take forever to finish animating here, but at least you might get some idea of the process with smaller arguments.

Solution 2

Here's a version that prints an explanation:

def A(m, n, s="%s"):
    print s % ("A(%d,%d)" % (m, n))
    if m == 0:
        return n + 1
    if n == 0:
        return A(m - 1, 1, s)
    n2 = A(m, n - 1, s % ("A(%d,%%s)" % (m - 1)))
    return A(m - 1, n2, s)

print A(2,2)

With arguments 2,2 the output is this. (With 3,4 it becomes already a bit too much)

A(2,2)
A(1,A(2,1))
A(1,A(1,A(2,0)))
A(1,A(1,A(1,1)))
A(1,A(1,A(0,A(1,0))))
A(1,A(1,A(0,A(0,1))))
A(1,A(1,A(0,2)))
A(1,A(1,3))
A(1,A(0,A(1,2)))
A(1,A(0,A(0,A(1,1))))
A(1,A(0,A(0,A(0,A(1,0)))))
A(1,A(0,A(0,A(0,A(0,1)))))
A(1,A(0,A(0,A(0,2))))
A(1,A(0,A(0,3)))
A(1,A(0,4))
A(1,5)
A(0,A(1,4))
A(0,A(0,A(1,3)))
A(0,A(0,A(0,A(1,2))))
A(0,A(0,A(0,A(0,A(1,1)))))
A(0,A(0,A(0,A(0,A(0,A(1,0))))))
A(0,A(0,A(0,A(0,A(0,A(0,1))))))
A(0,A(0,A(0,A(0,A(0,2)))))
A(0,A(0,A(0,A(0,3))))
A(0,A(0,A(0,4)))
A(0,A(0,5))
A(0,6)
7

Solution 3

ackerman(3,4) 

=ackerman(2,ackerman(3,3)) = ackerman(2,61)    #ackerman(3,3) = 61 ...
=ackerman(1,ackerman(2,60)) = ackerman (1,123)  #ackerman(2,60) = 123...
=ackerman(0,ackerman(1,122)) = ackerman (0,124)  #ackerman(1,122) = 124...
= 124+1 = 125

see http://goo.gl/jDDEA here to visualize ackerman(2,3) ( It was too long to visualize 3,4)

Comments

[Hummus]

How do you get ackerman(2,61) from ackerman(2,ackerman(3,3))? Where did the 61 come from?

[Joran Beasley]

ackerman(3,3) = 61 so ackerman(2,ackerman(3,3)) = ackerman(2,61) @MaksymPolshcha how is it wrong ... I looked at that wikipedia entry and all my numbers add up...

[Joran Beasley]

why -1? who put that? please explain

[Cagy79]

Please link to the "this page" you mentioned.