Introduction

The programs we have discussed thus far are generally structured as methods that call one another in a disciplined, hierarchical manner. For some problems, however, it is useful to have a method call itself. Such a method is known as a recursive method. A recursive method can be called either directly, or indirectly through another method. Recursion is an important topic discussed at length in upper-level computer science courses. In this chapter, we consider recursion conceptually, then present several programs containing recursive methods. Figure 15.1 summarizes the recursion examples and exercises in the book.

Figure 15.1. Summary of the 32 recursion examples and exercises in this text.

(This item is displayed on page 746 in the print version)

Chapter	Recursion examples and exercises in this book
15	Factorial Method (Fig. 15.3 and Fig. 15.4) Fibonacci Method (Fig. 15.5 and Fig. 15.6) String Permutations (Fig. 15.12 and Fig. 15.13) Towers of Hanoi (Fig. 15.15 and Fig. 15.16) Fractals (Fig. 15.23 and Fig. 15.24) What Does This Code Do? (Exercise 15.7, Exercise 15.12 and Exercise 15.13) Find the Error in the Following Code (Exercise 15.8) Raising an Integer to an Integer Power (Exercise 15.9) Visualizing Recursion (Exercise 15.10) Greatest Common Divisor (Exercise 15.11) Determine Whether a String Is a Palindrome (Exercise 15.14) Eight Queens (Exercise 15.15) Print an Array (Exercise 15.16) Print an Array Backward (Exercise 15.17) Minimum Value in an Array (Exercise 15.18) Star Fractal (Exercise 15.19) Maze Traversal Using Recursive Backtracking (Exercise 15.20) Generating Mazes Randomly (Exercise 15.21) Mazes of Any Size (Exercise 15.22) Time Needed to Calculate a Fibonacci Number (Exercise 15.23)
16	Merge Sort (Fig. 16.10 and Fig. 16.11) Linear Search (Exercise 16.8) Binary Search (Exercise 16.9) Quicksort (Exercise 16.10)
17	Binary-Tree Insert (Fig. 17.17) Preorder Traversal of a Binary Tree (Fig. 17.17) Inorder Traversal of a Binary Tree (Fig. 17.17) Postorder Traversal of a Binary Tree (Fig. 17.17) Print a Linked List Backward (Exercise 17.20) Search a Linked List (Exercise 17.21)