递归函数引起溢出，尽管它不是无限

-1

下面的函数我写了导致程序崩溃是由于堆栈溢出，虽然递归是有限的。递归函数引起溢出，尽管它不是无限

public static void Key(char[] chars, int i, int l, string str) { 
    string newStr=null; 

    for(int j=0; j<l; j++) 
     newStr+=chars[i/(int)Math.Pow(68, j)%68]; 

    if(newStr==str) 
     return; 

    Key(chars, ++i, l, newStr); 
}

当我打电话与这些参数的方法，一切顺利的罚款：

Key(chars, 0, 4, "aaaa");

但是，当涉及到呼叫的数量越大，它抛出StackOverflowException。所以我认为问题在于方法是有限的，调用堆栈在方法的工作完成之前被填满。所以我有几个问题：

为什么函数不能从栈中清除，它们不再需要，它们不返回任何值。
如果是这样，有没有办法我可以手动清除堆栈？我尝试了StackTrace类，但在这种情况下它是无助的。

来源

2013-04-05 Nathan Abramov

我得到的印象很深刻，你不明白堆栈是什么或它有什么作用。请仔细研究，您的问题应该自行解答。 – asawyer 2013-04-05 18:46:44

从技术上讲，你的代码是尾递归的，如果你用c＃优化来构建它，你永远不会有堆栈溢出，你应该只是得到一个无限循环（如果你的基本情况实际上永远不会被打）。尝试开启优化，看看你是否仍然堆栈溢出 – devshorts 2013-04-05 18:50:09

也许你应该试图描述你想要完成这个看起来真的不必要的过于复杂 – 2013-04-05 18:55:53

堆栈仍然有限。对于标准的C＃应用程序，它是1 MB。对于ASP，它是256 KB。如果你需要更多的堆栈空间，你会看到异常。

如果您自己创建线程，则可以使用此constructor来调整堆栈大小。

或者，你可以因此跟踪状态，而无需使用递归重写你的算法。

来源

2013-04-05 18:47:01

当downvoting请求者发表评论。谢谢。 – 2013-04-05 19:49:15

它看起来像NewStr == Str的退出条件永远不会发生，最终，您将用完堆栈。

来源

2013-04-05 18:48:58 Metaphor

为什么不会发生？当调用次数小于堆栈可以处理的调用次数时，它就会发生。 – 2013-04-05 18:51:36

@NathanAbramov针对可能输入子集的算法并不能证明它适用于所有可能的输入。 – 2013-04-05 18:54:08

我没有看到问题，为什么它不能用于所有可能的输入？（不管溢出问题） – 2013-04-05 18:57:15

1），当它已经结束执行的功能清除。在本身调用Key意味着每次调用它都会在堆栈中，直到最后一次调用结束，在这个阶段它们将以相反的顺序结束。

2）您不能清除栈和与呼叫矣。

来源

2013-04-05 18:52:17

所以，不管你的代码是否达到其基本情况或没有，你的代码应该永远不会在生产堆栈溢出异常。

例如，这应该给我们一个堆栈溢出吗？

private static void Main(string[] args) 
{ 
    RecursorKey(0); 
} 

public static int RecursorKey(int val) 
{ 
    return RecursorKey(val ++); 
}

事实上，如果您使用.NET 4并且没有进行调试，并且您的二进制文件被编译为发布版，

这是因为clr足够聪明，可以做所谓的tail recursion。尾递归并不适用于任何地方，但就您的情况而言，我很容易就能够重现您的确切问题。就你而言，每次调用函数时都会将另一个stack frame推入堆栈，因此即使该算法在理论上会在某个时间点结束，也会出现溢出。

要解决您的问题，here是您如何启用优化。

但是，我应该指出，Jon Skeet建议不要依赖尾部调用优化。鉴于Jon是个聪明人，我会听他的。如果您的代码将遇到大堆栈深度，请尝试重写它而不递归。

来源

2013-04-05 19:06:49 devshorts

我试图使用优化，但我不明白该怎么做，当我检查优化属性它不会做任何事情。 – 2013-04-05 19:46:30

在发布版本中在Visual Studio之外运行代码。 – devshorts 2013-04-05 19:47:49

我做了，它不会工作 – 2013-04-06 08:09:03

递归函数引起溢出，尽管它不是无限

回答

相关问题