Data Structures and Algorithms 
3.4 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! 

factorial( n ) = if ( n = 0 ) then 1 else n * factorial( n1 )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(n1); }
Note how this function calls itself to evaluate the next term. Eventually it will reach the termination condition and exit. However, before it reaches the termination condition, it will have pushed n stack frames onto the program's runtime stack.
The termination condition is obviously extremely important when dealing with recursive functions. If it is omitted, then the function will continue to call itself until the program runs out of stack space  usually with moderately unpleasant results!
Another commonly used (and abused!) example of a recursive function is the calculation of Fibonacci numbers. Following the definition:Failure to include a correct termination condition in a recursive function is a recipe for disaster!
fib( n ) = if ( n = 0 ) then 1 if ( n = 1 ) then 1 else fib( n1 ) + fib( n2 )one can write:
function fib( int n ) { if ( (n == 0)  (n == 1) ) return 1; else return fib(n1) + fib(n2); }Short and elegant, it uses recursion to provide a neat solution  that is actually a disaster! We shall revisit 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.
Key terms 
Continue on to Searching  Back to the Table of Contents 