2.7 Recursion

2.7.1 Example: Factorial

One of the simplest examples of a recursive definition is that for the factorial function:

Click here for Picture

A natural way to calculate factorials is to write a recursive function which matches this definition:

function fact( int n )
{
if ( n == 0 ) return 1;
else return n*fact(n-1);
}

Another commonly used (and abused!) example of a recursive function is the calculation of Fibonacci numbers. Following the definition:

Click here for Picture

one can write:

function fib( int n )
{
if ( n <= 1 ) return 1;
else return fib(n-1) + fib(n-2);
}

Short and elegant, it uses recursion neatly to provide a neat solution - but actually a disaster! We shall re-visit this and show why it is such a disaster later.

Data structures also may be recursively defined. One of the most important class of structure - trees - allows recursive definitions which lead to simple (and efficient) recursive functions for manipulating them.

But in order to see why trees are valuable structures, let's first examine the problem of searching.

Searching
Table of Contents


@ John Morris, 1996