Sudan function

From Rosetta Code
Task
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).

8080 Assembly[edit]

        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[edit]

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[edit]

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[edit]

 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[edit]

# 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[edit]

BASIC256[edit]

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[edit]

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[edit]

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[edit]

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[edit]

_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[edit]

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++[edit]

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#[edit]

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[edit]

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[edit]

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#[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

|=  [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[edit]

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[edit]

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[edit]

/**
 * @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[edit]

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[edit]

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[edit]

            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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

  [ 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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

//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[edit]

//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)[edit]

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[edit]

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[edit]

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