在 C# 中使用递归

Question

使用递归时是否有关于如何避免堆栈溢出的一般规则？

Answer 1

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

• 堆栈大小（通常为 1MB IIRC，但可以手动编辑二进制文件；我不建议这样做）
• 每个递归级别使用多少堆栈（例如，具有 10 个未捕获的

  Guid

  局部变量的方法将比没有任何局部变量的方法占用更多堆栈）
• 您正在使用的 JIT - 有时 JIT 会使用尾递归，有时则不会。规则很复杂，我记不住了。 （有一篇 David Broman 于 2007 年发表的博客文章，以及 同一作者/日期的 MSDN 页面
，但它们现在可能已经过时了。）

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

Answer 2

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

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);
}

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

Answer 3

我不知道有任何“硬集”来避免堆栈溢出。我个人尽力确保 - 1. 我的基本情况是正确的。
2. 代码在某个时刻到达基本情况。

Answer 4

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

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

Answer 5

如果连续调用之间堆栈上剩余的内容不多，则正常限制约为 15000-25000 层深度。如果您使用的是 IIS 6+，则为 25%。

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

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

Answer 6

除了拥有合理的堆栈大小并确保分解并解决问题，以便不断解决较小的问题之外，事实并非如此。

Answer 7

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

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

Answer 8

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

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

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

Answer 9

我在

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

Answer 10

请记住，如果您必须询问系统限制，那么您可能正在做一些严重错误的事情。

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

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