Sudan function

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

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

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>

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

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

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