6.20 Recursion vs. Iteration

In the two prior sections, we studied two recursive functions that can also be implemented with simple iterative programs. This section compares the two approaches and discusses why you might choose one approach over the other in a particular situation.

  • Both iteration and recursion are based on a control statement: Iteration uses a iteration statement; recursion uses a selection statement.

  • Both iteration and recursion involve iteration: Iteration explicitly uses an iteration statement; recursion achieves iteration through repeated function calls.

  • Iteration and recursion each involve a termination test: Iteration terminates when the loop-continuation condition fails; recursion terminates when a base case is recognized.

  • Counter-controlled iteration and recursion each gradually approach termination: Iteration modifies a counter until the counter assumes a value that makes the loopcontinuation condition fail; recursion produces simpler versions of the original problem until the base case is reached.

  • Both iteration and recursion can occur infinitely: An infinite loop occurs with iteration if the loop-continuation test never becomes false; infinite recursion occurs if the recursion step does not reduce the problem during each recursive call in a manner that converges on the base case.

Iterative Factorial Implementation

To illustrate the differences between iteration and recursion, let’s examine an iterative solution to the factorial problem (Fig. 6.28). An iteration statement is used (lines 22–24 of Fig. 6.28) rather than the selection statement of the recursive solution (lines 19–24 of Fig. 6.25). Both solutions use a termination test. In the recursive solution, line 19 (Fig. 6.25) tests for the base case. In the iterative solution, line 22 (Fig. 6.28) tests the loop-continuation condition—if the test fails, the loop terminates. Finally, instead of producing simpler versions of the original problem, the iterative solution uses a counter that is modified until the loop-continuation condition becomes false.

Fig. 6.28 Iterative function factorial.

Alternate View 

 1   // Fig. 6.28: fig06_28.cpp
 2   // Iterative function factorial.
 3   #include <iostream>
 4   #include <iomanip>
 5   using namespace std;
 6
 7   unsigned long factorial(unsigned int); // function prototype
 8
 9   int main() {
10      // calculate the factorials of 0 through 10
11      for (unsigned int counter{0}; counter <= 10; ++counter) {
12         cout << setw(2) << counter << "! = " << factorial(counter)
13            << endl;
14      }
15   }
16
17   // iterative function factorial
18   unsigned long factorial(unsigned int number) {
19      unsigned long result{1};
20
21      // iterative factorial calculation
22      for (unsigned int i{number}; i >= 1; --i) {
23         result *= i;                            
24      }                                          
25
26      return result;
27   }


 
 0! = 1
 1! = 1
 2! = 2
 3! = 6
 4! = 24
 5! = 120
 6! = 720
 7! = 5040
 8! = 40320
 9! = 362880
10! = 3628800

Negatives of Recursion

Recursion has negatives. It repeatedly invokes the mechanism, and consequently the overhead, of function calls. This can be expensive in both processor time and memory space. Each recursive call causes another copy of the function variables to be created; this can consume considerable memory. Iteration normally occurs within a function, so the overhead of repeated function calls and extra memory assignment is omitted. So why choose recursion? Software Engineering Observation 6.11 disusses two reasons.

Software Engineering Observation 6.11

Any problem that can be solved recursively can also be solved iteratively (nonrecursively). A recursive approach is normally chosen when the recursive approach more naturally mirrors the problem and results in a program that’s easier to understand and debug. Another reason to choose a recursive solution is that an iterative solution may not be apparent when a recursive solution is.

 

Performance Tip 6.6

Avoid using recursion in performance situations. Recursive calls take time and consume additional memory.

 

Common Programming Error 6.14

Accidentally having a nonrecursive function call itself, either directly or indirectly (through another function), is a logic error.

Summary of Recursion Examples and Exercises in This Book

Figure 6.29 summarizes the recursion examples and exercises in the text.

Fig. 6.29 Summary of recursion examples and exercises in the text.

Location in text Recursion examples and exercises
Chapter 6  
Section 6.18, Fig. 6.25 Factorial function
Section 6.19, Fig. 6.26 Fibonacci function
Exercise 6.36 Recursive exponentiation
Exercise 6.38 Towers of Hanoi
Exercise 6.40 Visualizing recursion
Exercise 6.41 Greatest common divisor
Exercise 6.43, Exercise 6.44 “What does this program do?” exercise
Chapter 7  
Exercise 7.17 “What does this program do?” exercise
Exercise 7.20 “What does this program do?” exercise
Exercise 7.28 Determine whether a string is a palindrome
Exercise 7.29 Eight Queens
Exercise 7.30 Print an array
Exercise 7.31 Print a string backward
Exercise 7.32 Minimum value in an array
Exercise 7.33 Maze traversal
Exercise 7.34 Generating mazes randomly
Chapter 19  
Section 19.6, Figs. 19.20–19.22 Binary tree insert
Section 19.6, Figs. 19.20–19.22 Preorder traversal of a binary tree
Section 19.6, Figs. 19.20–19.22 Inorder traversal of a binary tree
Section 19.6, Figs. 19.20–19.22 Postorder traversal of a binary tree
Exercise 19.20 Print a linked list backward
Exercise 19.21 Search a linked list
Exercise 19.22 Binary tree search
Exercise 19.23 Level order traversal of a binary tree
Exercise 19.24 Printing tree
Chapter 20  
Section 20.3.3, Fig. 20.6 Mergesort
Exercise 20.8 Linear search
Exercise 20.9 Binary search
Exercise 20.10 Quicksort
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset