•  03-07-2019
  •  | 
  •  

题

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

有帮助吗？

解决方案

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

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

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

其他提示

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

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

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

我不知道任何硬集以避免堆栈溢出。我个人试图确保 -
我的基本情况是对的。
2.代码在某些时候到达基本情况。

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

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

正常限制，如果在连续呼叫之间的堆栈上没有多少，则大约为15000-25000级别。如果您使用的是IIS 6 +，则为25％。

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

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

除了拥有合理的堆栈大小并确保分裂和克服你的问题，以便你继续处理一个小问题，而不是真的。

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

http：// blogs .msdn.com / abhinaba /存档/ 2007/7月27日/尾递归-ON-net.aspx

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

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

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

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

请记住，如果你不得不询问系统限制，那么你可能正在做一些可怕的错误。

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

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top