Ackermann function (deep recursion)

Hard TimeNon-primitive-recursive (grows explosively) SpaceO(depth) stack

The Ackermann function is defined by three rules: A(0, n) is n + 1; A(m, 0) is A(m - 1, 1); and otherwise A(m, n) is A(m - 1, A(m, n - 1)). Given m and n, both zero or greater, return A(m, n). The third rule's inner call has to be finished before the outer one can start.

Examples

Example 1

Input
m = 2n = 2
Output
7
A(2, 2) is A(1, A(2, 1)), and A(2, 1) is 5, so it is A(1, 5) — 7.

Example 2

Input
m = 3n = 3
Output
61
One more on each argument takes the answer from 7 to 61.

The Code

function ackermann(m, n) {
  if (m === 0) return n + 1;
  if (n === 0) return ackermann(m - 1, 1);
  return ackermann(m - 1, ackermann(m, n - 1));
}
ackermann(2, 2);
Done
Step through ackermann(2, 2) call by call

More like this

All recursion examples (13) →