Recursion - Java Software Solutions: Foundations of Program Design - page 595

some of the adjacent positions may be invalid, may be blocked, or may represent
a possible successful path. We continue this process recursively. If the base case,
position (7, 12) is reached, the maze has been traversed successfully.
The recursive method in the Maze class is called traverse . It returns a boolean
value that indicates whether a solution was found. First the method determines
whether a move to the specified row and column is valid. A move is considered
valid if it stays within the grid boundaries and if the grid contains a 1 in that
location, indicating that a move in that direction is not blocked. The initial call to
traverse passes in the upper-left location (0, 0).
If the move is valid, the grid entry is changed from a 1 to a 3, marking this
location as visited so that later we don't retrace our steps. The traverse method
then determines whether the maze has been completed by having reached the
bottom-right location. Therefore, there are actually three possibilities of the base
case for this problem that will terminate any particular recursive path:

an invalid move because the move is out of bounds

■

an invalid move because the move has been tried before ■

a move that arrives at the final location
If the current location is not the bottom-right corner, we search for a solution
in each of the primary directions, if necessary. First, we look down by recursively
calling the traverse method and passing in the new location. The logic of the
traverse method starts all over again using this new position. A solution is either
ultimately found by first attempting to move down from the current location,
or it's not found. If it's not found, we try moving right. If that fails, we try up.
Finally, if no other direction has yielded a correct path, we try left. If no direction
from the current location yields a correct solution, then there is no path from this
location, and traverse returns false.
If a solution is found from the current location, the grid entry is changed to
a 7. The first 7 is placed in the bottom-right corner. The next 7 is placed in the
location that led to the bottom-right corner, and so on until the final 7 is placed
in the upper-left corner. Therefore, when the final maze is printed, the zeros still
indicate a blocked path, a 1 indicates an open path that was never tried, a 3 indi-
cates a path that was tried but failed to yield a correct solution, and a 7 indicates
a part of the final solution of the maze.
Note that there are several opportunities for recursion in each call to the tra-
verse method. Any or all of them might be followed, depending on the maze
configuration. Although there may be many paths through the maze, the recur-
sion terminates when a path is found. Carefully trace the execution of this code
while following the maze array to see how the recursion solves the problem. Then
consider the difficulty of producing a non-recursive solution.

■