Developing the Recursive Solution

1. In developing a recursive solution, consider the base cases first. What situation(s) cause the recursive method to exit?

   • We have arrived at a location that is off the data structure. It is important to catch this situation first to avoid an array indexing error.
   • Encountering a '*' character means that we have run into a wall. The algorithm should stop.
   • Encountering a location we have already visited should cause the algorithm to stop.
     
     • Arriving at a location that has a row or column value equal to 1 or MAXROW or MAXCOL means that we have found an exit point.

2. The general case of encountering a blank space requires the following steps:

   • Change the character value from the blank space to the '!' character.
   • Check to see if you are at an exit point. If so, print the maze with a trail of '!' markers to the exit point.
   • If you are not at an exit point, make 4 recursive calls to check all 4 directions, feeding the new coordinates of the 4 neighboring cells.

3. When an exit point is found, print only the successful trail of '!' marks that leads to an exit. As a result, it is necessary for each recursive call to work with a copy of the array. Why is this? If a reference to the original array is passed with each recursive call, the placement of '!' marks would be permanent in the data structure.