Data Structures and Algorithms

2.6 Recursion

Many examples of the use of recursion may be found: the technique is useful both for the definition of mathematical functions and for the definition of data structures. Naturally, if a data structure may be defined recursively, it may be processed by a recursive function!

2.6.1 Example: Factorial

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

factorial( n ) = if ( n = 0 ) then 1
                 else n * factorial( n-1 )

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:

fib( n ) = if ( n = 0 ) then 1
           if ( n = 1 ) then 1
           else fib( n-1 ) + fib( n-2 )

one can write:

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

Short and elegant, it uses recursion 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.

Next
Table of Contents

@ John Morris, 1996