Mastering Algorithms With C - Kyle Loudon [17]
To begin, let's consider a simple problem that normally we might not think of in a recursive way. Suppose we would like to compute the factorial of a number n. The factorial of n, written n!, is the product of all numbers from n down to 1. For example, 4! = (4)(3)(2)(1). One way to calculate this is to loop through each number and multiply it with the product of all preceding numbers. This is an iterative approach, which can be defined more formally as:
n! = (n)(n - 1)(n - 2) . . . (1)
Another way to look at this problem is to define n! as the product of smaller factorials. To do this, we define n! as n times the factorial of n - 1. Of course, solving (n - 1)! is the same problem as n!, only a little smaller. If we then think of (n - 1)! as n - 1 times (n - 2)!, (n - 2)! as n - 2 times (n - 3)!, and so forth until n = 1, we end up computing n!. This is a recursive approach, which can be defined more formally as:
Figure 3.1 illustrates computing 4! using the recursive approach just described. It also delineates the two basic phases of a recursive process: winding and unwinding . In the winding phase, each recursive call perpetuates the recursion by making an additional recursive call itself. The winding phase terminates when one of the calls reaches a terminating condition. A terminating condition defines the state at which a recursive function should return instead of making another recursive call. For example, in computing the factorial of n, the terminating conditions are n = 1 and n = 0, for which the function simply returns 1. Every recursive function must have at least one terminating condition; otherwise, the winding phase never terminates. Once the winding phase is complete, the process enters the unwinding phase, in which previous instances of the function are revisited in reverse order. This phase continues until the original call returns, at which point the recursive process is complete.
Figure 3.1. Computing 4! recursively
Example 3.1 presents a C function, fact, that accepts a number n and computes its factorial recursively. The function works as follows. If n is less than 0, the function returns 0, indicating an error. If n is or 1, the function returns 1 because 0! and 1! are both defined as 1. These are the terminating conditions. Otherwise, the function returns the result of n times the factorial of n - 1. The factorial of n - 1 is computed recursively by calling fact again, and so forth. Notice the similarities between this implementation and the recursive definition shown earlier.
Example 3.1. Implementation of a Function for Computing Factorials Recursively
/*****************************************************************************
* *
* -------------------------------- fact.c -------------------------------- *
* *
*****************************************************************************/
#include "fact.h"
/*****************************************************************************
* *
* --------------------------------- fact --------------------------------- *
* *
*****************************************************************************/
int fact(int n) {
/*****************************************************************************
* *
* Compute a factorial recursively. *
* *
*****************************************************************************/
if (n < 0)
return 0;
else if (n == 0)
return 1;
else if (n == 1)
return 1;
else
return n * fact(n - 1);
}
To understand how recursion really works, it helps to look at the way functions are executed in C. For this, we need to understand a little about the organization of a C program in memory. Fundamentally, a C program consists of four areas as it executes: a code area, a static data area, a heap, and a stack (see Figure 3.2a). The code area contains the machine instructions that are executed as the program runs. The static data area contains data that persists throughout the life of the program, such as global variables and static local variables. The heap contains dynamically allocated