Section 17.2 - Recursion

The standard example of recursion is computing the factorial of an Integer. A factorial of some number n is defined as follows:

1. if n is 0, the factorial of n is 1.
2. if n is more than 0, the factorial of n is equal to n times the factorial of n-1.

Recursive subprograms are written in a relatively standard format: first, check for the "stopping" criteria of the recursion. If the "stopping" criteria is not met, do part of the work and then call "yourself" to complete the task.

Here's the factorial program:

function Factorial(A : in Integer) return Integer is
begin
 if A < 0 then                -- Stop recursion if A <= 0.
   raise Constraint_Error;
 elsif A = 0 then
    return 1;
 else
   return A * Factorial(A - 1);   -- recurse.
 end if;
end Sum;

Actually, you can implement the factorial using a "for" loop much more easily, but more complicated problems are sometimes easier to handle using recursion.

Quiz:

If you evaluated Factorial(5), how many times would the subprogram Factorial be called?

1. Once.
2. Four times.
3. Five times.
4. Six times.

Go back to the previous section	Skip to the next section	Go up to lesson 17 outline

The master copy of this file is at "http://www.adahome.com/Tutorials/Lovelace/s17s2.htm".