Overflowing stack with recursion that should terminate?

Question

I am attempting to make a random maze generator using Java and the recursive backtracking algorithm. I am getting stack overflow when I try to run this code. I know some about stack, I don't think this is infinite recursion. My guess is that I have a big logic error. Do I have to allocate more memory?

The stack trace:

Exception in thread "main" java.lang.StackOverflowError
    at java.base/java.util.Vector.elementAt(Vector.java:499)
    at java.base/java.util.Stack.peek(Stack.java:103)
    at java.base/java.util.Stack.pop(Stack.java:84)
    at mazeMaker.Maze.generateMaze(Maze.java:115)
    at mazeMaker.Maze.generateMaze(Maze.java:115)
...
    at mazeMaker.Maze.generateMaze(Maze.java:115)
    at mazeMaker.Maze.generateMaze(Maze.java:115)

Main.java

package mazeMaker;

public class Main 
{

    public static void main(String[] args) 
    {
        Maze mainMaze = new Maze(20, 30);
    }

}

Maze.java

package mazeMaker;

import java.util.Random;
import java.util.Stack;

public class Maze 
{
    public int xSize = 0;
    public int ySize = 0;
    public int totalDimensions = 0;

    Random randomGenerator = new Random();

    public Cell[][] cellData;

    public Stack<Cell> cellStack = new Stack<Cell>();

    Cell tempCell; // Temporary variable used for maze generation

    public Maze(int xSize, int ySize) 
    {
        cellData = new Cell[xSize][ySize];
        this.xSize = xSize;
        this.ySize = ySize;
        this.totalDimensions = this.xSize * this.ySize;

        // Initialize array objects
        for (int i = 0; i < this.xSize; i++) 
        {
            for (int j = 0; j < this.ySize; j++) 
            {
                cellData[i][j] = new Cell();
            }
        }

        // Assign x and y positions
        for (int i = 0; i < this.xSize; i++) 
        {
            for (int j = 0; j < this.ySize; j++) 
            {
                cellData[i][j].xPos = i;
                cellData[i][j].yPos = j;
            }
        }

        initBoundries();
        generateMaze();
    }

    private void initBoundries() 
    {
        // Initialize the border cells as visited so we don't go out of bounds
        int m = this.xSize;
        int n = this.ySize;

        for (int i = 0; i < m; i++) 
        { 
            for (int j = 0; j < n; j++) 
            { 
                if (i == 0 || j == 0 || i == n - 1 || j == n - 1) 
                    cellData[i][j].hasBeenVisited = true;
            } 
        } 
    }

    private void generateMaze(int x, int y) 
    {
        // Set current cell as visited
        cellData[x][y].hasBeenVisited = true;

        // While there are unvisited neighbors
        while (!cellData[x][y+1].hasBeenVisited || !cellData[x+1][y].hasBeenVisited || !cellData[x][y-1].hasBeenVisited || !cellData[x-1][y].hasBeenVisited) 
        {
            // Select a random neighbor
            while (true) 
            {
                int r = randomGenerator.nextInt(4);
                if (r == 0 && !cellData[x][y+1].hasBeenVisited) 
                {
                    cellStack.push(cellData[x][y]);
                    cellData[x][y].hasNorthWall = false;
                    cellData[x][y+1].hasSouthWall = false;
                    generateMaze(x, y + 1);
                    break;
                }
                else if (r == 1 && !cellData[x+1][y].hasBeenVisited) 
                {
                    cellStack.push(cellData[x][y]);
                    cellData[x][y].hasEastWall = false;
                    cellData[x+1][y].hasWestWall = false;
                    generateMaze(x+1, y);
                    break;
                }
                else if (r == 2 && !cellData[x][y-1].hasBeenVisited) 
                {
                    cellStack.push(cellData[x][y]);
                    cellData[x][y].hasSouthWall = false;
                    cellData[x][y-1].hasNorthWall = false;
                    generateMaze(x, y-1);
                    break;
                }
                else if (r == 3 && !cellData[x-1][y].hasBeenVisited) 
                {
                    cellStack.push(cellData[x][y]);
                    cellData[x][y].hasWestWall = false;
                    cellData[x-1][y].hasEastWall = false;
                    generateMaze(x-1, y);
                    break;
                }
            }
        }

        // There are no unvisited neighbors
        tempCell = cellStack.pop();
        generateMaze(tempCell.xPos, tempCell.yPos);

    }

    // Begin generating maze at top left corner
    private void generateMaze() 
    {
        generateMaze(1,1);
    }

}

Cell.java

package mazeMaker;

public class Cell 
{
    public boolean isCurrentCell;
    public boolean hasBeenVisited;
    public boolean hasNorthWall;
    public boolean hasSouthWall;
    public boolean hasEastWall;
    public boolean hasWestWall;
    public int xPos;
    public int yPos;
}

Answer 1

I tried to run your project on my own environment but unfortunately, I was not able to reproduce your issue.

However, I was facing an IndexOutOfBound exception in the method generateMaze. While I was solving this, I figured out that there was an issue in the initBoudaries method.

Indeed, when you set the boolean hasBeenVisited to true, you do not use the right variable in the IF clause. Here is the version I tried instead :

private void initBoundries() 
    {
        // Initialize the border cells as visited so we don't go out of bounds

        for (int i = 0; i < this.xSize; i++) 
        { 
            for (int j = 0; j < ySize; j++) 
            { 
                if (i == 0 || j == 0 || i == xSize - 1 || j == ySize - 1) 
                    cellData[i][j].hasBeenVisited = true;
            } 
        } 
    }

Now about the emptyStackException, I think that if this stack is empty, this means that there is no more cell to handle (as you mentioned in your comment) and the program must end. If I am right, just make sure to test if your stack is empty before call the method pop() on it like this :

// There are no unvisited neighbors
        if (!cellStack.isEmpty()) {
            tempCell = cellStack.pop();
            generateMaze(tempCell.xPos, tempCell.yPos);
        }

Hope it will help.

Answer 2

The method generateMaze can never terminate not even by chance for some simple reason:

For terminating the generateMaze method would need to finish it's execution - it has to return.

There are no return statements in this method, therefore it has to pass the while loops and then continue until the execution reaches and finishes the last statement of the method.

However the last statement is generateMaze(tempCell.xPos, tempCell.yPos); which starts a new recursion, therefore your code can never ever terminate!