Maze Generation giving me a stack overflow error

Question

In my maze generation code, I am getting a stack overflow error, why? How do i fix it? It is only occurring at the end. If i comment out one of the if statements within the else statement, the code works fine. Why is this? I am attempting to recursively generate a maze, and I am not sure if I am doing it right

    public void generate(int row, int col) {

        rng = new Random();
        int move = rng.nextInt(4);

        if(hasUnvisited()==false) {
            System.out.println("e");
        }

        else if(move==0&&row+2<=19) {
            if (maze[row+2][col].getVisited()==false) {
                maze[row+1][col].remove();
            }
            maze[row][col].visit();
            generate(row+2,col);
        }
        else if(move==1&&row-2>=0) {
            if (maze[row-2][col].getVisited()==false) {
                maze[row-1][col].remove();
            }
            maze[row][col].visit();
            generate(row-2,col);
        }
        else if(move==2&&col+2<=19) {
            if (maze[row][col+2].getVisited()==false) {
                maze[row][col+1].remove();
            }
            maze[row][col].visit();
            generate(row,col+2);
        }
        else if(move==3&&col-2>=0) {
            if (maze[row][col-2].getVisited()==false) {
                maze[row][col-1].remove();
            }
            maze[row][col].visit();
            generate(row,col-2);
        }

        else {
            maze[row][col].visit();
            if (move==0) {
                generate(row-2,col);
            }

            else if (move==1) {
                generate(row+2,col);
            }

            else if (move==2) {
                generate(row,col-2);
            }

            else if (move==3) {
                generate(row,col+2);
            }
        }       
    }

Exception in thread "main" java.lang.StackOverflowError
    at java.util.Random.<init>(Unknown Source)
    at Maze.generate(Maze.java:41)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:94)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:94)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:88)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:88)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:88)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:94)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:94)
    at Maze.generate(Maze.java:88)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:88)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:67)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:74)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:60)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:53)
    at Maze.generate(Maze.java:67)

Add the stack trace of error. You probably have infinite loop somewhere and stack trace shows where. Also what is implementation of `hasUnvisited()`, it may be that your end condition is wrong. — Piro, May 24 '19 at 04:19
What is the stack trace of error? Also, the end condition is never met. Instead, i get an error. If i remove one of the if statements in the else portion(any of them) the code works, but stops once the maze generation goes out of bounds — deejaylul, May 24 '19 at 04:25
See [What is stack trace and how can I use it to debug my application errors](https://stackoverflow.com/questions/3988788/what-is-a-stack-trace-and-how-can-i-use-it-to-debug-my-application-errors) — Piro, May 24 '19 at 04:32

score 0 · Answer 1 · answered May 24 '19 at 06:24

Your stack is very verbose in telling you two things:

You actually have a stack overflow that is not caused by a forgotten index increment or something thelike.
The code is not (by the looks of it) caught in an infinite loop, because the stack frames terminate at different lines in the code. If it were different, you'd have an infinite loop. It could still be one (hidden by seeming randomness) but it is much less likely.

Currently whenever you do a recursive call (call generate within generate), you increase the stack's size. You pass all the current field states into a stack frame and the VM has to remember that, while you continue the next lower invokation of generate. Because this will probably also make a call to itself, and so forth, at some point, the stack becomes too large to store on the stack.

You have two options in my opinion. Either increase maximum stack size, when starting the VM set JAVA_OPTS=%JAVA_OPTS% -Xms1024m -Xmx1024m or (better option) rework your code to be iterative. That way, you don't increase your stack indefinetly. What would that mean:

Instead of working recusrively, (make calls to the method itself) you would have to create loops that would access different levels of a stack by explicit design. All recursive code can (in IT theory) be converted into iterative code, so this should be possible. You have to think differently however.

Maze Generation giving me a stack overflow error

1 Answers1