Recursion

Introduction

Webster's Dictionary defines the word recur to mean "to return in talk, thought, etc." or "to occur again or at intervals." This laboratory explores the use of a function whose definition "returns" to itself and the call of which "occurs again" and again: the recursive function.

Topics Covered in this Lab:
• definition of recursion
• relationship of recursion and iteration
• When is recursion appropriate?
• What is the cost of recursion?
• What is the benefit of recursion?
Demonstrable Skills Acquired in this Lab:
• ability to implement a recursive definition
• understanding of when to select recursion over iteration

A First Example: Factorials

Simply put, a recursive function is one which calls itself. The typical example presented when recursion is first encountered is the factorial function. The factorial of $n$ is defined in mathematics as the product of the integers from 1 to $n$. $n! = 1 \times 2 \times 3 \times \ldots \times (n-2) \times (n-1) \times n$

For example: $3!$ $=$ $1 \times 2 \times 3$ $4!$ $=$ $1 \times 2 \times 3 \times 4$ $5!$ $=$ $1 \times 2 \times 3 \times 4 \times 5$

Factorials are useful in counting ordered outcomes. For example, consider a race run by five people. Assuming no ties, there are five possibilities as to who will cross the finish line first; there are subsequently four remaining possibilities for second place, three for third, two for second and finally only one possibility for last place. The total number of possible outcomes for the race is $5 \times 4 \times 3 \times 2 \times 1$, or $5!$.

An Iterative Factorial Function

It is easy enough to write a function which uses a counting loop to multiply successive numbers together in order to obtain a factorial. Start a program in file spRecursionT.cpp with the function iterativeFactorial, which accepts a value parameter n and returns an integer; note how the work of the function is done by its loop. Code Illustration
int iterativeFactorial (int n)
{
int product = 1;
for (int i = 2; i <= n; i++)
product = product * i;
return product;
}

Write function main to contain the following. Code Illustration
int n;
cout << "Enter a number for which to find a factorial: ";
cin >> n;
cout << endl << n << "! iteratively = "
<< iterativeFactorial (n) << endl << endl;

Add a prototype for iterativeFactorial and execute the program using 5 as input; the result displayed should be 120.

Increase the input value slowly and experiment to determine the largest number for which a factorial can be calculated; it is smaller than one might first think. Add this value to the output instructions in function main. Code Illustration
cout << "Enter a number for which to find a factorial (max is ___): ";

What is the significance of this number?

A Recursive Factorial Function

Any iterative function can be implemented recursively and vice versa. The recursive function will always be slower due to the added overhead needed by function calls, but it is often times easier to state the solution of a problem recursively. The factorial function can be defined recursively by the following. $5!$ $=$ $5 \times 4 \times 3 \times 2 \times 1$ $4!$ $=$ $4 \times 3 \times 2 \times 1$ $5!$ $=$ $5 \times 4!$ $n!$ $=$ $n \times (n-1)!$

