ackermann-visualizer

A basic tool for visually tracing the recursive call stack for the Ackermann–Péter function.

Build

gcc

g++ -std=c++11 -o ackermann_visualizer ackermann_visualizer.cpp

clang

clang++ -Wall -std=c++11 ackermann_visualizer.cpp -o ackermann_visualizer

Usage

 ackermann_visualizer m n [filename]

m: positive integer m in A(m, n)
n: positive integer n in A(m, n)
filename: optionally output to a file instead of console

Example

 ackermann_visualizer 2 2

Output:

A(1, 2)
A(0, A(1, 1))
A(0, A(0, A(1, 0)))
A(0, A(0, A(0, 1)))
A(0, A(0, 2))
A(0, 3)
Value: 4
Number of calls: 6
Run time: 0.000000 seconds

Note

This program may crash with high enough input values due to a recursion stack overflow. The Ackermann call stack grows very quickly.

Why?

Examining the definition of the function, Let RA(m, n) define the number of calls to A(m, n).

$RA(m,n)= \begin{cases} 1 & \text{for } m=0\\ 1 + RA(m-1, 1) & \text{for } m>0 \text{ and } n=0\\ 1 + RA(m, n-1) + RA(m-1, A(m, n-1)) & \text{for } m>0 \text{ and }n>0 \\ \end{cases}$

It can be concluded through some proof that:

$RA(m,n)=(n+1) + RA(m-1,1) + \sum_{k=0}^{n-1} RA(m-1,A(m,k))$

So for example:

$RA(3,n) = 128\frac{4^n-1}{3} - 40\left(2^n-1\right) + 3n + 15$

So, the number of calls for A(3, 6):

And even crazier:

Source

It is then evident how quickly one can hit the limit of the stack size even for small integer input. Also, I doubt most of the output would be useful visually for computations with that level of recursion. This program is however quite nice for input that produces smaller output.

License

MIT

enioluwas/ackermann-visualizer