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:
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.
