c# - 递归堆栈大小？

Question

class Program  
{
    static void Main(string[] args)
    {
        Test(0);
    }

    static void Test(int i)
    {
        if (i > 30000)
        {
            return;
        }
        Test(i + 1);
    }
}

为什么在调用上述示例时获取递归函数并抛出 StackOverflowException。

(因为超过了默认的递归堆栈大小？)

但我想知道如何解决这个问题。

谢谢。

Answer 1

你得到一个异常，因为 30,000 个堆栈帧是一个相当大的数字:-)

您通过以更谨慎的方式使用递归来解决它。递归解决的理想问题是那些快速减少“搜索空间”的问题^(a)。

例如，每次重复时搜索空间减半的二叉树遍历:

def find (searchkey, node):
    if node = NULL:
        return NULL
    if searchkey = node.key:
        return node
    if searchkey < node.key:
        return find (searchkey, node.left)
    return find (searchkey, node.right)

相加两个无符号整数(以及上面您自己的算法)不适合递归，因为您会在计算结果之前很久就耗尽堆栈分配。:

def add (a, b):
    if a = 0:
        return b
    return add (a-1, b+1)

---

^(a) 搜索空间可以定义为您的整组可能答案。您希望尽快减少它。

顺便说一句，递归的理想问题在理论/数学意义上与堆栈空间无关，它们只是可以表示为的任何问题:

• 具有“更简单”论证的相同或相似问题。
• 带有“最简单”参数的终止条件。

(“简单”，在这个意义上，意味着接近终止条件)。

理论/数学方法不需要考虑堆栈空间，但作为计算机科学家，我们必须考虑。现实设定了限制:-)

另见 When would I not use recursion?和 Situations where you would convert recursion to iteration .