# Ackermann Function¶

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:

$\begin{split}A(m, n) = \begin{cases} n+1 & \mbox{if } m = 0 \\ A(m-1, 1) & \mbox{if } m > 0 \mbox{ and } n = 0 \\ A(m-1, A(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0. \end{cases}\end{split}$

nCrypt has devised a way to calculate the value of the Ackermann function using native scripts. But it is definitely non-trivial. Below we present a much simpler version.

contract Ackermann {
int a;  // a = 2
int b;  // b = 1

function ackermann(int m, int n): int {
bytes stk = num2bin(m, 1);

// run this function off chain to get the loop count and set it here
// e.g., (2, 1) requires 14 loops, (3, 5) 42438
loop (14) {
if (len(stk) > 0) {
bytes top = stk[0:1];
m = unpack(top);

// pop
stk = stk[1:len(stk)];

if (m == 0) {
n = n + m + 1;
} else if (n == 0) {
n = n + 1;
m = m - 1;
// push
stk = num2bin(m, 1) + stk;
} else {
stk = num2bin(m - 1, 1) + stk;
stk = num2bin(m, 1) + stk;
n = n - 1;
}
}
}

return n;
}

// y = 5
public function unlock(int y) {
require(y == this.ackermann(this.a, this.b));
}
}