26 lines
1.2 KiB
Plaintext
26 lines
1.2 KiB
Plaintext
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> <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>
|