As is the case for every recursive definition, there must be some stopping point at which the function will no longer call itself. For factorial, this point is when zero is reached; by definition, $0! = 1$. This definition can be interpreted using the earlier race analogy to mean that there is only one way for a race with zero participants to end. The full recursive definition for factorial follows. $n! = \left\{ \begin{array}{ccl} 1 & {\rm if} & n = 0 \\ n \times (n-1)! & {\rm if} & n > 0 \end{array} \right.$

Add the function recursiveFactorial, which implements this definition, to the program. Code Illustration
int recursiveFactorial (int n)
{
int result;
if (n == 0)
result = 1;
else // n != 0
result = n * recursiveFactorial (n-1);
return result;
}

Add a prototype for recursiveFactorial and add the following line to function main.

cout << endl << n << "! recursively = "
<< recursiveFactorial (n) << endl;

Test the program to see that the same results are returned by both functions for a number of trials. Note that both functions have the same upper limit for a valid result, as one might expect.

Add the following statements as the first and penultimate lines of function recursiveFactorial. Code Illustration
cout << "entering recursiveFactorial with n = " << n << endl; // first

cout << "exiting recursiveFactorial with n = " << n           // next to last
<< " and result = " << result << endl;

Examine the sequence of "entering" and "exiting" messages which are collected; below is the sequence obtained for an input value of five. Example of expected output.
Enter a number for which to find a factorial: 5
5! iteratively = 120

entering recursiveFactorial with n = 5
entering recursiveFactorial with n = 4
entering recursiveFactorial with n = 3
entering recursiveFactorial with n = 2
entering recursiveFactorial with n = 1
entering recursiveFactorial with n = 0
exiting recursiveFactorial with n = 0 and result = 1
exiting recursiveFactorial with n = 1 and result = 1
exiting recursiveFactorial with n = 2 and result = 2
exiting recursiveFactorial with n = 3 and result = 6
exiting recursiveFactorial with n = 4 and result = 24
exiting recursiveFactorial with n = 5 and result = 120

5! recursively = 120

Note how the function is entered repeatedly without exiting until the function is entered when n is zero.

Exponential Growth in Recursion: The Fibonacci Numbers

Leonardo Pisano, an Italian mathematician born in 1170, published his book Liber abaci in 1202. In the third section of this book, the following problem was posed.

A certain man put a pair of rabbits in a place surrounded on all sides by a wall. How many pairs of rabbits can be produced from that pair in a year if it is supposed that every month each pair begets a new pair which from the second month on becomes productive?
Said another way, the question asks for the number of pairs of rabbits $n$ months after a single pair begins breeding (and newly born bunnies are assumed to begin breeding when they are two months old). When the initial pair of rabbits is put in place, there is of course one pair. After one month, there is still just the first pair in place. After two months, the initial pair of rabbits has produced a second pair (and will continue to do so every month from that time forward). After three months, these two pairs will be joined by a third pair produced by the original rabbits. After four months, these three pairs will be joined by two more pairs, one descending from the original rabbits, and one from the firstborn pair that is now two months old. After five months, these five pairs will be joined by another pair for each of the pairs alive at three months. Herein lies the pattern: after $n$ months, the rabbit pairs alive one month ago are joined by a new pair produced by each pair alive two months ago. The resulting sequence is 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, .... These numbers are known by Leonardo's nickname Fibonacci. The sequence is conventionally defined as follows: $Fib_{n} = \left\{ \begin{array}{cl} 1 & {\rm if} \, n = 0 \\ 1 & {\rm if} \, n = 1 \\ Fib_{n-1} + Fib_{n-2} & {\rm if} \, n > 1 \end{array} \right.$

A Recursive Fibonacci Function

In this case, as with many functions of a recursive nature, the mathematical definition can be easily transformed into program code. Code Illustration
int recursiveFibonacci (int n)
{
int result;
if (n == 0)
result = 1;
else if (n == 1)
result = 1;
else // n >= 2
result = recursiveFibonacci (n-1) + recursiveFibonacci (n-2);
return result;
}

There are several things worthy of note concerning a function like this, the most significant of which is that the function calls itself not once, but twice. This translates into serious problem with respect to computation time. In order for the computer to determine the tenth Fibonacci number, it must first determine the ninth and the eighth. The ninth in turn will require the eighth and the seventh, but this "eighth" is not the same function call as the earlier eighth. Both eighths require the seventh and the sixth, each of which are done separately as well. The result of this behavior is an enormous amount of unnecessary repetition; this cost is offset for small $n$ by the ease with which the function can be written.

In order to see how serious the repetitious calls are in the Fibonacci function, add the following lines to the beginning of the function above. Code Illustration
static int calls = 0;
cout << "recursiveFibonacci(" << n
<< "); Fibonacci function call #" << ++calls << endl;

When memory is declared to be static, it will be allocated and initialized only once, when the program begins execution, and it will remain allocated, regardless of where it is defined, until the program ends execution. Such a declaration is well-suited to counting the number of invocations of a function. Execute the program with the lines above and use a spreadsheet to plot the graph of the Fibonacci numbers and the associated number of function calls against $n$.

Use the graph to predict the number of invocations for the number following the last one graphed and explain the conclusion reached.

An Iterative Fibonacci Function

In order to reduce the execution time for Fibonacci numbers, an iterative algorithm can be developed. The iterative factorial-for- $n$ algorithm provides a good starting point. Time permitting, develop this algorithm and execute it with an extension to function main.