Stack overflow when finding all paths through a grid with recursion and backtracking

Question

I have been following a playlist of Java for data structures and algorithms and I have come across the topic of Backtracking in which a board is given to you along with starting point (0,0) and end point (board_length,board_width). The task is to find and print all the possible paths that occur in a way that you don't visit and tile which was previously visited in the current path for which the recursion call is going on.

Here is the code in Java for the problem:

import java.util.ArrayList;
import java.util.Arrays;

public class Main {

    public static void main(String[] args){
        boolean[][] board={{false,false,false},
                           {false,false,false},
                           {false,false,false},
    };
        ArrayList<String> ans=countPath("",0,0,board);
        System.out.println(ans);
    }

    static ArrayList<String> countPath(String path,int r,int c,boolean[][] board){
        ArrayList<String> ans=new ArrayList<>();
        if(r==board.length-1 && c==board[0].length-1){
            ans.add(path);
            return ans;
        }else if(board[r][c]){
            board[r][c]=false;
            path=path.substring(0,path.length()-1);
            return ans;
        }else{
            ArrayList<String> temp=new ArrayList<>();
            board[r][c]=true;
            if(r>0){
                temp=countPath(path+"U",r-1,c,board);
                ans.addAll(temp);
            }

            if(c<2){
                temp=countPath(path+"R",r,c+1,board);
                ans.addAll(temp);
            }

            if(r<2){
                temp=countPath(path+"D",r+1,c,board);
                ans.addAll(temp);

            }

            if(c>0){
                temp=countPath(path+"L",r,c-1,board);
                ans.addAll(temp);
            }
            board[r][c]=false;
            path=path.substring(0,path.length()-1);
            return ans;
        }
    }
}

But I am getting an error of stack overflow which I don't know how to fix. I don't know why it is throwing the stack overflow error. I do know that it has to do with some loop that is occurring for the error to get thrown but I am not able to figure out which loop it is. Please help me point out that loop.

Below is the error:

Exception in thread "main" java.lang.StackOverflowError
    at Main.countPath(Main.java:23)
    at Main.countPath(Main.java:29)
    at Main.countPath(Main.java:39)
        ... and so on as it is recursion

I tried debugging the code file and observed that there was loop occurring for the path variable but I am not able to figure out how to stop that loop from occurring. I have provided the restriction for not going back to the tile that was previously visited but still it is throwing the error.

Answer 1

First, begin by autoformatting your code so there's whitespace between operators. It's difficult to read otherwise.

---

The main problem is the else if (board[r][c]) {} branch. If you mark a visited cell as unvisited, a loop will occur. Only mark and unmark visited cells in the unvisited branch:

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        System.out.println(countPaths("", 0, 0, new boolean[3][3]));
    }

    static ArrayList<String> countPaths(
        String path, int r, int c, boolean[][] board
    ) {
        var ans = new ArrayList<String>();

        if (r == board.length - 1 && c == board[r].length - 1) {
            ans.add(path);
        }
        else if (!board[r][c]) {
            board[r][c] = true;

            if (r > 0) {
                ans.addAll(countPaths(path + "U", r - 1, c, board));
            }
            if (c < board[r].length - 1) {
                ans.addAll(countPaths(path + "R", r, c + 1, board));
            }
            if (r < board.length - 1) {
                ans.addAll(countPaths(path + "D", r + 1, c, board));
            }
            if (c > 0) {
                ans.addAll(countPaths(path + "L", r, c - 1, board));
            }

            board[r][c] = false;
        }

        return ans;
    }
}

There are other issues. For one, some of the path assignments don't do anything, since it's a reassignment of a local variable.

Allocating new ArrayLists for every call and merging them as you unwind the call stack is expensive. I'd allocate one result list and pass a reference to it into all of the calls.

You can use a public helper wrapper method to avoid exposing result parameters to the top-level caller, keeping the recursive method private to avoid corrupted calls.

I'll leave these (and other) optimizations as an exercise.