Lecture 16: Recursive programming

Recursive

A function or procedure is recursive if it is defined in terms of itself (i.e., it calls itself)

Example 1: Factorial

The classic example is the calculation of the factorial function n! We might do this with a loop, as described in lectures 11 and 12:
FUNCTION Factorial(n: integer): integer;
(* returns n! *)
var result: integer;
    i: integer;
begin
result := 1;        (* initialize the variable *)
for i := 1 to n do
    result := i*result;
Factorial := result; (* return result *)
end;
This function, indeed, will return the factorial of the argument, for instance Factorial(5) = 120. Check this.

A much more interesting solution is if we define the function Factorial in terms of itself, just as we have learned in school,

n! = n*(n-1)!

Let's do exactly that:
FUNCTION Factorial(n: integer): integer;
(* returns n! *)
begin
(* the value to be returned is expressed in terms of itself: *)
Factorial := n*Factorial(n-1);
end;

This function is already nearly correct. The only problem is that it will never stop calling itself. For instance, we can call it with Factorial(4), which will then try to calculate 4*Factorial(3) and hence call Factorial(3). Factorial(3) will try to calculate 3*Factorial(2), which will call Factorial(2), ... which will call Factorial(1) ... which will call Factorial(0) ... which will call Factorial(-1) ... which will call Factorial(-2) ... and this will never end. The program will never return anything and the computer will crash, probably generating a so-called "stack overflow" error. Clearly we have to build in a way to stop calling itself. Now remember that in the mathematical way of defining a function in terms of itself we also always had to build in a stop, for the Factorial function, this was

1! = 1

Let's also built this into our function:
FUNCTION Factorial(n: integer): integer;
(* returns n! *)
begin
if n=1 then
Factorial := 1
else
Factorial := n*Factorial(n-1);
end;

The idea we should learn from this is that we should give it a possibility to come up with an answer and exit the recursive calculation. Just like the way we had to give a loop the possibility to end we should also give this possibilty to recursive functions. If not, the program will continue forever (or crash).

Example 2: Fibonacci

Remember from the practical lessons, the definition of a Fibonacci number is in terms of itsef:
f_n = f_n_-2 + f_n_-1
with the stopping conditions
f₁ = 1
f₂ = 1
For instance,
f₃ = 1 + 1 = 2
f₄ = 1 + 2 = 3
f₅ = 2 + 3 = 5
f₆ = 3 + 5 = 8
f₇ = 5 + 8 = 13

We can implement this in a function, note the stopping condition:
FUNCTION Fibonacci(n: integer): integer;
begin
if (n=1) OR (n=2) then
Fibonacci := 1
else
Fibonacci := Fibonacci(n-2) + Fibonacci(n-1);
end;

Variables

Variables that are declared inside recursive procedures and functions are all local. Moreover, everytime the function is called, a new instance of the variable is created that exists until the procedure finishes. (in C we can prevent this with the word "static" in front of the variable declaration). Each of these variables, although they have the same name, will point to a different space in memory. As an example, let's create a local variable in our Factorial function:
FUNCTION Factorial(n: integer): integer;
Var m: integer;
begin
m := 2*n;
if n=1 then
Factorial := 1
else
Factorial := n*Factorial(n-1);
WriteLn(m);
end;
When we call this function with argument 3 the following will happen:

Factorial(3) is called
    a variable with name m is created
    2*3 is assigned to it
    Factorial(2) is called
      a variable with name m is created (different than m above!)
      2*2 is assigned to it
      Factorial(1) is called
        a variable with name m is created (different than the two above)
        2*1 is assined to it
        ... we reach the stop condition and Fortorial := 1;
        The value of m is writen: 2
      we exit Factorial(1)
      The value of m is written: 4
    we exit Factorial(2)
    The value of m is written: 6
We exit Factorial(3)

What we learn from this is that the variable m is not a static object in memory, pointing to a certain address, but instead, the variable is created at the time we run the program. Each time we enter the function, a new one is created that lives until we exit the function. Moreover, as can be seen in the example above, the last variable created is the one to be used locally.

Quick Test

To test your knowledge of what you have learned in this lesson, click here for an on-line test.

Peter Stallinga. Universidade do Algarve, 7 Abril 2002