Mastering Algorithms with C

Basic Recursion

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