Sudan function: Difference between revisions

Content added Content deleted

Inline

Revision as of 19:08, 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"

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