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).
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
BASIC
BASIC256
<lang freebasic>for n = 0 to 1
print "Values of F(" & n & ", x, y):" print "y/x 0 1 2 3 4 5" print ("-"*28) for y = 0 to 6 print y; " |"; for x = 0 to 5 print rjust(string(F(n,x,y)),4); next x print next y print
next n
print "F(2,1,1) = "; F(2,1,1) print "F(3,1,1) = "; F(3,1,1) print "F(2,2,1) = "; F(2,2,1) end
function F(n, x, y)
if n = 0 then return x + y if y = 0 then return x return F(n - 1, F(n, x, y - 1), F(n, x, y - 1) + y)
end function</lang>
- Output:
Same as FreeBASIC entry.
PureBasic
<lang PureBasic>Procedure.d F(n.i, x.i, y.i)
If n = 0 ProcedureReturn x + y ElseIf y = 0 ProcedureReturn x Else ProcedureReturn F(n - 1, F(n, x, y - 1), F(n, x, y - 1) + y) EndIf
EndProcedure
OpenConsole() For n = 0 To 1
PrintN("Values of F(" + Str(n) + ", x, y):") PrintN("y/x 0 1 2 3 4 5") PrintN("---------------------------------------------------") For y = 0 To 6 Print(Str(y) + " |") For x = 0 To 5 Print(#TAB$ + F(n,x,y)) Next x PrintN("") Next y PrintN("")
Next n
PrintN("F(2,1,1) = " + Str(F(2,1,1))) PrintN("F(3,1,1) = " + Str(F(3,1,1))) PrintN("F(2,2,1) = " + Str(F(2,2,1))) Input() CloseConsole()</lang>
- Output:
Similat to FreeBASIC entry.
Yabasic
<lang freebasic>for n = 0 to 1
print "Values of F(", n, ", x, y):" print "y/x 0 1 2 3 4 5" print "----------------------------" for y = 0 to 6 print y, " | "; for x = 0 to 5 print F(n,x,y) using ("###"); next x print next y print
next n
print "F(2,1,1) = ", F(2,1,1) print "F(3,1,1) = ", F(3,1,1) print "F(2,2,1) = ", F(2,2,1) end
sub 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)
end sub</lang>
- Output:
Same as FreeBASIC entry.
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
FreeBASIC
<lang freebasic>Function F(n As Integer, x As Integer, y As Integer) As Integer
If n = 0 Then Return x + y If y = 0 Then Return x Return F(n - 1, F(n, x, y - 1), F(n, x, y - 1) + y)
End Function
Dim As Integer n, x, y For n = 0 To 1
Print " Values of F(" & n & ", x, y):" Print " y/x 0 1 2 3 4 5" Print String(29, "-") For y = 0 To 6 Print y; " |"; For x = 0 To 5 Print Using "####"; F(n,x,y); Next x Print Next y Print
Next n
Print "F(2,1,1) ="; F(2,1,1) Print "F(3,1,1) ="; F(3,1,1) Print "F(2,2,1) ="; F(2,2,1) Sleep</lang>
- Output:
Same as Wren entry.
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>
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
Phix
with javascript_semantics function F(integer n, x, y) if n=0 then return x+y end if if y=0 then return x end if integer t = F(n,x,y-1) return F(n-1,t,t+y) end function for n=0 to 1 do printf(1,"Values of F(%d, x, y):\n",n) printf(1,"y/x 0 1 2 3 4 5\n") printf(1,"----------------------------\n") for y=0 to 6 do sequence r = apply(true,F,{n,tagset(5,0),y}) printf(1,"%d |%s\n",{y,join(r,"",fmt:="%4d")}) end for printf(1,"\n") end for for t in {{2,1,1},{3,1,1},{2,2,1}} do integer {n,x,y} = t printf(1,"F(%d, %d, %d) = %d\n",{n,x,y,F(n,x,y)}) end for
Output same as Wren.
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
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"
Ruby
<lang ruby> def sudan(n, x, y)
return x + y if n == 0 return x if y == 0
sudan(n - 1, sudan(n, x, y - 1), sudan(n, x, y - 1) + y)
end </lang>
Output
puts sudan(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