在进行递归调用之前有没有一种方法可以检查可用的堆栈大小？（C＃）

Question

对于我的 C# AI 程序，我使用递归调用来查找最佳下一步（使用 30x30 的数组来存储当前的棋盘状态）。对于我采取的每个移动，我想看看从新的棋盘状态中我可以做出哪些可能的移动是最好的...以此类推，直到我达到“结束游戏”位置（在该状态下不再有可能的移动）或者计时器停止进程并且没有进行更多的递归调用（并返回“最佳”已知位置）。这只是为了解释为什么我必须使用递归（它不是尾递归），而且我不能使用单个（全局）棋盘状态，但必须搜索所有可能从当前状态开始的棋盘状态。

有时候我会得到 System.StackOverflowException。有没有办法在下一个递归调用之前检查可用的堆栈空间？然后我就可以将当前状态作为“到目前为止找到的最佳位置”返回，并且不进行下一个递归调用。也就是说，当可用的堆栈变得太小时，它也应该被视为基本情况。

当然，另一种选择可能是将每个递归调用放入 try..catch 块中，并通过将其用作基本情况来处理 System.StackOverflowException？

- Chavoux Luyt

---

重新设计你的代码？Stack Overflow 是一个 bug 或糟糕的 (C#) 代码的迹象。你需要大量的递归调用才能引发 Stack Overflow。如果你真的希望这样做，使用支持尾调用的函数式语言，比如 F#。C# 并不适合这种情况。 - Dykam

如果您正在调用递归方法或计划使用大量堆栈空间，则必须使用RuntimeHelpers.ExecuteCodeWithGuaranteedCleanup方法。 - DavidO

Answer 1

实际上，系统会动态扩展堆栈大小，如果现有堆栈空间不足。因此，即使您可以测试堆栈的大小，也无关紧要。http://msdn.microsoft.com/en-us/library/windows/desktop/ms686774(v=vs.85).aspx详细介绍了系统如何从保留的堆栈内存中分配额外的页面，直到堆栈达到保留大小减去一页（用作防止堆栈溢出的守卫页）或系统内存非常低，操作失败为止。这意味着，在递归发生之前，堆栈的大小是固定的；如果递归导致堆栈溢出，则在发生时堆栈的大小将会改变。

由于您无法捕获StackOverflowException，所以您可以使用尾递归而不是终端递归。以下链接提供了将终端递归转换为尾递归的详细信息：http://www.thomaslevesque.com/2011/09/02/tail-recursion-in-c/。

- Peter Ritchie

---

有时候我会遇到 System.StackOverflowException 异常。(可能需要解释一下这是什么意思。) - DavidO

@DavidO，这并不意味着尽管在递归进行时增加了堆栈，但内存已经耗尽以扩展堆栈。 - Peter Ritchie

这取决于当前的棋局。如果答案早期被找到（基本情况早期被找到），那么通常我不会遇到问题。 - Chavoux Luyt

Answer 2

您可以使用队列+循环（Queue<TNode>+while(queue.MoveNext())）代替递归，并限制队列的大小。

或者您可以计算方法的开放调用并以此方式限制递归。 （计算进入和退出次数，如果进入-退出>maxOpenCalls，则不进行递归）。

- Danny Varod

Answer 3

如果你真的想要这样做，你可以使用EnsureSufficientExecutionstack方法。正如其他人指出的那样，从.NET 2.0开始，你无法捕获StackOverflowException异常，不过，从MSDN文档中可以知道上述方法具有以下行为:

确保剩余的堆栈空间足以执行平均.NET Framework函数。

当根据该方法计算的堆栈不够大时，它将抛出一个InsufficientExecutionStackException异常，你可以捕获该异常。

- João Angelo

---

你试过了吗？“确保剩余的堆栈空间足够执行平均 .NET Framework 函数”。在 OP 的情况下，永远不可能有足够的空间 - 这种方法如何“知道”呢？ - Peter Ritchie

每个递归层都要重新检查，对吗？ - DavidO

那部分内容来自MSDN文档，我应该为它添加引用，我会更新答案。正如DavidO指出的那样，为了成为有效的解决方法，检查需要在每个步骤中执行。 - João Angelo

@DavidO 嗯，我想那样做也可以。但是每次调用递归方法都要调用RuntimeHelpers.EnsureSufficientExecutionStack？呸，我只能想象你会受到多大的性能影响... - Peter Ritchie

这看起来像是我想要的，但似乎在VS2005中不可用。我只能尝试另一个算法或限制递归深度。 - Chavoux Luyt

Answer 4

从.NET 2开始，您无法捕获StackOverflowException...

唯一确定已使用多少堆栈的方法是使用不安全代码，我强烈建议不要这样做...最好使用显式基于堆的Stack<T>。

- Yahia

Answer 5

实际上，您可以捕获Stackoverflow异常，当然递归方法必须进行一些协作。您可以创建一个像这样的方法：

void Zoo()
    {
        RuntimeHelpers.EnsureSufficientExecutionStack();
        int[] baba = new int[1024 * 5];
        Zoo();
    }

然后像这样调用它。

 try
        {
            Zoo();
        }
        //catch (Exception ex)
        catch(InsufficientExecutionStackException ex)
        {
            ex.ProcessException().Show("Good God what are you doing");
        }

这就是处理异常的方法运作方式

public static class Helper{

[System.Runtime.InteropServices.DllImport("kernel32.dll")]
    public static extern uint GetCurrentThreadId();

public static string ProcessException(this Exception ex)
    {
        StringBuilder strBuild = new StringBuilder(5000);
        if (ex is InsufficientExecutionStackException)
        {
            strBuild.AppendLine("#%#%#%#%#% We Ran out of Stack Space on thread id : " + GetCurrentThreadId().ToString() + " @ :" + DateTime.Now.ToString() + " #%#%#%#%#%");
            strBuild.AppendLine(ex.Message);
            string[] ribals = ex.StackTrace.Split('\n');
            strBuild.AppendLine(String.Join("\n", ribals.Take(3).ToArray()));
            strBuild.AppendLine("\nLike this you can have many more lines ...\n");
            strBuild.AppendLine("Main issue  found here :\n" + ribals.Last());
            strBuild.AppendLine("#%#%#%#%#% We Ran out of Stack Space on thread id : " + GetCurrentThreadId().ToString() + " @ :" + DateTime.Now.ToString() + " #%#%#%#%#%");
            return strBuild.ToString();
        }
        Exception inner = ex;
        Enumerable.Range(0, 30).All(x =>
        {
            if (x == 0) strBuild.Append("########## Exception begin on thread id : " + GetCurrentThreadId().ToString() + " @ :" + DateTime.Now.ToString() + " ##########\n");
            strBuild.Append("---------------------[" + x.ToString() + "]---------------------\n");
            strBuild.Append("Message : " + inner.Message + "\nStack Trace : " + inner.StackTrace + "\n");
            strBuild.Append("---------------------[" + x.ToString() + "]---------------------\n");
            inner = inner.InnerException;
            if (inner == null)
            {
                strBuild.Append("########## Exception End on thread id : " + GetCurrentThreadId().ToString() + " @ :" + DateTime.Now.ToString() + " ##########\n\n");
                return false;
            }
            return true;
        });
        return strBuild.ToString();
    }
}

- Dr.Sai