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).
Ada
<lang Ada>with Ada.Text_IO; use Ada.Text_IO;
procedure Sudan_Function is
function F (N, X, Y : Natural) return Natural is (if N = 0 then X + Y elsif Y = 0 then X else F (N => N - 1, X => F (N, X, Y - 1), Y => F (N, X, Y - 1) + Y));
begin
Put_Line ("F0 (0, 0) = " & F (0, 0, 0)'Image); Put_Line ("F1 (1, 1) = " & F (1, 1, 1)'Image); Put_Line ("F1 (3, 3) = " & F (1, 3, 3)'Image); Put_Line ("F2 (1, 1) = " & F (2, 1, 1)'Image); Put_Line ("F2 (2, 1) = " & F (2, 2, 1)'Image); Put_Line ("F3 (1, 1) = " & F (3, 1, 1)'Image);
end Sudan_Function;</lang>
- Output:
F0 (0, 0) = 0 F1 (1, 1) = 3 F1 (3, 3) = 35 F2 (1, 1) = 8 F2 (2, 1) = 27 F3 (1, 1) = 10228
ALGOL 68
...with a minor optimisation. <lang algol68>BEGIN # compute some values of the Sudan function #
PROC sudan = ( INT n, x, y )INT: IF n = 0 THEN x + y ELIF y = 0 THEN x ELSE INT s = sudan( n, x, y - 1 ); sudan( n - 1, s, s + y ) FI # sudan # ; FOR n FROM 0 TO 1 DO print( ( "Values of F(", whole( n, 0 ), ", x, y):", newline ) ); print( ( "y/x 0 1 2 3 4 5", newline ) ); print( ( "----------------------------", newline ) ); FOR y FROM 0 TO 6 DO print( ( whole( y, 0 ), " |" ) ); FOR x FROM 0 TO 5 DO print( ( whole( sudan( n, x, y ), -4 ) ) ) OD; print( ( newline ) ) OD; print( ( newline ) ) OD; print( ( newline ) ); print( ( "F(2, 1, 1) = ", whole( sudan( 2, 1, 1 ), 0 ), newline ) ); print( ( "F(3, 1, 1) = ", whole( sudan( 3, 1, 1 ), 0 ), newline ) ); print( ( "F(2, 2, 1) = ", whole( sudan( 2, 2, 1 ), 0 ), newline ) )
END</lang>
- Output:
Values of F(0, x, y): y/x 0 1 2 3 4 5 ---------------------------- 0 | 0 1 2 3 4 5 1 | 1 2 3 4 5 6 2 | 2 3 4 5 6 7 3 | 3 4 5 6 7 8 4 | 4 5 6 7 8 9 5 | 5 6 7 8 9 10 6 | 6 7 8 9 10 11 Values of F(1, x, y): y/x 0 1 2 3 4 5 ---------------------------- 0 | 0 1 2 3 4 5 1 | 1 3 5 7 9 11 2 | 4 8 12 16 20 24 3 | 11 19 27 35 43 51 4 | 26 42 58 74 90 106 5 | 57 89 121 153 185 217 6 | 120 184 248 312 376 440 F(2, 1, 1) = 8 F(3, 1, 1) = 10228 F(2, 2, 1) = 27
C
<lang C> //Aamrun, 11th July 2022
- include <stdio.h>
int F(int n,int x,int y) {
if (n == 0) { return x + y; } else if (y == 0) { return x; } return F(n - 1, F(n, x, y - 1), F(n, x, y - 1) + y);
}
int main() {
printf("F1(3,3) = %d",F(1,3,3)); return 0;
} </lang>
Output
F1(3,3) = 35
C++
<lang cpp> //Aamrun , 11th July, 2022
- include <iostream>
using namespace std;
int F(int n,int x,int y) {
if (n == 0) { return x + y; } else if (y == 0) { return x; } return F(n - 1, F(n, x, y - 1), F(n, x, y - 1) + y);
}
int main() {
cout << "F(1,3,3) = "<<F(1,3,3)<<endl; return 0;
} </lang> Output
F(1,3,3) = 35
C#
<lang csharp> //Aamrun, 11th July 2022
using System;
namespace Sudan {
class Sudan { static int F(int n,int x,int y) { if (n == 0) { return x + y; } else if (y == 0) { return x; } return F(n - 1, F(n, x, y - 1), F(n, x, y - 1) + y);
}
static void Main(string[] args) { Console.WriteLine("F(1,3,3) = " + F(1,3,3)); } }
} </lang> Output
F(1,3,3) = 35
Go
<lang go>package main
import "fmt"
func F(n, x, y int) int {
if n == 0 { return x + y } if y == 0 { return x } return F(n-1, F(n, x, y-1), F(n, x, y-1)+y)
}
func main() {
for n := 0; n < 2; n++ { fmt.Printf("Values of F(%d, x, y):\n", n) fmt.Println("y/x 0 1 2 3 4 5") fmt.Println("----------------------------") for y := 0; y < 7; y++ { fmt.Printf("%d |", y) for x := 0; x < 6; x++ { fmt.Printf("%4d", F(n, x, y)) } fmt.Println() } fmt.Println() } fmt.Printf("F(2, 1, 1) = %d\n", F(2, 1, 1)) fmt.Printf("F(3, 1, 1) = %d\n", F(3, 1, 1)) fmt.Printf("F(2, 2, 1) = %d\n", F(2, 2, 1))
}</lang>
- Output:
Identical to Wren example.
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>
Java
<lang Java> //Aamrun, 11th July 2022
public class Main {
private static int F(int n,int x,int y) { if (n == 0) { return x + y; } else if (y == 0) { return x; } return F(n - 1, F(n, x, y - 1), F(n, x, y - 1) + y); }
public static void main(String[] args) { System.out.println("F(1,3,3) = " + F(1,3,3)); }
} </lang> Output
F(1,3,3) = 35
JavaScript
<lang Javascript> /**
* @param {bigint} n * @param {bigint} x * @param {bigint} y * @returns {bigint} */
function F(n, x, y) {
if (n === 0) { return x + y; }
if (y === 0) { return x; }
return F(n - 1, F(n, x, y - 1), F(n, x, y - 1) + y);
} </lang>
PHP
<lang php>
- Aamrun , 11th July 2022
<?php function F(int $n,int $x,int $y) {
if ($n == 0) { return $x + $y; } else if ($y == 0) { return $x; } return F($n - 1, F($n, $x, $y - 1), F($n, $x, $y - 1) + $y);
} echo "F(1,3,3) = " . F(1,3,3); ?> </lang> Output
F(1,3,3) = 35
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
Python
<lang Python>
- Aamrun, 11th July 2022
def F(n,x,y):
if n==0: return x + y elif y==0: return x else: return F(n - 1, F(n, x, y - 1), F(n, x, y - 1) + y)
print("F(1,3,3) = ", F(1,3,3)) </lang>
Output
F(1,3,3) = 35
R
<lang rsplus>
- Aamrun, 11th July 2022
F <- function(n, x, y) {
if(n==0){ F <- x+y return (F) } else if(y == 0) { F <- x return (F) } F <- F(n - 1, F(n, x, y - 1), F(n, x, y - 1) + y) return (F)
}
print(paste("F(1,3,3) = " , F(1,3,3))) </lang> Output
[1] "F(1,3,3) = 35"
Vlang
<lang ruby>fn sudan(n int, x int, y int) int {
if n == 0 { return x + y } if y == 0 { return x } return sudan(n-1, sudan(n, x, y-1), sudan(n, x, y-1) + y)
}
fn main() {
for n := 0; n < 2; n++ { println("Values of F($n, x, y):") println("y/x 0 1 2 3 4 5") println("----------------------------") for y := 0; y < 7; y++ { print("$y |") for x := 0; x < 6; x++ { s := sudan(n, x, y) print("${s:4}") } println() } println() } println("F(2, 1, 1) = ${sudan(2, 1, 1)}") println("F(3, 1, 1) = ${sudan(3, 1, 1)}") println("F(2, 2, 1) = ${sudan(2, 2, 1)}")
}</lang>
- Output:
Identical to Wren example.
Wren
<lang ecmascript>import "./fmt" for Fmt
var F = Fn.new { |n, x, y|
if (n == 0) return x + y if (y == 0) return x return F.call(n - 1, F.call(n, x, y-1), F.call(n, x, y-1) + y)
}
for (n in 0..1) {
System.print("Values of F(%(n), x, y):") System.print("y/x 0 1 2 3 4 5") System.print("----------------------------") for (y in 0..6) { System.write("%(y) |") for (x in 0..5) { var sudan = F.call(n, x, y) Fmt.write("$4d", sudan) } System.print() } System.print()
} System.print("F(2, 1, 1) = %(F.call(2, 1, 1))") System.print("F(3, 1, 1) = %(F.call(3, 1, 1))") System.print("F(2, 2, 1) = %(F.call(2, 2, 1))")</lang>
- Output:
Values of F(0, x, y): y/x 0 1 2 3 4 5 ---------------------------- 0 | 0 1 2 3 4 5 1 | 1 2 3 4 5 6 2 | 2 3 4 5 6 7 3 | 3 4 5 6 7 8 4 | 4 5 6 7 8 9 5 | 5 6 7 8 9 10 6 | 6 7 8 9 10 11 Values of F(1, x, y): y/x 0 1 2 3 4 5 ---------------------------- 0 | 0 1 2 3 4 5 1 | 1 3 5 7 9 11 2 | 4 8 12 16 20 24 3 | 11 19 27 35 43 51 4 | 26 42 58 74 90 106 5 | 57 89 121 153 185 217 6 | 120 184 248 312 376 440 F(2, 1, 1) = 8 F(3, 1, 1) = 10228 F(2, 2, 1) = 27