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

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

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

（因为超过了默认的递归堆栈大小？）

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

谢谢。

4

5 回答 5

6

你得到一个例外，因为 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)搜索空间可以定义为您的整个可能答案集。你想尽快减少它。

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

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

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

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

另请参阅何时不使用递归？以及将递归转换为迭代的情况。

于 2011-09-24T23:23:48.523 回答
5

问题是你做了太多的递归。无论您在做什么，都会使用如此多的递归级别，应该使用循环来解决。

适用于递归的算法不会对每个项目使用一个递归级别。通常，您会将每个级别的工作分成两半，因此 30000 个项目只需要 15 个级别的递归。

于 2011-09-24T23:23:10.597 回答
2

你得到一个StackOverflowException，因为你的堆栈在这 30k 调用中的某处溢出Test。没有办法“解决”这个问题，堆栈大小是有限的（而且非常小）。您可以重新设计代码以迭代方式工作。

for( int i = 0; i <= 30000; ++i )
{
    Test( i );
}

但是，我假设您的实际用例比这更复杂；否则递归没有任何好处。

于 2011-09-24T23:23:15.510 回答
2

虽然您可以手动指定新线程的堆栈大小，但我会使用 aStack<T>或循环（这实际上是您的简化示例所需要的全部），因此您根本不需要递归，即：

Stack<int> stack = new Stack<int>();
stack.Push(1);
while(stack.Count > 0)
{
    int someValue = stack.Pop();
    //some calculation based on someValue
    if(someValue < 30000)
        stack.Push(someValue +1);
}
于 2011-09-24T23:27:18.747 回答
1

看看这个问题：从递归到迭代的方法

如果您的递归深度将达到 30k+ 级……您可能希望将其转换为迭代算法。该问题的答案应该有所帮助。

于 2011-09-24T23:26:16.650 回答