Hummus - 4 months ago 73

Python 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

Answer

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.