C#递归引发内存不足异常：求解LeetCode K-th Symbol in Grammar遇阻

你的代码触发内存不足异常，核心问题是直接生成了完整的超长字符串。当A=30时，字符串长度为2^(30-1)=536870912，光是这个字符串就需要500MB以上的内存空间，再加上递归过程中产生的大量中间字符串，内存必然撑爆。

问题规律拆解 #

这道题完全不需要生成完整字符串就能得出结果，核心规律如下：

• 第n行的第k个字符，由第n-1行的第(k+1)//2个字符决定（整数除法，向上取整）
• 若k为奇数，则与上一行对应位置字符相同；若k为偶数，则是上一行对应位置字符的反转（0变1，1变0）

换个更直观的角度：每一行的右半部分是左半部分的完全反转，我们只需要不断缩小k所在的区间，判断是否需要反转即可。

优化后的代码 #

递归版本（逻辑清晰，适合理解）

public static int solve(int A, int B)
{
    // 终止条件：第1行只有字符0
    if (A == 1)
        return 0;
    // 计算当前行的中间位置（即上一行的长度）
    int mid = (int)Math.Pow(2, A - 2);
    if (B <= mid)
    {
        // B在左半区，直接取上一行对应位置的结果
        return solve(A - 1, B);
    }
    else
    {
        // B在右半区，取上一行对应位置结果的反转值
        return 1 - solve(A - 1, B - mid);
    }
}

迭代版本（避免递归栈开销，适合更大的A值）

public static int solve(int A, int B)
{
    int result = 0;
    int currentLength = (int)Math.Pow(2, A - 1);
    while (currentLength > 1)
    {
        currentLength /= 2;
        if (B > currentLength)
        {
            // 进入右半区，反转结果
            result = 1 - result;
            B -= currentLength;
        }
        // 左半区无需反转，继续缩小范围
    }
    return result;
}

内存优化原理 #

不管A取值多大，这两个方案都只需要记录当前的位置和反转状态，完全不需要生成任何字符串。内存占用仅为O(1)（迭代版）或O(A)的递归栈深度（A=30时栈深度极小），彻底解决内存溢出问题。

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