Return function returning to main instead of caller

Question

just wondering...

void mazeTraversal(char maze[12][12], int x, int y)
{
if (maze[x + 1][y] == '.')
    mazeTraversal(maze, ++x, y);
if (maze[x][y + 1] == '.')
    mazeTraversal(maze, x, ++y);
if (maze[x - 1][y] == '.')
    mazeTraversal(maze, --x, y);
if (maze[x][y - 1] == '.')
    mazeTraversal(maze, x, --y);
   return;
}

when i hit a dead end, should i revert to the previous instance of the call, instead of going straight back to the main function? If I have something wrong please tell me.

Answer 1

The following addresses using a return value to capture "correct path" information as well as providing a base case condition. However, another crucial problem with the original code is the use of ++/-- which cause side effects upon the respective variables. The code below eschews these operators for that reason.

---

The primary way to do this is to return a value - say, true if this path led to and end or false otherwise.

A very primitive conversion would then look like the following. Note the addition of the base case - this means that we can stop recursing. True is returned so that previous caller(s) also know they can stop looking and the function stack will quickly be unwound back to "main".

bool mazeTraversal(char maze[12][12], int x, int y) {
  // This is the BASE CASE and means WE ARE DONE LOOKING
  if (maze[x][y] == 'X') return true; // found end!

  if (maze[x + 1][y] == '.')
    if (mazeTraversal(maze, x + 1, y)) return true;

  if (maze[x][y + 1] == '.')
     if (mazeTraversal(maze, x, y + 1)) return true;

  if (maze[x - 1][y] == '.')
     if (mazeTraversal(maze, x - 1, y)) return true;

  if (maze[x][y - 1] == '.')
     if (mazeTraversal(maze, x, y - 1)) return true;

  return false; // didn't find any valid path from here
}

Note that I removed ++/-- to avoid strange side-effects.

However, we can do better and clean up the code some. The crucial difference is each recursive calls checks the current location - instead of the location of its neighbors.

bool mazeTraversal(char maze[12][12], int x, int y) {
  if (maze[x][y] == 'X')
    return true; // found end!

  if (maze[x][y] == '.') {
    // we are still on a path - see where exploration leads!
    if (mazeTraversal(maze, x + 1, y)) return true;
    if (mazeTraversal(maze, x, y + 1)) return true;
    if (mazeTraversal(maze, x - 1, y)) return true;
    if (mazeTraversal(maze, x, y - 1)) return true;
  }

  // Didn't find any valid path from here -
  // maybe "here" is a wall!
  return false;
}

Ultimately you'd likely want to do something else on the found path (i.e. where it reads "return true") such as record the current position.

Also note that, depending on the language, the if (mazeTraversal..) return true stuff can also be "cleaned up". In C, consider using a short-circuiting || operator. Then we can shorten the end case to something like:

int leadsToEnd =
       (maze[x][y] == 'X')      // at end
    || (maze[x][y] == '.')      // or not end ..
       && (mazeTraversal(maze, x + 1, y)   // but may lead to end
           || mazeTraversal(maze, x, y + 1)
           || mazeTraversal(maze, x - 1, y) 
           || mazeTraversal(maze, x, y - 1));

And thus the entire function effectively becomes return leadsToEnd (substituting the above expression as desired). Of course, you'll have to decided which approach - the latter example is arguably overly clever - or hybrid of such makes most sense to you.

Answer 2

As you have it now, when you hit a dead-end, you just return. That is correct, as you will back up to the previous call and then select the next path. When you have traversed all the possible paths, your top-level call will return.