StackOverflow error due to recursion in Java

Question

I'm attempting to use recursive methods to solve a maze represented by an int array of 1s and 0s in Java. wasHere[] checks if the method has already parsed that particular set of coordinates, correctPath[] records the answer path to the maze; both of them are initialized with every index being false.

import java.awt.Point;
class mazeSolver{
   int[][] maze;
   int startX, startY; 
   int endX, endY;     
   int width, height;
   boolean[][] wasHere, correctPath;

   mazeSolver(int[][] m, int sX,int sY,int nX,int nY){
      maze = m;
      width = maze[0].length;
      height = maze.length;
      startX = sX;
      startY = sY;
      endX = nX;
      endY = nY;
      System.out.println("Height: " + height + "\t Width: " + width);

      correctPath = new boolean[height][width];
      wasHere = new boolean[height][width];
      for (int row = 0; row < maze.length; row++)  
         for (int col = 0; col < maze[row].length; col++){
            wasHere[row][col] = false;
            correctPath[row][col] = false;
         }
      solveMaze(startX,startY);
   }

     public boolean solveMaze(int x, int y){
      boolean solvable = recursiveSolve(x,y);
      return solvable;
     }

     private boolean recursiveSolve(int x, int y){ //1s are walls, 0s are free space
      if (x == endX && y == endY)
         return true;
      if (wasHere[y][x] || maze[y][x] == 1)
         return false;

      wasHere[y][x] = true;

      if (y < height-1){
         if (solveMaze(x,y+1))
            return true;
      }

      if (y > 0){
         if (solveMaze(x,y-1))
            return true;
      }

      if (x > 0){
         if (solveMaze(x-1,y))
            return true;
      }

      if (x < width-1){
         if (solveMaze(x+1,y)) 
            return true;
      }

      return false;
   }

   public int[][] getSolvedMaze(){
      for(int y = 0; y < height; y++)
         for (int x = 0; x< width; x++)
            if(correctPath[y][x])
               maze[y][x] = 2;
      return maze;
   }
}

I have been stuck with this error for the past few hours, any help would be greatly appreciated.

It's possible there is no bug. How big is your maze? The stack is finite, so for every stack there's a big enough maze to overflow it. — Barry Fruitman
– Barry Fruitman, Commented Jun 13, 2015 at 0:54
@BarryFruitman My test maze is 300x400. I'd preferably like to process ones that are 2000x2000 though also — potatochemist
– potatochemist, Commented Jun 13, 2015 at 2:59

vinay chilakamarri · Accepted Answer · 2015-06-13 01:40:23Z

1

I think there is no bug as such (not that I can see) but you are recursing way too much which caused this issue. I am not sure what values are you feeding into the program, but I was able to notice the issue with initializing the above program with these parameters:

mazeSolver MazeSolver = new  mazeSolver(new int [100][100], 0, 0, 100,100);

So to run your program as-it-is I increased the stack size. You could do so by feeding the following parameter to JVM as you run the program: -Xss258m

This stack size was able to accommodate array of 1000 size. I did not have much time to test other sizes.

mazeSolver MazeSolver = new  mazeSolver(new int [1000][1000], 0, 0, 1000,1000);

answered Jun 13, 2015 at 1:40

vinay chilakamarri

2513 silver badges8 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

potatochemist Over a year ago

I set the run arguments to -Xss258m as you suggested, then to -Xss2580m and neither of them worked :/. My array is roughly 300x400, which is odd since 258 megabytes worked for your 1000x1000 array. Thanks for the input though.

vinay chilakamarri Over a year ago

Can you show how you are doing it? If it worked for me, it has to for you. Also print "java -version" and paste it here please.

vinay chilakamarri Over a year ago

Here is the way I ran: ../jdk1.6.0_38/bin/java -Xss218m mazeSolver

potatochemist Over a year ago

i.imgur.com/ruHroYN.png - That's how I set the argument (IDE is called jGrasp). Here is the output: java version "1.8.0_40" Java(TM) SE Runtime Environment (build 1.8.0_40-b26) Java HotSpot(TM) Client VM (build 25.40-b25, mixed mode, sharing)

vinay chilakamarri Over a year ago

I am not a jGrasp expert, but quickly downloading and trying it out shows that the jGrasp is setting the arguments this way: java mazeSolver -Xss218m. This is not going to work. To test what I am recommending, try the command line approach. Go to command line, execute java with arguments EXACTLY like I showed you. If jGrasp can't set the runtime stack size for a Java program...I'd rather use Eclipse which had pretty straightforward way to set JVM arguments for programs...

|

Collectives™ on Stack Overflow

StackOverflow error due to recursion in Java

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related