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;
  }

I understand you are learning, so i think you need to figure this one out on your own. But here is a tip for solving your problem: Clean, your, code. This way you can more eassily spot your problem and debug much faster. This link provides powerful knowledge about recursion, it's directed at Python, but still you can take a learning out of it, espacially the rules at the top: http://interactivepython.org/runestone/static/pythonds/Recursion/TheThreeLawsofRecursion.html — Nebulosar, Apr 20 '18 at 06:28
Welcome to SO. To make help possible and easier please post [mcve]. Include test data and the expected output. — c0der, Apr 20 '18 at 06:32

score 2 · Answer 1 · answered May 30 '19 at 07:52

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); 
    // ...  
  }

score 0 · Answer 2 · answered May 29 '19 at 17:06

0

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.

answered May 29 '19 at 17:06

Scott Hunter

48,888
12
60
101

Edit the question (proper list, whatever, `code`-style in the text) and you will get the Excavator too ;-) – tevemadar May 29 '19 at 17:27

How to avoid StackOverflow Error in Recursive MazeSolver

2 Answers2