Sudan function
The Sudan function is a classic example of a recursive function, notable especially because it is not a 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.
You are encouraged to solve this task according to the task description, using any language you may know.
The Sudan function is usually defined as follows (svg):
<big>
:<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>
</big>
- Task
Write a function which returns the value of F(x, y).
Hoon
<lang Hoon> |= [n=@ x=@ y=@] ^- @ |- ?: =(n 0)
(add x y)
?: =(y 0)
x
$(n (dec n), x $(n n, x x, y (dec y)), y (add $(n n, x x, y (dec y)) y)) </lang>
JavaScript
<lang Javascript> /**
* @param {bigint} n
* @param {bigint} x
* @param {bigint} y
* @returns {bigint}
*/
function F(n, x, y) {
if (n === 0n) {
return x + y;
}
if (y === 0n) {
return x;
}
return F(n - 1n, F(n, x, y - 1n), F(n, x, y - 1n) + y);
} </lang>