How to avoid StackOverflow Error in Recursive MazeSolver

Question

Like many other java students in college, I need to develop a maze program that solves the maze. My solveMaze method that implements recursion returned a stackoverflow runtime error. How do I solve this problem please? Does this have to do with my algorithm? Thanks in advance.

A) I created a solution maze that array that's going to hold the path to the exit.

B) Then, I implemented a method solveMaze() that took a step toward the exit everytime it's called.

Note: The isWall() method checks if the position you're moving to is a wall or not.

  public void showPath() {
    int[][] sol = new int[m.length][m[0].length];
    for (int j = 0; j < sol.length; j++) {
      for (int i = 0; i < sol[0].length; i++) {
        sol[j][i] = m[j][i];
      }
    }
    if (solveMaze(sol, m.length - 1, 0, exitCords) == false)
      System.out.println("Solution doesn't exist");
    else {
      for (int y = 0; y < sol.length; y++) {
        for (int x = 0; x < sol[0].length; x++) {
          if (sol[y][x] == exitCords[0] && sol[y][x] == exitCords[1]) {
            System.out.print("E ");
          } else {
            if (sol[y][x] == 1) {
              System.out.print("  ");
            } else if (sol[y][x] == 3) {
              System.out.print("~");
            } else {
              System.out.print("# ");
            }
          }

        }
        System.out.println();
      }
    }
  }

  public boolean solveMaze(int[][] sol, int y, int x, int[] exitCords) {
    //exitCords[] is a one-dimensional array that holds the x and y coordinate of the exit point on a maze.
    if (y == exitCords[1] && x == exitCords[0]) {//Base Case
      return true;
    }
    //North
    if (!isWall(x, y - 1) && sol[y - 1][x] != 3) {
      sol[y][x] = 3;//3 is assigned to positions you already visited.
      y--;
      sol[y][x] = 3;
      //Implement recursion to call the solveMaze again on this line.
      solveMaze(sol, y, x, exitCords);
      return true;
    }

    //South
    else if (!isWall(x, y + 1) && sol[y + 1][x] != 3) {
      sol[y][x] = 3;
      y++;
      sol[y][x] = 3;
      solveMaze(sol, y, x, exitCords);
      return true;
    }
    //East
    else if (!isWall(x + 1, y) && sol[y][x + 1] != 3) {
      sol[y][x] = 3;
      x++;
      sol[y][x] = 3;
      solveMaze(sol, y, x, exitCords);
      return true;
    }
    //West
    else if (!isWall(x - 1, y) && sol[y][x - 1] != 3) {
      sol[y][x] = 3;
      x--;
      sol[y][x] = 3;
      solveMaze(sol, y, x, exitCords);
      return true;
    }
    /*The following line of code are to get out of dead ends and replace every position near a dead end with a wall*/
    else if ((isWall(x, y - 1) && isWall(x, y + 1) && isWall(x + 1, y)) || (isWall(x, y - 1) && isWall(x, y + 1) && isWall(x - 1, y))
        || (isWall(x - 1, y) && isWall(x, y + 1) && isWall(x + 1, y)) || (isWall(x - 1, y) && isWall(x, y - 1) && isWall(x + 1, y))) {

      if (isWall(x, y - 1) && isWall(x, y + 1) && isWall(x + 1, y)) {
        sol[y][x] = 0;
        solveMaze(sol, y, x - 1, exitCords);
        return true;
      }
      if (isWall(x, y - 1) && isWall(x, y + 1) && isWall(x - 1, y)) {
        sol[y][x] = 0;
        solveMaze(sol, y, x + 1, exitCords);
        return true;
      }
      if (isWall(x - 1, y) && isWall(x, y + 1) && isWall(x + 1, y)) {
        sol[y][x] = 0;
        solveMaze(sol, y - 1, x, exitCords);
        return true;
      }
      if (isWall(x - 1, y) && isWall(x, y - 1) && isWall(x + 1, y)) {
        sol[y][x] = 0;
        solveMaze(sol, y + 1, x, exitCords);
        return true;
      }
    }
    return false;
  }

Answer 1

You have different ways to solve the problem:

• The first one is to rewrite your code without using recursion (no luck for tail recursion - Java doesn't have optimization for it)
• Another way is to increase stack size using -Xss option
• Or you can add actual depth check to solveMaze method, e.g.:

  public void showPath() {
    // ...
    if (solveMaze(sol, m.length - 1, 0, exitCords , 0) == false) {
    // ...
  }

  public boolean solveMaze(int[][] sol, int y, int x, int[] exitCords, int depth) {
    if (depth > 64) {
      return false;
    }
    // ...
    solveMaze(sol, y, x, exitCords, depth + 1); 
    // ...  
  }

Answer 2

A stack overflow error means that your recursion has gone deeper than the language allows. For a small maze, this shouldn't happen, unless you are revisiting locations in the maze. As your code does not seem to make any effort to avoid that, you might want to fix that.