fbpx

C++: Ackermann Function

Bjarne-stroustrup
 

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:

 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}

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";
		}
	}
}

SOURCE

Content is available under GNU Free Documentation License 1.2.

Our team found a curious site for our readers that are fans of online gaming, a rather exciting site that provides the latest gaming technology. Casinodots.com is the site, they compile the best reviews of MGA casino utan svensk licens sites. This site might pique your curiosity and you can win extra money!