Solving maze using recursion in java

Question

I am to solve maze using recursion in java but when I try to run I get a Stack overflow error. A maze starts at a + and the path that leads to the end is also +, ends at a -, walls are X, spaces are potential paths, '.' will mark a dead end path. What I think causes the error is the backtracking step. The code shown is the part that I get the error on. When The maze path is a straight line the maze works fine. Any help is much appreciated.

/*Sample maze that causes errors
       XXXXXXXXXXXX
       +   XXX    -
       XXX XXX XXXX
       XXX  XX XXXX
       XX         X
       XXXXXXXXXXXX
*/

   public  boolean isValidSpot(int r, int c) { // r and c represent position in 2d array
       if(r < nrow && c < ncol)  //make sure current postion is not out of bounds
       {  
        return true;
       }
       return false;
   }

   public  boolean traverse(char[][] maze, int r, int c) {
       if(isValidSpot(r, c)) {
           if(maze[r][c]=='X')
               return false;
           if(maze[r][c]=='-') {
               return true;}

           maze[r][c]='+';

           //right
           if(traverse(maze, r, c+1))
               return true;
           //up
           if(traverse(maze, r-1, c ))//error on this line
               return true;

           //down
           if(traverse(maze, r+1, c))//error on this line
               return true;


           //left
           if(traverse(maze, r, c - 1))
               return true;

           //backtrack
           maze[r][c]='.';
           return false;

       }

       return false;
   }

The solved maze look something like this

/*
        XXXXXXXXXXXX
        ++++XXX++++-
        XXX+XXX+XXXX
        XXX+ XX+XXXX
        XX.+++++...X
        XXXXXXXXXXXX

Answer 1

Code to traverse through the maze is below remember '+' represents that it's the start and '*' represent that we have traversed it so we don't traverse it again other wise it will lead to stackoverflow since traverse method will keep on calling it self until overflow happens.

from each cell we are traversing up, down , left and right if there is path we will reach to out goal.

Code:

import java.util.ArrayList;

public class Maze{
    //checks weather the spot is valid
    public  static boolean isValidSpot(int r, int c, int nrow, int ncol) {
        return r < nrow && c < ncol && r >= 0 && c >= 0; 
    }
    //traverses through the maze
    public static boolean traverse(final char[][] maze, final int r, final int c) {

        int nrow = maze.length, ncol = maze[0].length;

        if(isValidSpot(r, c, nrow, ncol)) {
            if(maze[r][c] == 'X' || maze[r][c] == '.' || maze[r][c] == '*')
                return false;
            if(maze[r][c]=='-') {
                return true;
            }

            maze[r][c]='*';

            //right
            if(traverse(maze, r, c+1))
                return true;
            //up
            if(traverse(maze, r-1, c ))
                return true;

            //down
            if(traverse(maze, r+1, c))
                return true;

            //left
            if(traverse(maze, r, c - 1))
                return true;

            //backtrack
            maze[r][c]='.';
            return false;

        }

        return false;
    }
    ///////////////Main////////////////
    public static void main(String ...$){
        var out = System.out;

        ArrayList<String> list = new ArrayList<>();

        list.add("XXXXXXXXXXXX");
        list.add("+   XXX    -");
        list.add("XXX XXX XXXX");
        list.add("XXX  XX XXXX");
        list.add("XX         X");
        list.add("XXXXXXXXXXXX");

        char[][] maze =new char[list.size()][];
        //converting list of string to a 2D char array
        for(int i=0;i<list.size();i++){
            String str = list.get(i);
            maze[i] = str.toCharArray(); 
        }
        boolean pathExists = false;
        for(int i =0;i<maze.length;i++)
            for(int j =0;j<maze[i].length;j++)
                if(maze[i][j] == '+'){
                    //out.println("found");
                    pathExists = traverse(maze,i,j);
                }
        out.println(pathExists);
        for(int i =0;i<maze.length;i++){
            for(int j =0;j<maze[i].length;j++)
                out.print(maze[i][j]);
            out.println();
        }

    }
}

output:

$ javac Maze.java && java Maze 
true
XXXXXXXXXXXX
****XXX****-
XXX*XXX*XXXX
XXX**XX*XXXX
XX  ****...X
XXXXXXXXXXXX