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):
- Task
Write a function which returns the value of F(x, y).
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;
- 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.
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
- 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
APL
sudan←{
0∨.>⍺ ⍺⍺ ⍵:'Negative input'⎕SIGNAL 11
⍺⍺=0:⍺+⍵
⍵=0:⍺
tm((⍺⍺-1)∇∇)⍵+tm←⍺∇⍵-1
}
- Output:
0 sudan/¨ ¯1+⍳ 6 7 0 1 2 3 4 5 6 1 2 3 4 5 6 7 2 3 4 5 6 7 8 3 4 5 6 7 8 9 4 5 6 7 8 9 10 5 6 7 8 9 10 11 1 sudan/¨ ¯1+⍳ 6 7 0 1 4 11 26 57 120 1 3 8 19 42 89 184 2 5 12 27 58 121 248 3 7 16 35 74 153 312 4 9 20 43 90 185 376 5 11 24 51 106 217 440 1 (2 sudan) 1 8 1 (3 sudan) 1 10228 2 (2 sudan) 1 27
AWK
# syntax: GAWK -f SUDAN_FUNCTION.AWK
BEGIN {
for (n=0; n<=1; n++) {
printf("sudan(%d,x,y)\n",n)
printf("y/x 0 1 2 3 4 5\n")
printf("%s\n",strdup("-",28))
for (y=0; y<=6; y++) {
printf("%2d | ",y)
for (x=0; x<=5; x++) {
printf("%3d ",sudan(n,x,y))
}
printf("\n")
}
printf("\n")
}
n=1; x=3; y=3; printf("sudan(%d,%d,%d)=%d\n",n,x,y,sudan(n,x,y))
n=2; x=1; y=1; printf("sudan(%d,%d,%d)=%d\n",n,x,y,sudan(n,x,y))
n=2; x=2; y=1; printf("sudan(%d,%d,%d)=%d\n",n,x,y,sudan(n,x,y))
n=3; x=1; y=1; printf("sudan(%d,%d,%d)=%d\n",n,x,y,sudan(n,x,y))
exit(0)
}
function sudan(n,x,y) {
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)
}
function strdup(str,n, i,new_str) {
for (i=1; i<=n; i++) {
new_str = new_str str
}
return(new_str)
}
- Output:
sudan(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 sudan(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 sudan(1,3,3)=35 sudan(2,1,1)=8 sudan(2,2,1)=27 sudan(3,1,1)=10228
BASIC
BASIC256
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
- Output:
Same as FreeBASIC entry.
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()
- Output:
Similat to FreeBASIC entry.
Yabasic
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
- Output:
Same as FreeBASIC entry.
BCPL
get "libhdr"
let sudan(n, x, y) =
n = 0 -> x + y,
y = 0 -> x,
sudan(n-1, sudan(n, x, y-1), sudan(n, x, y-1)+y)
let showtable(f, n, x, y) be
$( writef("sudan(%N,x,y)*N", n)
writes(" ")
for i=0 to x do writed(i, 5)
for i=0 to y
$( writef("*N%I4:", i)
for j=0 to x do writed(f(n, j, i), 5)
$)
writes("*N*N")
$)
let show(f, n, x, y) be
writef("sudan(%I4,%I4,%I4) = %I6*N", n, x, y, f(n, x, y))
let start() be
$( showtable(sudan, 0, 6, 5)
showtable(sudan, 1, 6, 5)
wrch('*N')
show(sudan, 1, 3, 3)
show(sudan, 2, 1, 1)
show(sudan, 2, 2, 1)
show(sudan, 3, 1, 1)
$)
- Output:
sudan(0,x,y) 0 1 2 3 4 5 6 0: 0 1 2 3 4 5 6 1: 1 2 3 4 5 6 7 2: 2 3 4 5 6 7 8 3: 3 4 5 6 7 8 9 4: 4 5 6 7 8 9 10 5: 5 6 7 8 9 10 11 sudan(1,x,y) 0 1 2 3 4 5 6 0: 0 1 2 3 4 5 6 1: 1 3 5 7 9 11 13 2: 4 8 12 16 20 24 28 3: 11 19 27 35 43 51 59 4: 26 42 58 74 90 106 122 5: 57 89 121 153 185 217 249 sudan( 1, 3, 3) = 35 sudan( 2, 1, 1) = 8 sudan( 2, 2, 1) = 27 sudan( 3, 1, 1) = 10228
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;
}
Output
F1(3,3) = 35
C++
//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;
}
Output
F(1,3,3) = 35
C#
//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));
}
}
}
Output
F(1,3,3) = 35
F#
let rec sudan = function
0L, x, y -> x + y
|_, x, 0L -> x
|n, x, y -> let x' = sudan (n, x, y-1L) in sudan (n-1L, x', x' + y)
printfn "%d\n%d\n%d" (sudan(1L, 13L, 14L)) (sudan(2L, 5L, 1L)) (sudan(2L, 2L, 2L))
- Output:
245744 440 15569256417
Factor
USING: combinators kernel math prettyprint ;
: sudan ( n x y -- z )
{
{ [ pick zero? ] [ nipd + ] }
{ [ dup zero? ] [ drop nip ] }
[
[ 2drop 1 - ]
[ 1 - sudan dup ]
[ 2nip + sudan ] 3tri
]
} cond ;
3 1 1 sudan .
- Output:
10228
Or with locals:
USING: combinators kernel locals math prettyprint ;
:: sudan ( n x y -- z )
{
{ [ n zero? ] [ x y + ] }
{ [ y zero? ] [ x ] }
[ n 1 - n x y 1 - sudan dup y + sudan ]
} cond ;
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
- Output:
Same as Wren entry.
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))
}
- Output:
Identical to Wren example.
Haskell
import Control.Monad.Memo (Memo, memo, startEvalMemo)
import Data.List.Split (chunksOf)
import System.Environment (getArgs)
import Text.Tabular (Header(..), Properties(..), Table(..))
import Text.Tabular.AsciiArt (render)
type SudanArgs = (Int, Integer, Integer)
-- Given argument (n, x, y) calculate Fₙ(x, y). For performance reasons we do
-- the calculation in a memoization monad.
sudan :: SudanArgs -> Memo SudanArgs Integer Integer
sudan (0, x, y) = return $ x + y
sudan (_, x, 0) = return x
sudan (n, x, y) = memo sudan (n, x, y-1) >>= \x2 -> sudan (n-1, x2, x2 + y)
-- A table of Fₙ(x, y) values, where the rows are y values and the columns are
-- x values.
sudanTable :: Int -> [Integer] -> [Integer] -> String
sudanTable n xs ys = render show show show
$ Table (Group NoLine $ map Header ys)
(Group NoLine $ map Header xs)
$ chunksOf (length xs)
$ startEvalMemo
$ sequence
$ [sudan (n, x, y) | y <- ys, x <- xs]
main :: IO ()
main = do
args <- getArgs
case args of
[n, xlo, xhi, ylo, yhi] -> do
putStrLn $ "Fₙ(x, y), where the rows are y values " ++
"and the columns are x values.\n"
putStr $ sudanTable (read n)
[read xlo .. read xhi]
[read ylo .. read yhi]
_ -> error "Usage: sudan n xmin xmax ymin ymax"
- Output:
$ sudan 0 0 5 0 6 Fₙ(x, y), where the rows are y values and the columns are x values. +---++---------------+ | || 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 | +---++---------------+ $ sudan 1 0 5 0 6 Fₙ(x, y), where the rows are y values and the columns are x values. +---++-------------------------+ | || 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 | +---++-------------------------+
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))
J
This is, of course, not particularly efficient and some results are too large for a computer to represent.
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
Examples:
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
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));
}
}
Output
F(1,3,3) = 35
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);
}
jq
def sudan(n;x;y):
if n == 0 then x+y
elif y == 0 then x
else sudan(n-1; sudan(n;x;y-1); sudan(n;x;y-1) + y)
end;
# For testing and syntactic convenience:
def sudan:
"sudan(\(.[0]); \(.[1]); \(.[2])) => \(sudan(.[0]; .[1]; .[2]))";
# Illustrations
[0,0,0], [1,1,1], [2,1,1], [3,1,1], [2,2,1]
| sudan
- 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
Julia
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)))
- 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
OCaml
let rec sudan = function
| 0, x, y -> x + y
| _, x, 0 -> x
| n, x, y -> let x' = sudan (n, x, pred y) in sudan (pred n, x', x' + y)
# sudan (1, 13, 14) ;; - : int = 245744 # sudan (2, 5, 1) ;; - : int = 440 # sudan (2, 2, 2) ;; - : int = 15569256417
Perl
Three ways of doing the same thing.
use v5.36;
use experimental 'for_list';
sub F1($n, $x, $y) { $n ? $y ? F1($n-1, F2($n,$x,$y-1), F3($n,$x,$y-1)+$y) : $x : $x+$y }
sub F2($n, $x, $y) { $n == 0 ? $x+$y : $y == 0 ? $x : F2($n-1, F1($n,$x,$y-1), F3($n,$x,$y-1)+$y) }
sub F3($n, $x, $y) {
return $x + $y if $n == 0;
return $x if $y == 0;
F3($n-1, F1($n, $x, $y-1), F2($n, $x, $y-1) + $y)
}
for my($n,$x,$y) (0,0,0, 1,1,1, 2,1,1, 3,1,1, 2,2,1) {
say join ' ',F1($n,$x,$y), F2($n,$x,$y), F3($n,$x,$y)
}
- Output:
0 0 0 3 3 3 8 8 8 10228 10228 10228 27 27 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
#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);
?>
Output
F(1,3,3) = 35
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))
Output
F(1,3,3) = 35
Quackery
[ rot dup 0 = iff
[ drop + ] done
over 0 = iff
2drop done
over temp put
dup 1 -
swap 2swap 1 -
recurse
dup temp take +
again ] is sudan ( n x y --> f(n) )
' [ [ 0 0 0 ]
[ 1 1 1 ]
[ 1 3 3 ]
[ 2 1 1 ]
[ 2 2 1 ]
[ 3 1 1 ] ]
witheach
[ dup echo say " = "
do sudan echo cr ]
- Output:
[ 0 0 0 ] = 0 [ 1 1 1 ] = 3 [ 1 3 3 ] = 35 [ 2 1 1 ] = 8 [ 2 2 1 ] = 27 [ 3 1 1 ] = 10228
R
#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)))
Output
[1] "F(1,3,3) = 35"
Raku
Outputting wiki-tables to more closely emulate the wikipedia examples. Not very efficient but good enough.
multi F (0, $x, $y) { $x + $y }
multi F ($n where * > 0, $x, 0) { $x }
multi F ($n, $x, $y) { F($n-1, F($n, $x, $y-1), F($n, $x, $y-1) + $y) }
# Testing
for 0, 6, 1, 15 -> $f, $g {
my @range = ^$g;
say "\{|class=\"wikitable\"\n", "|+ F\<sub>$f\</sub> (x,y)\n" ~ '!x\y!!', join '!!', @range;
-> $r { say "|-\n" ~ '|' ~ join '||', $r, @range.map:{ F($f, $r, $_) } } for @range;
say( "|}" );
}
- Output:
x\y | 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 |
x\y | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 1 | 4 | 11 | 26 | 57 | 120 | 247 | 502 | 1013 | 2036 | 4083 | 8178 | 16369 | 32752 |
1 | 1 | 3 | 8 | 19 | 42 | 89 | 184 | 375 | 758 | 1525 | 3060 | 6131 | 12274 | 24561 | 49136 |
2 | 2 | 5 | 12 | 27 | 58 | 121 | 248 | 503 | 1014 | 2037 | 4084 | 8179 | 16370 | 32753 | 65520 |
3 | 3 | 7 | 16 | 35 | 74 | 153 | 312 | 631 | 1270 | 2549 | 5108 | 10227 | 20466 | 40945 | 81904 |
4 | 4 | 9 | 20 | 43 | 90 | 185 | 376 | 759 | 1526 | 3061 | 6132 | 12275 | 24562 | 49137 | 98288 |
5 | 5 | 11 | 24 | 51 | 106 | 217 | 440 | 887 | 1782 | 3573 | 7156 | 14323 | 28658 | 57329 | 114672 |
6 | 6 | 13 | 28 | 59 | 122 | 249 | 504 | 1015 | 2038 | 4085 | 8180 | 16371 | 32754 | 65521 | 131056 |
7 | 7 | 15 | 32 | 67 | 138 | 281 | 568 | 1143 | 2294 | 4597 | 9204 | 18419 | 36850 | 73713 | 147440 |
8 | 8 | 17 | 36 | 75 | 154 | 313 | 632 | 1271 | 2550 | 5109 | 10228 | 20467 | 40946 | 81905 | 163824 |
9 | 9 | 19 | 40 | 83 | 170 | 345 | 696 | 1399 | 2806 | 5621 | 11252 | 22515 | 45042 | 90097 | 180208 |
10 | 10 | 21 | 44 | 91 | 186 | 377 | 760 | 1527 | 3062 | 6133 | 12276 | 24563 | 49138 | 98289 | 196592 |
11 | 11 | 23 | 48 | 99 | 202 | 409 | 824 | 1655 | 3318 | 6645 | 13300 | 26611 | 53234 | 106481 | 212976 |
12 | 12 | 25 | 52 | 107 | 218 | 441 | 888 | 1783 | 3574 | 7157 | 14324 | 28659 | 57330 | 114673 | 229360 |
13 | 13 | 27 | 56 | 115 | 234 | 473 | 952 | 1911 | 3830 | 7669 | 15348 | 30707 | 61426 | 122865 | 245744 |
14 | 14 | 29 | 60 | 123 | 250 | 505 | 1016 | 2039 | 4086 | 8181 | 16372 | 32755 | 65522 | 131057 | 262128 |
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
Output
puts sudan(1, 3, 3) > 35
V (Vlang)
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)}")
}
- Output:
Identical to Wren example.
Wren
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))")
- 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
XPL0
func F; int 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);
];
int N, X, Y;
[Format(4, 0);
for N:= 0 to 1 do
[Text(0, "Values of F("); IntOut(0, N); Text(0, ", X, Y):^m^j");
Text(0, "Y/X 0 1 2 3 4 5^m^j");
Text(0, "----------------------------^m^j");
for Y:= 0 to 6 do
[IntOut(0, Y); Text(0, " |");
for X:= 0 to 5 do
RlOut(0, float(F(N, X, Y)));
CrLf(0);
];
CrLf(0);
];
Text(0, "F(2, 1, 1) = "); IntOut(0, F(2, 1, 1)); CrLf(0);
Text(0, "F(3, 1, 1) = "); IntOut(0, F(3, 1, 1)); CrLf(0);
Text(0, "F(2, 2, 1) = "); IntOut(0, F(2, 2, 1)); CrLf(0);
]
- 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