9. (Ackermann Function)

Consider the Ackermann function:

A(m, n) =

⎧⎪⎨⎪⎩

n + 1 if m = 0 A(m − 1, 1) if m > 0 and n = 0 A(m − 1, A(m, n − 1)) if m > 0 and n > 0 Implement this definition in C++ and experiment with the following examples:

A(1, 2) = 4 A(4, 3) = 2265536 − 3 A(1, 3) = 5.

Compute A(1, 3) by hand. How many steps are there?
Investigate what happens in the following code and why:
std::cout << Ackermann(1,3) << std::endl;
std::cout << Ackermann(1,2) << std::endl;
// Stack overflow and program 'silently' stops try {
std::cout << Ackermann(4,3) << std::endl;
}
catch (std::exception& e)
{
std::cout << e.what() << std::endl;
}
Now implement the Ackermann function as a metafunction.