递归栈溢出问题排查：N×N二进制数组连通1计数异常

问题场景 #

给定由0和1组成的N×N二维数组，需递归计算指定索引所在连通分量的1的总数（包含间接相连的上下左右邻居）。测试7×7数组时，调用Recursive(arr,2,5)预期返回6，但实际触发Stack Overflow Exception。

测试代码：

static void Main(string[] args)
{
    int[,] arr = { 
       { 0,0,0,1,0,0,0 },
       { 1,0,0,1,1,0,0 },
       { 0,0,0,0,1,1,0 },
       { 0,0,0,0,1,0,0 },
       { 0,0,0,0,0,0,0 },
       { 0,1,1,1,1,0,0 },
       { 1,0,0,1,0,0,0 }, 
    };

    Console.WriteLine(Recursive(arr,2,5));
    Console.ReadLine();
}

待测试的递归函数：

static public int Recursive(int[,] arr, int x, int y) 
{   
    if (x < 0 || y < 0 || x > arr.GetLength(0) || y > arr.GetLength(1))
    {
        return 0;
    }
    
    if (arr[x, y] == 1)
    {
        return 1 + 
               Recursive(arr, x - 1, y) +
               Recursive(arr, x + 1, y) + 
               Recursive(arr, x, y - 1) +
               Recursive(arr, x, y + 1);
    }
    else
    {
        return 0;
    }                   
}

错误原因 #

1. 无限递归导致栈溢出：递归时未标记已访问的1，会在相邻的1之间反复调用（比如(2,5)调用(2,4)，(2,4)又回调(2,5)），形成无限递归，最终耗尽栈空间触发异常。
2. 边界判断错误：数组索引从0开始，最大有效索引为数组长度-1，原代码中x > arr.GetLength(0)的判断会允许x等于数组长度（比如7×7数组中x=7），此时访问arr[x,y]会触发索引越界。

修复方案 #

方案1：修改原数组标记已访问（简单直接） #

修改递归函数，将访问过的1改为0避免重复递归，同时修正边界判断逻辑：

static public int Recursive(int[,] arr, int x, int y) 
{   
    // 修正边界判断：索引不能小于0，也不能大于等于数组长度
    if (x < 0 || y < 0 || x >= arr.GetLength(0) || y >= arr.GetLength(1))
    {
        return 0;
    }
    
    if (arr[x, y] == 1)
    {
        // 标记当前节点为已访问，防止重复递归
        arr[x, y] = 0;
        return 1 + 
               Recursive(arr, x - 1, y) +
               Recursive(arr, x + 1, y) + 
               Recursive(arr, x, y - 1) +
               Recursive(arr, x, y + 1);
    }
    else
    {
        return 0;
    }                   
}

方案2：使用额外数组标记已访问（不修改原数组） #

若需保留原数组原始数据，可创建布尔数组记录访问状态：

static public int Recursive(int[,] arr, int x, int y, bool[,] visited) 
{   
    if (x < 0 || y < 0 || x >= arr.GetLength(0) || y >= arr.GetLength(1))
    {
        return 0;
    }
    
    // 仅当当前是1且未被访问时才递归
    if (arr[x, y] == 1 && !visited[x, y])
    {
        visited[x, y] = true;
        return 1 + 
               Recursive(arr, x - 1, y, visited) +
               Recursive(arr, x + 1, y, visited) + 
               Recursive(arr, x, y - 1, visited) +
               Recursive(arr, x, y + 1, visited);
    }
    else
    {
        return 0;
    }                   
}

调用时需初始化访问标记数组：

bool[,] visited = new bool[arr.GetLength(0), arr.GetLength(1)];
Console.WriteLine(Recursive(arr,2,5, visited));

验证结果 #

修改后调用对应递归方法，会返回预期的6，且不会触发栈溢出。

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