Java递归实现二维数组最大岛屿和的getIslandValue方法故障排查

版本1栈溢出原因 #

• 没有对已访问的单元格做标记，导致递归调用时出现循环：比如从坐标(r,c)调用右侧(r,c+1)后，(r,c+1)的逻辑会再次调用左侧(r,c)，两个非0单元格互相递归调用，永远无法触发map[r][c]==0的base case，最终栈内存耗尽溢出。

版本2结果错误原因 #

• 仅遍历右下两个方向，会漏掉当前单元格左侧、上方相连的非0岛屿单元格，统计的和不完整
• 求和逻辑错误使用Math.max取两个方向的最大值而不是相加，进一步导致结果和实际岛屿总和不符

为什么需要显式置0？ #

base case里的map[r][c]==0是终止判断条件，但你如果不主动将已经访问过的非0单元格修改为0，那么该单元格在后续被相邻格子的递归逻辑再次访问时，仍然会被判定为有效单元格，重复进入递归逻辑，无法触发base case返回。置0操作的本质就是给单元格打「已访问」标记，避免重复统计和循环递归。

private static int getIslandValue(int map[][], int r, int c) {
    // 越界或者当前单元格为0（已访问/是海洋）直接返回0
    if (r < 0 || c < 0 || r >= map.length || c >= map[r].length || map[r][c] == 0) {
        return 0;
    }
    // 先保存当前单元格的值
    int currentValue = map[r][c];
    // 置0标记已访问，避免后续递归重复统计
    map[r][c] = 0;
    // 递归计算四个方向的岛屿值总和
    int right = getIslandValue(map, r, c + 1);
    int down = getIslandValue(map, r + 1, c);
    int left = getIslandValue(map, r, c - 1);
    int up = getIslandValue(map, r - 1, c);
    // 返回当前值加四个方向的总和
    return currentValue + right + down + left + up;
}

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