Recursion (Advanced)

Recursion is a powerful programming technique. It is the ability of a routine to call itself. Recursion provides another approach to solving problems. Some things can be easily defined in a recursive way. For example, an ancestor is a person's father or mother or one of their ancestors. In programming, recursion is used for sorting, searching trees, parsing languages, and so on.

XPL0 is designed to facilitate recursive programming. Any procedure (or function) can call itself. A procedure can also call itself indirectly. For instance, a procedure P could call a second procedure Q that calls the original procedure P. Each time a procedure calls itself, the current set of local variables for the procedure is saved and a new set is created.

Here is an example using recursion to compute factorials:

        code IntOut=11;

                function Factorial(N);          \Returns N!

                integer N;

                begin

                if N = 0 then return 1          \(0! = 1)

                else return N * Factorial(N-1);

                end;

        begin   \Main

        IntOut(0, Factorial(7));

        end;

Seven factorial (7!) is 7*6*5*4*3*2*1, which is equal to 5040.