# Sudan function

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):

${\displaystyle \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} }$

Write a function which returns the value of F(x, y).

## 8080 Assembly

        org     100h
jmp     demo
;; Sudan function. BC=N, DE=X, HL=Y; output in HL.
sudan:  mov     a,b             ; N=0?
ora     c
jz      sdnbse
mov     a,h             ; Y=0?
ora     l
jz      sdnbse
push    b               ; Save N and Y (we don't need X)
push    h
dcx     h
call    sudan           ; Calculate result of inner call
xchg                    ; Set X = result of inner call
pop     h               ; Get Y
dad     d               ; Set Y = Y + result of inner call
pop     b               ; Get N
dcx     b               ; N = N-1
jmp     sudan           ; Calculate result of outer call
sdnbse: dad     d               ; Return X+Y (base case)
ret

;; Output routine (show 'sudan(N,X,Y) = value'), using CP/M call
show:   push    h!      push    d!      push    b!      ; Copies of args
push    h!      push    d!      push    b!      ; For output
lxi     d,sdt!  call    pstr                    ; Print call
pop     h!      call    prhl
lxi     d,sdc!  call    pstr
pop     h!      call    prhl
lxi     d,sdc!  call    pstr
pop     h!      call    prhl
lxi     d,sdi!  call    pstr
pop     b!      pop     d!      pop     h!      ; Restore args
call    sudan!  call    prhl                    ; Find and print result
lxi     d,sdnl! jmp     pstr
prhl:   lxi     d,numbuf!       push    d!      lxi     b,-10
prdgt:  lxi     d,-1
pdiv:   inx     d!              dad     b!      jc      pdiv
mvi     a,'0'+10!       add     l!      pop     h
dcx     h!              mov     m,a!    push    h
xchg!   mov     a,h!    ora     l!      jnz     prdgt
pop     d
pstr:   mvi     c,9!    jmp     5

;; Set up big system stack (using CP/M)
demo:   lhld    6
sphl
;; Show a couple of values
lxi     b,0!    lxi     d,0!    lxi     h,0!    call    show
lxi     b,1!    lxi     d,1!    lxi     h,1!    call    show
lxi     b,2!    lxi     d,1!    lxi     h,1!    call    show
lxi     b,3!    lxi     d,1!    lxi     h,1!    call    show
lxi     b,2!    lxi     d,2!    lxi     h,1!    call    show
rst     0
sdt:    db      'sudan($' sdc: db ',$'
sdi:    db      ') = $' db '.....' numbuf: db '$'
sdnl:   db      13,10,'$' 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 ## Ada Translation of: Javascript 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 Translation of: Wren ...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 Translation of: 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  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

Translation of: 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

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

## BQN

_sudan←{
x 0 _𝕣 y: x + y;
x n _𝕣 0: x;
x n _𝕣 y: k (n-1)_𝕣 y+k←x𝕊y-1
}

•Show "⍉(↕7) 0 _sudan⌜ ↕6:"
•Show ⍉(↕7) 0 _sudan⌜ ↕6

•Show "⍉(↕7) 1 _sudan⌜ ↕6:"
•Show ⍉(↕7) 1 _sudan⌜ ↕6

•Show "1 2 _sudan 1: "∾•Fmt 1 2 _sudan 1
•Show "2 2 _sudan 1: "∾•Fmt 2 2 _sudan 1
•Show "1 3 _sudan 1: "∾•Fmt 1 3 _sudan 1
Output:
"⍉(↕7) 0 _sudan⌜ ↕6:"
┌─
╵ 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
┘
"⍉(↕7) 1 _sudan⌜ ↕6:"
┌─
╵  0  1   2   3   4   5   6
1  3   5   7   9  11  13
4  8  12  16  20  24  28
11 19  27  35  43  51  59
26 42  58  74  90 106 122
57 89 121 153 185 217 249
┘
"1 2 _sudan 1: 8"
"2 2 _sudan 1: 27"
"1 3 _sudan 1: 10228"

## C

Translation of: Javascript
//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++

Translation of: 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#

Translation of: 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


## CLU

sudan = proc (n, x, y: int) returns (int)
if n=0 then
return(x + y)
elseif y=0 then
return(x)
else
k: int := sudan(n, x, y-1)
return(sudan(n-1, k, k+y))
end
end sudan

table = proc (n, xs, ys: int) returns (string)
ss: stream := stream$create_output() stream$putl(ss, "sudan(" || int$unparse(n) || ",x,y):") stream$puts(ss, "     ")
for x: int in int$from_to(0, xs) do stream$putright(ss, int$unparse(x), 5) end for y: int in int$from_to(0, ys) do
stream$putl(ss, "") stream$putright(ss, int$unparse(y) || ":", 5) for x: int in int$from_to(0, xs)
do stream$putright(ss, int$unparse(sudan(n, x, y)), 5) end
end
stream$putl(ss, "") return(stream$get_contents(ss))
end table

show = proc (n, x, y: int) returns (string)
return("sudan(" || int$unparse(n) || ", " || int$unparse(x)
|| ", " || int$unparse(y) || ") = " || int$unparse(sudan(n,x,y)))
end show

start_up = proc ()
po: stream := stream$primary_output() stream$putl(po, table(0, 6, 5))
stream$putl(po, table(1, 6, 5)) stream$putl(po, show(1, 3, 3))
stream$putl(po, show(2, 1, 1)) stream$putl(po, show(2, 2, 1))
stream$putl(po, show(3, 1, 1)) end start_up 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 ## Draco proc sudan(word n, x, y) word: word k; if n=0 then x + y elif y=0 then x else k := sudan(n, x, y-1); sudan(n-1, k, k+y) fi corp proc table(word n, xs, ys) void: word x, y; writeln("sudan(",n,",x,y):"); write(" "); for x from 0 upto xs do write(x:5) od; for y from 0 upto ys do writeln(); write(y:4, ":"); for x from 0 upto xs do write(sudan(n,x,y):5) od; od; writeln(); writeln() corp proc show(word n, x, y) void: writeln("sudan(", n:1, ",", x:3, ",", y:3, ") = ", sudan(n,x,y):5) corp proc main() void: table(0, 6, 5); table(1, 6, 5); show(1, 3, 3); show(2, 1, 1); show(2, 2, 1); show(3, 1, 1) corp 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 ## F# Translation of: OCaml 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 Works with: Factor version 0.99 2022-04-03 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 Translation of: Wren and Phyton 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 Translation of: Wren 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 |
+---++---------------+

## J

Translation of: Javascript

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

Translation of: C
//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  ## MAD  NORMAL MODE IS INTEGER R WE HAVE TO DEFINE OUR OWN STACK FIRST DIMENSION STACK(1000) SET LIST TO STACK R SUDAN FUNCTION INTERNAL FUNCTION(N,X,Y) ENTRY TO SUDAN. R BASE CASES WHENEVER N.E.0, FUNCTION RETURN X+Y WHENEVER Y.E.0, FUNCTION RETURN X R RECURSIVE CASE - WITH MANUAL STACK MANIPULATION R NOTE WE DON'T NEED X AFTER THE FIRST CALL SAVE RETURN SAVE DATA N,Y K = SUDAN.(N,X,Y-1) RESTORE DATA N,Y RESTORE RETURN SAVE RETURN K = SUDAN.(N-1, K, K+Y) RESTORE RETURN FUNCTION RETURN K END OF FUNCTION INTERNAL FUNCTION(N,X,Y) ENTRY TO SHOW. VECTOR VALUES FMT =$7HSUDAN.(,I1,1H,,I1,1H,,I1,4H) = ,I8*$PRINT FORMAT FMT,N,X,Y,SUDAN.(N,X,Y) END OF FUNCTION SHOW.(1,3,3) SHOW.(2,1,1) SHOW.(2,2,1) SHOW.(3,1,1) END OF PROGRAM Output: SUDAN.(1,3,3) = 35 SUDAN.(2,1,1) = 8 SUDAN.(2,2,1) = 27 SUDAN.(3,1,1) = 10228 ## Modula-2 MODULE Sudan; FROM InOut IMPORT WriteCard, WriteString, WriteLn; PROCEDURE sudan(n, x, y: CARDINAL): CARDINAL; VAR k: CARDINAL; BEGIN IF n = 0 THEN RETURN x+y ELSIF y = 0 THEN RETURN x ELSE k := sudan(n, x, y-1); RETURN sudan(n-1, k, k+y) END END sudan; PROCEDURE Show(n, x, y: CARDINAL); BEGIN WriteString("sudan("); WriteCard(n, 0); WriteString(", "); WriteCard(x, 0); WriteString(", "); WriteCard(y, 0); WriteString(") = "); WriteCard(sudan(n,x,y), 0); WriteLn END Show; BEGIN Show(0, 0, 0); Show(1, 1, 1); Show(2, 1, 1); Show(3, 1, 1); Show(2, 2, 1) END 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 ## 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 Translation of: C #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 Translation of: Javascript # 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 Translation of: C #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:
F0 (x,y)
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
F1 (x,y)
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


## Swift

Translation of: C

I have started working on Swift and am going to practice on RosettaCode. On converting my C implementation for this task to Swift which I contributed last year, I found Swift allows statement ending semicolons and enclosing parantheses in if/else statements which are mandatory in C. I didn't find that anywhere while learning Swift so I am posting both implementations here, the "C like" and the "Pure" Swift.

Both have been tested with Xcode 14.2 (14C18)

### C like

//Aamrun, 3rd February 2023

func F(n: Int,x: Int,y: Int) -> Int {
if (n == 0) {
return x + y;
}

else if (y == 0) {
return x;
}

return F(n: n - 1, x: F(n: n, x: x, y: y - 1), y: F(n: n, x: x, y: y - 1) + y);
}

print("F1(3,3) = " + String(F(n: 1,x: 3,y: 3)));


### Pure Swift

//Aamrun, 3rd February 2023

func F(n: Int,x: Int,y: Int) -> Int {
if n == 0 {
return x + y
}

else if y == 0 {
return x
}

return F(n: n - 1, x: F(n: n, x: x, y: y - 1), y: F(n: n, x: x, y: y - 1) + y)
}

print("F1(3,3) = " + String(F(n: 1,x: 3,y: 3)))


Output is the same for both

Output:
F1(3,3) = 35


## V (Vlang)

Translation of: Wren
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

Library: Wren-fmt
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

Translation of: Wren
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