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

- if n is 0, the factorial of n is 1.
- 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.

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

You may also:

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

David A. Wheeler (dwheeler@dwheeler.com)

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