Sudan function: Difference between revisions

Content added Content deleted

Inline

Revision as of 19:13, 12 July 2022

The Sudan function is a classic example of a recursive function, notable especially because it is not a primitive recursive function. This is also true of the better-known Ackermann function. The Sudan function was the first function having this property to be published.

The Sudan function is usually defined as follows (svg):

  <big>
    :<math>\begin{array}{lll}
      F_0 (x, y) & = x+y \\
      F_{n+1} (x, 0) & = x & \text{if } n \ge 0 \\
      F_{n+1} (x, y+1) & = F_n (F_{n+1} (x, y), F_{n+1} (x, y) + y + 1) & \text{if } n\ge 0 \\
      \end{array}
    </math>
  </big>

Task

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

Ada

Translation of: Javascript

<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

Translation of: Wren

...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

Translation of: FreeBASIC

<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

Translation of: FreeBASIC

<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

Translation of: Javascript

<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++

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

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

Translation of: Wren and Phyton

<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

Translation of: Wren

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

$(n (dec n), x $(n n, x x, y (dec y)), y (add $(n n, x x, y (dec y)) y)) </lang>

J

Translation of: Javascript

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

Translation of: C

<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

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); ?> </lang> 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)) </lang>

Output

F(1,3,3) =  35

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))) </lang> Output

[1] "F(1,3,3) =  35"

Raku

Outputting wiki-tables to more closely emulate the wikipedia examples. Not very efficient but good enough. <lang perl6>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\_$f\ (x,y)\n" ~ '!x\y!!', join '!!', @range;
   -> $r { say "|-\n" ~ '|' ~ join '||', $r, @range.map:{ F($f, $r, $_) } } for @range;
   say( "|}" );

} </lang>

Output:

F₀ (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

F₁ (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

<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

Translation of: Wren

<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

Library: Wren-fmt

<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

@@ Line 570: / Line 570: @@
 [1] "F(1,3,3) =  35"
 </pre>
+=={{header|Raku}}==
+Outputting wiki-tables to more closely emulate the wikipedia examples. Not very efficient but good enough.
+<lang perl6>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( "|}" );
+}
+</lang>
+{{out}}
+{|class="wikitable"
+|+ F<sub>0</sub> (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
+|}
+{|class="wikitable"
+|+ F<sub>1</sub> (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
+|}
 =={{header|Ruby}}==
@@ Line 586: / Line 652: @@
 > 35
 </pre>
 =={{header|Vlang}}==