Java Reference
In-Depth Information
reached (i.e., we cannot take any more steps forward without hitting a wall), we back up
to the previous location and try to go in a different direction. If no other direction can be
taken, we back up again. This process continues until we find a point in the maze where
a move
can
be made in another direction. Once such a location is found, we move in the
new direction and continue with another recursive call to solve the rest of the maze.
To back up to the previous location in the maze, our recursive method simply returns
false, moving up the method-call chain to the previous recursive call (which references the
previous location in the maze). Using recursion to return to an earlier decision point is
known as
recursive backtracking
. If one set of recursive calls does not result in a solution
to the problem, the program
backs up
to the previous decision point and makes a different
decision, often resulting in another set of recursive calls. In this example, the previous deci-
sion point is the previous location in the maze, and the decision to be made is the direction
that the next move should take. One direction has led to a
dead end
, so the search con-
tinues with a
different
direction. The recursive backtracking solution to the maze problem
uses recursion to return only
partway
up the method-call chain, then try a different direc-
tion. If the backtracking reaches the entry location of the maze and the paths in all direc-
tions have been attempted, the maze does not have a solution.
The exercises ask you to implement recursive backtracking solutions to the maze
problem (Exercises 18.20-18.22) and the Eight Queens problem (Exercise 18.15), which
attempts to find a way to place eight queens on an empty chessboard so that no queen is
“attacking” any other (i.e., no two queens are in the same row, in the same column or
along the same diagonal).
In this chapter, you learned how to create recursive methods—i.e., methods that call
themselves. You learned that recursive methods typically divide a problem into two con-
ceptual pieces—a piece that the method knows how to do (the base case) and a piece that
the method does not know how to do (the recursion step). The recursion step is a slightly
smaller version of the original problem and is performed by a recursive method call. You
saw some popular recursion examples, including calculating factorials and producing val-
ues in the Fibonacci series. You then learned how recursion works “under the hood,” in-
cluding the order in which recursive method calls are pushed on or popped off the
program-execution stack. Next, you compared recursive and iterative approaches. You
learned how to use recursion to solve more complex problems—the Towers of Hanoi and
displaying fractals. The chapter concluded with an introduction to recursive backtracking,
a technique for solving problems that involves backing up through recursive calls to try
different possible solutions. In the next chapter, you'll learn numerous techniques for sort-
ing lists of data and searching for an item in a list of data, and you'll explore the circum-
stances under which each searching and sorting technique should be used.
Summary
Section 18.1 Introduction
• A recursive method (p. 777) calls itself directly or indirectly through another method.
