# Ackermann function

Jump to navigation
Jump to search

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:

unsigned int A(unsigned int m,unsigned 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)); } }