15 lines
788 B
Plaintext
15 lines
788 B
Plaintext
The '''[[wp:Sudan function|Sudan function]]''' is a classic example of a recursive function, notable especially because it is not a [[wp:Primitive_recursive_function|primitive recursive function]]. This is also true of the better-known [[Ackermann function]]. The Sudan function was the first function having this property to be published.
|
|
|
|
The Sudan function is usually defined as follows ([https://wikimedia.org/api/rest_v1/media/math/render/svg/59304f0b3ff0baad7dd21f5ce16ce6fa241111a2 svg]):
|
|
|
|
<math>\begin{array}{lll}
|
|
F_0 (x, y) & = x+y \\
|
|
F_{n+1} (x, 0) & = x & \text{if } n \ge 0 \\
|
|
F_{n+1} (x, y+1) & = F_n (F_{n+1} (x, y), F_{n+1} (x, y) + y + 1) & \text{if } n\ge 0 \\
|
|
\end{array}
|
|
</math>
|
|
|
|
;Task:
|
|
Write a function which returns the value of F(x, y).
|
|
|