16

在使用递归时是否有任何一般规则来避免stackoverflows？

4

10 回答 10

33

您能够递归多少次取决于：

  • 堆栈大小（通常为 1MB IIRC，但二进制文件可以手动编辑；我不建议这样做）
  • 每个级别的递归使用多少堆栈（例如，具有 10 个未捕获的Guid局部变量的方法将比没有任何局部变量的方法占用更多的堆栈）
  • 您正在使用的 JIT - 有时 JIT会使用尾递归，有时则不会。规则很复杂，我不记得了。（David Broman 从 2007 年开始发表博客文章，以及同一作者/日期的 MSDN 页面，但它们现在可能已经过时了。）

如何避免堆栈溢出？不要递归太远 :) 如果你不能合理地确定你的递归会在不走很远的情况下终止（我会担心“超过 10”，尽管这很安全）然后重写它以避免递归。

于 2009-03-04T14:18:24.557 回答
8

这实际上取决于您使用的递归算法。如果它是简单的递归，你可以这样做：

public int CalculateSomethingRecursively(int someNumber)
{
    return doSomethingRecursively(someNumber, 0);
}

private int doSomethingRecursively(int someNumber, int level)
{
    if (level >= MAX_LEVEL || !shouldKeepCalculating(someNumber))
        return someNumber;
    return doSomethingRecursively(someNumber, level + 1);
}

值得注意的是，这种方法实际上只在递归级别可以定义为逻辑限制的情况下才有用。如果这不可能发生（例如分而治之的算法），您将必须决定如何平衡简单性、性能和资源限制。在这些情况下，一旦达到任意预定义的限制，您可能必须在方法之间切换。我在快速排序算法中使用的一种有效方法是将其作为列表总大小的比率。在这种情况下，逻辑限制是条件不再最优的结果。

于 2009-03-04T14:21:42.193 回答
7

我不知道有任何硬性设置可以避免堆栈溢出。我个人尽量确保 -
1. 我的基本情况是正确的。
2. 代码在某个时候达到了基本情况。

于 2009-03-04T14:16:40.023 回答
4

如果您发现自己生成了这么多堆栈帧，您可能需要考虑将递归展开为循环。

特别是如果您正在执行多级递归（A->B->C->A->B...），您可能会发现可以将其中一个级别提取到循环中并为自己节省一些内存。

于 2009-03-04T14:16:58.023 回答
3

正常的限制，如果在连续调用之间的堆栈上没有多少剩余的话，大约是 15000-25000 层深。如果您使用的是 IIS 6+，则为 25%。

大多数递归算法都可以迭代表示。

有多种方法可以增加分配的堆栈空间，但我宁愿让你先找到一个迭代版本。:)

于 2009-03-04T14:18:26.570 回答
1

除了有一个合理的堆栈大小并确保你分而治之，这样你就可以不断地处理一个较小的问题，而不是真的。

于 2009-03-04T14:16:16.590 回答
1

我只是想到了尾递归，但事实证明，C# 不支持它。但是 .Net-Framework 似乎支持它：

http://blogs.msdn.com/abhinaba/archive/2007/07/27/tail-recursion-on-net.aspx

于 2009-03-04T14:22:11.927 回答
1

如果您在默认 CLR 下运行，则线程的默认堆栈大小为 1 MB。但是，其他主机可能会改变这一点。例如，ASP 主机将默认值更改为 256 KB。这意味着您的代码可能在 VS 下运行良好，但在将其部署到真实托管环境时会中断。

幸运的是，当您使用正确的构造函数创建新线程时，您可以指定堆栈大小。根据我的经验，很少有必要，但我见过一个案例，这是解决方案。

您可以编辑二进制文件本身的 PE 标头以更改默认大小。如果您想更改主线程的大小，这很有用。否则，我建议在创建线程时使用适当的构造函数。

于 2009-03-04T15:00:15.440 回答
1

我在这里写了一篇关于这个的短文。基本上，我传递了一个名为 depth 的可选参数，每次深入它时都会给它加 1。在递归方法中，我检查一个值的深度。如果它大于我设置的值，我会抛出异常。该值（阈值）将取决于您的应用程序需求。

于 2011-01-28T11:25:33.210 回答
0

请记住，如果您必须询问系统限制，那么您可能做错了什么。

因此，如果您认为在正常操作中可能会出现堆栈溢出，那么您需要考虑一种不同的方法来解决问题。

将递归函数转换为迭代函数并不难，尤其是在 C# 具有 Generic::Stack 集合的情况下。使用 Stack 类型将使用的内存移动到程序的堆而不是堆栈中。这为您提供了存储递归数据的完整地址范围。如果这还不够，将数据分页到磁盘并不太难。但如果你到了这个阶段，我会认真考虑其他解决方案。

于 2009-03-04T14:29:29.430 回答