在 C# 中使用递归
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/610743/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Using Recursion in C#
提问by Ted Smith
Are there any general rules when using recursion on how to avoid stackoverflows?
使用递归时是否有关于如何避免堆栈溢出的一般规则？
采纳答案by Jon Skeet
How many times you will be able to recurse will depend on:
您可以递归多少次取决于：
- The stack size (which is usually 1MB IIRC, but the binary can be hand-edited; I wouldn't recommend doing so)
- How much stack each level of the recursion uses (a method with 10 uncaptured
Guidlocal variables will be take more stack than a method which doesn't have any local variables, for example) - The JIT you're using - sometimes the JIT willuse tail recursion, other times it won't. The rules are complicated and I can't remember them. (There's a blog post by David Broman back from 2007, and an MSDN page from the same author/date, but they may be out of date by now.)
- 堆栈大小（通常为 1MB IIRC，但可以手动编辑二进制文件；我不建议这样做）
- 递归的每个级别使用多少堆栈（例如，具有 10 个未捕获
Guid局部变量的方法将比没有任何局部变量的方法占用更多堆栈） - 您正在使用的 JIT - 有时 JIT会使用尾递归，有时则不会。规则很复杂，我记不清了。（David Broman 于 2007 年发表了一篇博文，还有一个来自同一作者/日期的 MSDN 页面，但它们现在可能已经过时了。）
How to avoid stack overflows? Don't recurse too far :) If you can't be reasonably sure that your recursion will terminate without going very far (I'd be worried at "more than 10" although that's very safe) then rewrite it to avoid recursion.
如何避免堆栈溢出？不要递归太远:) 如果你不能合理地确定你的递归会在不走很远的情况下终止（我会担心“超过 10 个”虽然这很安全）然后重写它以避免递归。
回答by Jeff Moser
Other than having a reasonable stack size and making sure you divide and conquer your problem such that you continually work on a smaller problem, not really.
除了拥有合理的堆栈大小并确保您分而治之，以便您继续解决较小的问题，而不是真正的问题。
回答by batbrat
I am not aware of any hard setto avoid stackoverflows. I personally try to ensure -
1. I have my base cases right.
2. The code reaches the base case at some point.
我不知道有什么硬设置可以避免计算器溢出。我个人尽量确保 -
1. 我的基本情况是正确的。
2. 代码在某个时候达到了基本情况。
回答by DevinB
If you're finding yourself generating that many stack frames, you might want to consider unrolling your recursion into a loop.
如果您发现自己生成了那么多堆栈帧，您可能需要考虑将递归展开为一个循环。
Especially if you are doing multiple levels of recursion (A->B->C->A->B...) you might find that you can extract one of those levels into a loop and save yourself some memory.
尤其是如果您正在执行多个级别的递归（A->B->C->A->B...），您可能会发现可以将其中一个级别提取到循环中并为自己节省一些内存。
回答by leppie
The normal limit, if not much is left on the stack between successive calls, is around 15000-25000 levels deep. 25% of that if you are on IIS 6+.
如果在连续调用之间堆栈上没有多少剩余，正常限制是大约 15000-25000 级深。如果您使用的是 IIS 6+，则为其中的 25%。
Most recursive algorhitms can be expressed iteratively.
大多数递归算法都可以迭代地表达。
There are various way to increase allocated stack space, but I'll rather let you find an iterative version first. :)
有多种方法可以增加分配的堆栈空间，但我宁愿让您先找到一个迭代版本。:)
回答by Michael Meadows
It really depends on what recursive algorithm you're using. If it's simple recursion, you can do something like this:
这实际上取决于您使用的递归算法。如果是简单的递归，您可以执行以下操作：
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);
}
It's worth noting that this approach is really only useful where the level of recursion can be defined as a logical limit. In the case that this cannot occur (such as a divide and conquer algorithm), you will have to decide how you want to balance simplicity versus performance versus resource limitations. In these cases, you may have to switch between methods once you hit an arbritrary pre-defined limit. An effective means of doing this that I have used in the quicksort algorithm is to do it as a ratio of the total size of the list. In this case, the logical limit is a result of when conditions are no longer optimal.
值得注意的是，这种方法实际上仅在递归级别可以定义为逻辑限制的情况下才有用。如果这不可能发生（例如分治算法），您将必须决定如何平衡简单性与性能与资源限制。在这些情况下，一旦达到任意的预定义限制，您可能必须在方法之间切换。我在快速排序算法中使用的一种有效方法是将其作为列表总大小的比率。在这种情况下，逻辑限制是条件不再是最佳时的结果。
回答by tanascius
I just thought of tail-recursion, but it turned out, that C# does not support it. However the .Net-Framework seems to support it:
我只是想到了尾递归，但事实证明，C# 不支持它。然而 .Net-Framework 似乎支持它：
http://blogs.msdn.com/abhinaba/archive/2007/07/27/tail-recursion-on-net.aspx
http://blogs.msdn.com/abhinaba/archive/2007/07/27/tail-recursion-on-net.aspx
回答by Skizz
Remember, if you have to ask about system limits, then you are probably doing something horribly wrong.
请记住，如果您必须询问系统限制，那么您可能做错了什么。
So, if you think you might get a stack overflow in normal operation then you need to think of a different approach to the problem.
因此，如果您认为在正常操作中可能会出现堆栈溢出，那么您需要考虑另一种解决问题的方法。
It's not difficult to convert a recursive function into an iterative one, especially as C# has the Generic::Stack collection. Using the Stack type moves the memory used into the program's heap instead of the stack. This gives you the full address range to store the recursive data. If that isn't enough, it's not too difficult to page the data to disk. But I'd seriously consider other solutions if you get to this stage.
将递归函数转换为迭代函数并不困难，尤其是当 C# 具有 Generic::Stack 集合时。使用 Stack 类型将使用的内存移动到程序的堆而不是堆栈中。这为您提供了存储递归数据的完整地址范围。如果这还不够，将数据分页到磁盘并不太困难。但如果你到了这个阶段，我会认真考虑其他解决方案。
回答by Brian Rasmussen
The default stack size for a thread is 1 MB, if you're running under the default CLR. However, other hosts may change that. For example the ASP host changes the default to 256 KB. This means that you may have code that runs perfectly well under VS, but breaks when you deploy it to the real hosting environment.
如果您在默认 CLR 下运行，则线程的默认堆栈大小为 1 MB。但是，其他主机可能会改变这一点。例如，ASP 主机将默认值更改为 256 KB。这意味着您的代码可能在 VS 下运行良好，但在将其部署到真实托管环境时会中断。
Fortunately you can specify a stack size, when you create a new thread by using the correct constructor. In my experience it is rarely necessary, but I have seen one case where this was the solution.
幸运的是，当您使用正确的构造函数创建新线程时，您可以指定堆栈大小。根据我的经验，很少有必要这样做，但我见过一个案例，这是解决方案。
You can edit the PE header of the binary itself to change the default size. This is useful if you want to change the size for the main thread. Otherwise I would recommend using the appropriate constructor when creating threads.
您可以编辑二进制文件本身的 PE 标头以更改默认大小。如果您想更改主线程的大小，这很有用。否则我会建议在创建线程时使用适当的构造函数。
回答by Benjamin
I wrote a short article about this here. Basically, I pass an optional parameter called, depth, adding 1 to it each time I go deeper into it. Within the recursive method I check the depth for a value. If it is greater than the value I set, I throw an exception. The value (threshold) would be dependent on your applications needs.
我在这里写了一篇关于此的简短文章。基本上，我传递了一个名为depth 的可选参数，每次我深入研究它时都会给它加1。在递归方法中，我检查一个值的深度。如果它大于我设置的值，我会抛出异常。该值（阈值）将取决于您的应用程序需求。
