Problem Statement

The Ackermann function is a classic example of a recursive function, notable especially because it is not a primitive recursive function. It grows very quickly in value, as does the size of its call tree.

The Ackermann function is usually defined as follows:

Its arguments are never negative and it always terminates.

Write a function which returns the value of

A ( m , n )

{\displaystyle A(m,n)}

. Arbitrary precision is preferred (since the function grows so quickly), but not required.

Let's start with the solution:

/* Ackermann function, in Jsish */

function ack(m, n) {
 return m === 0 ? n + 1 : ack(m - 1, n === 0  ? 1 : ack(m, n - 1));
}

if (Interp.conf('unitTest')) {
    Interp.conf({maxDepth:4096});
;    ack(1,3);
;    ack(2,3);
;    ack(3,3);
;    ack(1,5);
;    ack(2,5);
;    ack(3,5);
}

/*
=!EXPECTSTART!=
ack(1,3) ==> 5
ack(2,3) ==> 9
ack(3,3) ==> 61
ack(1,5) ==> 7
ack(2,5) ==> 13
ack(3,5) ==> 253
=!EXPECTEND!=
*/