Problem 734. Ackermann's Function

Ackermann's Function is a recursive function that is not 'primitive recursive.'

Ackermann Function

The first argument drives the value extremely fast.

A(m, n) =

• n + 1 if m = 0
• A(m − 1, 1) if m > 0 and n = 0
• A(m − 1,A(m, n − 1)) if m > 0 and n > 0

A(2,4)=A(1,A(2,3)) = ... = 11.

% Range of cases
% m=0 n=0:1024
% m=1 n=0:1024
% m=2 n=0:128
% m=3 n=0:6
% m=4 n=0:1

There is some deep recusion.

Input: m,n

Out: Ackerman value

Ackermann(2,4) = 11

Practical application of Ackermann's function is determining compiler recursion performance.