|
|
|
|
|
|
|
Figure 19-3
Execution of Factorial(4) |
|
|
|
|
|
|
|
|
summarizes the execution of the Factorial function with an actual parameter of 4. |
|
|
|
|
|
|
|
|
Let's organize what we have done in these two solutions into an outline for writing recursive algorithms. |
|
|
|
|
|
|
|
|
1. Understand the problem. (We threw this in for good measure; it is always the first step.) |
|
|
|
|
|
|
|
|
2. Determine the base case(s). |
|
|
|
|
|
|
|
|
3. Determine the recursive case(s). |
|
|
|
|
|
|
|
|
We have used the factorial and the power algorithms to demonstrate recursion because they are easy to visualize. In practice, one would never want to calculate either of these functions using the recursive solution. In both cases, the iterative solutions are simpler and much more efficient because starting a new iteration of a loop is a faster operation than calling a function. Let's compare the code for the iterative and recursive versions of the factorial problem. |
|
|
|
|
|
|
|
|
int Factorial ( /* in */ int n )
{
int factor;
int count;
factor = 1;
for (count = 2; count <= n; count++)
factor = factor * count;
return factor;
} |
|
|
|
|
|
