如何终止Java二维数组峰值查找的递归？单路径输出问题求助

我明白你现在的困扰——花了好多时间调这个递归找峰值路径的方法，结果找到一条后程序还会回溯去搜其他路径，怎么都没法让它停下来。别着急，咱们来拆解问题，一步步解决它。

问题根源分析 #

你原来的printPath是void类型的方法，每一个if分支都会独立触发递归调用。哪怕前面的递归已经找到了完整的峰值路径，后面的if只要条件满足，还是会继续执行，导致回溯后又去探索其他分支，最终打印多条路径。你尝试过用布尔标记，但应该是没处理好递归返回值的传递逻辑，所以没起到终止作用。

解决方案：用返回值控制递归终止 #

核心思路是把方法的返回类型改成boolean，用返回值来标记是否已经找到并打印了一条完整的峰值路径。一旦某个递归分支返回true，就立刻向上传递这个信号，跳过后续所有分支的探索，直接终止整个递归链。

修改后的代码 #

private static boolean printPath(int[][] mat, int i, int j) {
    // 打印当前路径节点
    System.out.println("(" + i + "," + j + ")");
    
    // 标记当前节点是否为峰值
    boolean isPeak = true;

    // 检查下方：如果下方元素更大，递归探索
    if (i < mat.length - 1 && mat[i][j] < mat[i+1][j]) {
        if (printPath(mat, i+1, j)) {
            return true; // 找到路径，直接终止递归链
        }
        isPeak = false;
    }

    // 检查右方：仅在未找到路径时继续探索
    if (j < mat[0].length - 1 && mat[i][j] < mat[i][j+1]) {
        if (printPath(mat, i, j+1)) {
            return true;
        }
        isPeak = false;
    }

    // 检查上方：仅在未找到路径时继续探索
    if (i > 0 && mat[i][j] < mat[i-1][j]) {
        if (printPath(mat, i-1, j)) {
            return true;
        }
        isPeak = false;
    }

    // 检查左方：仅在未找到路径时继续探索
    if (j > 0 && mat[i][j] < mat[i][j-1]) {
        if (printPath(mat, i, j-1)) {
            return true;
        }
        isPeak = false;
    }

    // 如果当前节点是峰值，返回true表示找到完整路径
    return isPeak;
}

关键改动说明 #

1. 返回值类型变更：从void改为boolean，true代表已找到有效路径，无需继续探索；false代表当前节点不是峰值，需要继续找。
2. 递归分支的条件判断：每一个方向的递归调用后，都会检查返回值。如果返回true，就立刻向上返回true，直接跳过后续所有分支的执行，彻底终止递归。
3. 冗余边界判断移除：比如原来向上探索时的i < mat.length-1是多余的，已经帮你删掉了，让逻辑更简洁。
4. 峰值判断逻辑：当当前节点的上下左右都没有比它大的元素时，标记为峰值，返回true结束递归链。

调用方式示例 #

假设你从数组的(0,0)位置开始查找，只需要这样调用：

int[][] matrix = {{1,3,2},{4,6,5},{7,9,8}};
printPath(matrix, 0, 0);

程序会打印第一条找到的峰值路径，然后立刻终止，不会再回溯探索其他路径。

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