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:

function F (n, x, y)
    if n == 0 then
        return x + y
    elseif y == 0 then
        return x
    else
        return F(n - 1, F(n, x, y - 1), F(n, x, y - 1) + y)
    end
end

local testCases = {
    {0, 0, 0},
    {1, 1, 1},
    {1, 3, 3},
    {2, 1, 1},
    {2, 2, 1},
    {3, 1, 1}
}

for _, v in pairs(testCases) do
    io.write("F(" .. table.concat(v, ",") .. ") = ")
    print(F(unpack(v)))
end