Previous Section
 < Free Open Study > 
Next Section


7.3 Programming Recursively

Of course, the use of recursion is not limited to mathematicians with telephones. Computer languages such as C++ that support recursion give the programmer a powerful tool for solving certain kinds of problems by reducing the complexity or hiding the details of the problem.

In this chapter, we consider recursive solutions to several simple problems. In our initial discussion, you may wonder why a recursive solution would ever be preferred to an iterative, or nonrecursive, one because the iterative solution may seem simpler and more efficient. Don't worry. As you will see later, in some situations the use of recursion produces a much simpler-and more elegant-program.

Coding the Factorial Function

As noted earlier, a recursive function is one that calls itself. In the previous section, Sue Ann, Max, Max's mom, and Bernie all had the same formula for solving the factorial function. When we construct a recursive C++ function Factorial for solving n!, we know where we can get the value of (n - 1)! that we need in the formula. We already have a function for doing this calculation: Factorial. Of course, the actual parameter (number - 1) in the recursive call is different than the parameter in the original call (number). (The recursive call is the one within the function.) As we see, this difference is an important and necessary consideration.

int Factorial(int number)
// Pre:  number is nonnegative.
// Post: Function value = factorial of number.
{
  if (number == 0)                        // Line 1
    return 1;                             // Line 2
  else
    return number * Factorial(number-1);  // Line 3
}

Notice the use of Factorial in line 3. Factorial involves a recursive call to the function, with the parameter number - 1.

Let's walk through the calculation of 4! using the function Factorial. The original value of number is 4. Table 7.1 shows the steps in the calculation.

Table 7.1: Walk-through of Factorial(4)

Recursive Call

Line

Action

 

1

4 is not 0, so skip to else clause.

 

3

return number * Factorial (4 2 1)

First recursive call returns us to the beginning of the function with number = 3.

1

1

3 is not 0, so skip to else clause.

 

3

return number * Factorial (3 - 1)

Second recursive call returns us to the beginning of the function with number = 2.

2

1

2 is not 0, so skip to else clause.

 

3

return number * Factorial (2 - 1)

Third recursive call returns us to the beginning of the function with number = 1.

3

1

1 is not 0, so skip to else clause.

 

3

return number * Factorial(1 - 1)

Fourth recursive call returns us to the beginning of the function with number = 0.

4

1

0 is 0, so go to line 2.

 

2

return 1

3

3

1 replaces call to Factorial; number is 1.

   

return 1

2

3

1 replaces call to Factorial; number is 2.

   

return 2

1

3

2 replaces call to Factorial; number is 3.

   

return 6

 

3

6 replaces call to Factorial; number is 4.

   

return 24

For purposes of comparison, let's look at the recursive and iterative solutions to this problem side by side:

int Factorial(int number)
{
  if (number == 0)
    return 1;
  else
    return number *
      Factorial(number - 1);
}

int Factorial(int number)
{
  int fact = 1;

  for (int count = 2;
    count <= number; count++)
    fact = fact * count;
  return fact;
}

These two versions of Factorial illustrate some of the differences between recursive and iterative functions. First, an iterative algorithm uses a looping construct such as the for loop (or while or do ... while loop) to control the execution. In contrast, the recursive solution uses a branching structure (if or switch statement). The iterative version needs a couple of local variables, whereas the recursive version uses the parameters of the function to provide all its information. Sometimes, as we will see later, the recursive solution needs more parameters than the equivalent iterative one. Data values used in the iterative solution are usually initialized inside the routine, above the loop. Similar data values used in a recursive solution are typically initialized by the choice of parameter values in the initial call to the routine.

Let's summarize the vocabulary of recursive solutions. A recursive definition is a definition in which something is defined in terms of smaller versions of itself. The definition of the factorial function certainly fits this description. A recursive call is a call made to the function from within the function itself. Line 3 in the function Factorial is an example of a recursive call.

In a recursive algorithm there is always at least one case for which the answer is known; the solution is not stated in terms of smaller versions of itself. In the case of the factorial, the answer is known if the number is 0. The case for which the answer is known is called the base case. The case that is stated recursively is the general or recursive case.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)