递归函数Stack Overflow问题排查及代码优化咨询

核心优化方向：减少无效递归+替代系统栈 #

1. 标记已处理格子，彻底避免重复递归调用 #

• 在调用Reveal前新增一个布尔数组isRevealed，检查当前格子是否已被展开，若已处理直接返回，杜绝重复递归：

// 假设棋盘大小为ROWS x COLS
bool isRevealed[ROWS][COLS] = {false};

void SUPERreveal(int row, int col) {
    if (row < 0 || row >= ROWS || col < 0 || col >= COLS || isRevealed[row][col]) {
        return;
    }
    isRevealed[row][col] = true;
    Reveal(row, col);

    // 仅当当前格子无周围地雷时，继续处理周边
    if (getAdjacentMineCount(row, col) == 0) {
        // 遍历8个方向
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if (i == 0 && j == 0) continue;
                SUPERreveal(row + i, col + j);
            }
        }
    }
}

• 这一步能大幅减少递归次数，尤其针对大面积空白棋盘的场景，避免重复处理同一个格子。

2. 用自定义栈实现迭代式DFS，完全替代系统栈 #

• 若递归深度仍然超出系统栈限制，无需大幅修改Reveal逻辑，仅将SUPERreveal的递归改为迭代，用自定义栈存储待处理的格子坐标：

typedef struct {
    int row;
    int col;
} Cell;

void SUPERreveal(int startRow, int startCol) {
    // 可根据棋盘大小调整栈的容量，或用动态分配
    Cell stack[ROWS * COLS];
    int top = -1;

    // 初始格子入栈
    stack[++top] = (Cell){startRow, startCol};
    isRevealed[startRow][startCol] = true;

    while (top >= 0) {
        Cell curr = stack[top--];
        int row = curr.row;
        int col = curr.col;

        Reveal(row, col);

        // 空白格子才需要处理周边
        if (getAdjacentMineCount(row, col) == 0) {
            for (int i = -1; i <= 1; i++) {
                for (int j = -1; j <= 1; j++) {
                    if (i == 0 && j == 0) continue;
                    int newRow = row + i;
                    int newCol = col + j;
                    // 检查坐标合法且未被处理
                    if (newRow >= 0 && newRow < ROWS && newCol >=0 && newCol < COLS && !isRevealed[newRow][newCol]) {
                        isRevealed[newRow][newCol] = true;
                        stack[++top] = (Cell){newRow, newCol};
                    }
                }
            }
        }
    }
}

• 这种方式完全脱离系统栈的限制，不管多大的空白区域都不会触发栈溢出，且仅修改SUPERreveal的调用逻辑，Reveal函数可以原封不动保留。

3. 递归深度兜底限制（临时过渡方案） #

• 如果暂时不想改成迭代，可以给递归函数加深度计数器，当超过预设阈值（比如1000）时，切换为迭代处理剩余格子：

#define MAX_RECURSION_DEPTH 1000

void SUPERrevealHelper(int row, int col, int depth) {
    if (row <0 || row >= ROWS || col <0 || col >= COLS || isRevealed[row][col]) {
        return;
    }
    isRevealed[row][col] = true;
    Reveal(row, col);

    if (getAdjacentMineCount(row, col) == 0) {
        if (depth >= MAX_RECURSION_DEPTH) {
            // 触发迭代处理当前格子的周边
            Cell stack[ROWS * COLS];
            int top = -1;
            for (int i = -1; i <=1; i++) {
                for (int j = -1; j <=1; j++) {
                    if (i==0 && j==0) continue;
                    int r = row+i, c=col+j;
                    if (r >=0 && r < ROWS && c >=0 && c < COLS && !isRevealed[r][c]) {
                        stack[++top] = (Cell){r, c};
                    }
                }
            }
            // 处理栈中剩余格子
            while (top >=0) {
                Cell curr = stack[top--];
                SUPERrevealHelper(curr.row, curr.col, 0); // 重置深度重新递归
            }
            return;
        }
        // 继续递归
        for (int i = -1; i <=1; i++) {
            for (int j = -1; j <=1; j++) {
                if (i==0 && j==0) continue;
                SUPERrevealHelper(row+i, col+j, depth+1);
            }
        }
    }
}

// 对外调用接口
void SUPERreveal(int row, int col) {
    memset(isRevealed, 0, sizeof(isRevealed));
    SUPERrevealHelper(row, col, 0);
}

额外注意事项 #

• 确保getAdjacentMineCount函数的逻辑高效，避免在递归中重复计算周边地雷数，可提前预计算所有格子的地雷数并存储在数组中。

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