RosettaCodeData/Task/Ackermann-function/00DESCRIPTION

The '''[[wp:Ackermann function|Ackermann function]]''' is a classic example of a recursive function, notable especially because it is not a [[wp:Primitive_recursive_function|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:

<big>
:<math> 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}
</math>
</big>

<!-- <table><tr><td width=12><td><td><math>n+1</math><td>if <math>m=0</math> <tr><td> <td><math>A(m, n) =</math> <td><math>A(m-1, 1)</math> <td>if <math>m>0</math> and <math>n=0</math> <tr><td><td><td><math>A(m-1, A(m, n-1))</math>&nbsp;&nbsp;<td> if <math>m>0</math> and <math>n>0</math></table> -->

Its arguments are never negative and it always terminates.

;Task:
Write a function which returns the value of <math>A(m, n)</math>. Arbitrary precision is preferred (since the function grows so quickly), but not required.

;See also:
* [[wp:Conway_chained_arrow_notation#Ackermann_function|Conway chained arrow notation]] for the Ackermann function.
<br><br>