Sudan function
You are encouraged to solve this task according to the task description, using any language you may know.
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.
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>
J
This is, of course, not particularly efficient and some results are too large for a computer to represent. <lang J>F=: {{ 'N X Y'=. y assert. N>:0
if. 0=N do. X+Y elseif. Y=0 do. X else. F (N-1),(F N,X,Y-1), Y+F N, X, Y-1 end.
}}"1</lang>
Examples: <lang J> F 0 0 0 0
F 1 1 1
3
F 2 1 1
8
F 3 1 1
10228
F 2 2 1
27</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>
Julia
<lang ruby>using Memoize
@memoize function sudan(n, x, y)
return n == 0 ? x + y : y == 0 ? x : sudan(n - 1, sudan(n, x, y - 1), sudan(n, x, y - 1) + y)
end
foreach(t -> println("sudan($(t[1]), $(t[2]), $(t[3])) = ",
sudan(t[1], t[2], t[3])), ((0,0,0), (1,1,1), (2,1,1), (3,1,1), (2,2,1)))
</lang>
- Output:
sudan(0, 0, 0) = 0 sudan(1, 1, 1) = 3 sudan(2, 1, 1) = 8 sudan(3, 1, 1) = 10228 sudan(2, 2, 1) = 27