How to resolve the algorithm Sudan function step by step in the XPL0 programming language

Published on 12 May 2024 09:40 PM
#Xpl0

How to resolve the algorithm Sudan function step by step in the XPL0 programming language

Table of Contents

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:

Step by Step solution about How to resolve the algorithm Sudan function step by step in the XPL0 programming language

Source code in the xpl0 programming language

func F; int 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);
];
 
int N, X, Y;
[Format(4, 0);
for N:= 0 to 1 do
    [Text(0, "Values of F("); IntOut(0, N);  Text(0, ", X, Y):^m^j");
     Text(0, "Y/X    0   1   2   3   4   5^m^j");
     Text(0, "----------------------------^m^j");
     for Y:= 0 to 6 do
        [IntOut(0, Y);  Text(0, "  |");
        for X:= 0 to 5 do
            RlOut(0, float(F(N, X, Y)));
        CrLf(0);
        ];
    CrLf(0);
    ];
Text(0, "F(2, 1, 1) = ");  IntOut(0, F(2, 1, 1));  CrLf(0);
Text(0, "F(3, 1, 1) = ");  IntOut(0, F(3, 1, 1));  CrLf(0);
Text(0, "F(2, 2, 1) = ");  IntOut(0, F(2, 2, 1));  CrLf(0);
]

You may also check:How to resolve the algorithm Vigenère cipher/Cryptanalysis step by step in the Wren programming language
You may also check:How to resolve the algorithm Ackermann function step by step in the V (Vlang) programming language
You may also check:How to resolve the algorithm Factorial step by step in the Perl programming language
You may also check:How to resolve the algorithm Catalan numbers/Pascal's triangle step by step in the EasyLang programming language
You may also check:How to resolve the algorithm XML/DOM serialization step by step in the Pascal programming language