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

Start Free Trial

No credit card required