Problem Statement

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

F

0

( x , y )

= x + y

F

n + 1

( x , 0 )

= x

if

n ≥ 0

F

n + 1

( x , y + 1 )

=

F

n

(

F

n + 1

( x , y ) ,

F

n + 1

( x , y ) + y + 1 )

if

n ≥ 0

{\displaystyle {\begin{array}{lll}F_{0}(x,y)&=x+y\F_{n+1}(x,0)&=x&{\text{if }}n\geq 0\F_{n+1}(x,y+1)&=F_{n}(F_{n+1}(x,y),F_{n+1}(x,y)+y+1)&{\text{if }}n\geq 0\\end{array}}}

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

Let's start with the solution:

 sudan←{
    0∨.>⍺ ⍺⍺ ⍵:'Negative input'⎕SIGNAL 11
    ⍺⍺=0:⍺+⍵
    ⍵=0:⍺
    tm((⍺⍺-1)∇∇)⍵+tm←⍺∇⍵-1
 }