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). Arbitrary precision is preferred (since the function grows so quickly), but not required.
#include <iostream> unsigned int ackermann(unsigned int m, unsigned int n) { if (m == 0) { return n + 1; } if (n == 0) { return ackermann(m - 1, 1); } return ackermann(m - 1, ackermann(m, n - 1)); } int main() { for (unsigned int m = 0; m < 4; ++m) { for (unsigned int n = 0; n < 10; ++n) { std::cout << "A(" << m << ", " << n << ") = " << ackermann(m, n) << "\n"; } } }
Content is available under GNU Free Documentation License 1.2.