0

我编写的以下函数导致程序由于堆栈溢出而崩溃,尽管递归是有限的。

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. 所以我认为问题是尽管方法是有限的,但调用堆栈在方法的工作完成之前就被填满了。所以我对此有几个问题:

  1. 为什么函数没有从堆栈中清除,它们不再需要,它们不返回任何值。

  2. 如果是这样,有没有办法我可以手动清除堆栈?我尝试了这StackTrace门课,但在这种情况下它是无助的。

4

4 回答 4

2

1) 函数在结束执行后清零。在自身内部调用 Key 意味着对它的每次调用都将在堆栈上,直到最后一次调用结束,在此阶段它们都将以相反的顺序结束。

2)您无法清除堆栈并继续调用。

于 2013-04-05T18:52:17.137 回答
1

So, regardless of whether your code reaches its base case or not, your code should never get a stack overflow exception in production.

For example, this should give us a stack overflow right?

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

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

In fact it doesn't, if you use .NET 4 and are not debugging and your binary is compiled as release.

This is because the clr is smart enough to do what is called tail recursion. Tail recursion isn't applicable everywhere, but in your case it is, and I was easily able to reproduce your exact problem. In your case, each time you call the function it pushes another stack frame onto the stack, so you get the overflow, even though the algorithm would theoretically end at some point.

To solve your issue, here is how you can enable optimizations.

However, I should point out that Jon Skeet recommends to not rely on tail call optimizations. Given that Jon's a smart guy, I'd listen to it him. If your code is going to encounter large stack depths, try rewriting it without recursion.

于 2013-04-05T19:06:49.330 回答
1

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

如果您自己创建线程,则可以使用此构造函数调整堆栈大小。

或者,您可以重写您的算法,以便在不使用递归的情况下跟踪状态。

于 2013-04-05T18:47:01.490 回答
1

看起来 NewStr == Str 的退出条件永远不会发生,最终你会用完堆栈。

于 2013-04-05T18:48:58.060 回答