在C#中使用递归

Question

在使用递归来避免堆栈溢出时是否有任何一般规则？

Answer 1

你可以多少次递归取决于:

• 堆栈大小(通常为1MB IIRC,但二进制文件可以手工编辑;我不建议这样做)
• 递归的每个级别使用多少堆栈(例如,具有10个未捕获的Guid局部变量的方法将比不具有任何局部变量的方法占用更多堆栈)
• 您正在使用的JIT - 有时JIT 将使用尾递归,有时则不会.规则很复杂,我不记得了.(有一个博客文章由大卫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);
}

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

Answer 3

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