递归回溯求解网格全路径时遇Stack Overflow错误求助

问题描述 #

我正在学习Java数据结构与算法的回溯法，需求是在给定网格中，从起点(0,0)到终点（网格右下角），找出所有不重复访问已走过格子的路径。编写代码后运行出现Stack OverflowError，已知是递归循环导致，但无法定位具体循环点，请求排查错误。

错误代码 #

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;
        }
    }
}

错误信息 #

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

问题分析 #

• 错误的回溯状态修改：在判断当前格子已访问的分支中，错误地将board[r][c]设为false并截断path，这会破坏上层递归的状态，导致后续递归可以重复访问该格子，直接引发无限递归循环（比如来回穿梭同一个格子）。
• 硬编码边界判断：使用c<2、r<2这类固定值判断边界，仅适配3x3网格，且逻辑不严谨。
• 不必要的路径截断：Java字符串是不可变类型，每次递归传入的path+"方向"都是新字符串，上层递归的path不会被修改，手动截断反而会导致路径状态混乱。

修正后的代码 #

import java.util.ArrayList;

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;
        }
        // 当前格子已访问，直接返回空列表
        if(board[r][c]){
            return ans;
        }

        // 标记当前格子为已访问
        board[r][c]=true;

        // 向上走
        if(r>0){
            ans.addAll(countPath(path+"U",r-1,c,board));
        }
        // 向右走
        if(c < board[0].length-1){
            ans.addAll(countPath(path+"R",r,c+1,board));
        }
        // 向下走
        if(r < board.length-1){
            ans.addAll(countPath(path+"D",r+1,c,board));
        }
        // 向左走
        if(c>0){
            ans.addAll(countPath(path+"L",r,c-1,board));
        }

        // 回溯：恢复当前格子的访问状态
        board[r][c]=false;
        return ans;
    }
}

修正说明 #

• 移除已访问分支中对board和path的错误修改，遇到已访问格子直接返回空列表即可。
• 将边界判断改为动态适配网格大小的逻辑，支持任意尺寸的网格。
• 删除手动截断path的代码，利用Java字符串不可变的特性自动维护路径状态。
• 保留正确的回溯操作：递归前标记访问，递归结束后恢复状态，确保上层递归的状态不受影响。

内容的提问来源于stack exchange，提问作者Aadit Baldha