Ackermann function

From Esolang

The Ackermann function is probably the most well-known example of a function that is computable but which grows so extremely fast that it is not primitive recursive. Thus being able to calculate it is a test of the computational class of a language.

It is a function of two natural numbers, returning a natural number. Its definition is by recursion in two variables:

int A(int m,int n) {
  if (m==0) { return n+1; }
  else if (n==0) { return A(m-1,1); }
  else { return A(m-1,A(m,n-1)); }
}

[edit] External resources

• Ackermann function on Wikipedia.