10

For a C# AI program I use a recursive call to find the best next move (using a 30x30 Array to store the current board state). For each move I make, I want to see which of the possible moves I can make from the new board state will be best... and so on until I either reach an "end of game" position (no further moves possible in that state) or a timer stops the process and no further recursive calls are made (and the "best" known position is returned). This just to explain why I must use recursion (it is not tail recursion) and I cannot use a single (global) board state, but must search all board states possible from the current state.

(Sometimes) I get a System.StackOverflowException. Is there a way to check the available stack space before the next recursive call? Then I could just return the current state as a "best position found so far" and not make the next recursive call. I.e. when the available stack becomes too small it should also count as a base case.

The other option of course, may be to just put each recursive call in a try..catch block and handle the System.StackOverflowException by using it as a base case?

Chavoux Luyt
  • 103
  • 1
  • 6
  • 5
    Redesign your code? A stackoverflow is a sign of a bug or bad (C#) code. You need an insane amount of recursive calls to trigger an stackoverflow. Use a functional language supporting tail-calls, like F#, if you really want to do it this way. C# is not designed for it. – Dykam Sep 09 '12 at 15:58
  • "If you are calling a recursive method or plan to use a lot of stack space, you must use the RuntimeHelpers.ExecuteCodeWithGuaranteedCleanup method." -- http://msdn.microsoft.com/en-us/library/system.runtime.compilerservices.runtimehelpers.probeforsufficientstack.aspx – DavidO Sep 09 '12 at 16:16

5 Answers5

2

Actually, the system will expand the stack size dynamically, should it run out of space on the existing stack. So, even if you could test the size of the stack, it wouldn't really matter.

http://msdn.microsoft.com/en-us/library/windows/desktop/ms686774(v=vs.85).aspx details

The system commits additional pages from the reserved stack memory as they are needed, until either the stack reaches the reserved size minus one page (which is used as a guard page to prevent stack overflow) or the system is so low on memory that the operation fails".

Which is saying that, before the recursion occurs, the stack is one size; and if the recursion causes a stack overflow, the stack is a new size when that happened.

Since you can't catch the StackOverflowException, instead of terminal recursion, you could use tail recursion. The following link provides some good detail on converting terminal recusion into tail recusion: http://www.thomaslevesque.com/2011/09/02/tail-recursion-in-c/

Peter Ritchie
  • 35,463
  • 9
  • 80
  • 98
  • "(Sometimes) I get a System.StackOverflowException." (Might be useful to explain that.) – DavidO Sep 09 '12 at 15:57
  • @DavidO, that's not to say that despite increasing the stack while the recursion is going on, it ran out of memory to expand the stack. – Peter Ritchie Sep 09 '12 at 15:58
  • It depends on the current board position. If the answer is found early enough (base case found early), I normally don't get the problem. – Chavoux Luyt Sep 10 '12 at 13:57
2

You could use a queue + loop (Queue<TNode> + while (queue.MoveNext())) instead of recursion and limit the size of the queue.

Or you could count open calls to the method and limit the recursion in that manner. (Count entries and exits and don't enter recursion if entries - exists > maxOpenCalls).

Danny Varod
  • 17,324
  • 5
  • 69
  • 111
2

If you really want to go down that path you can use EnsureSufficientExecutionstack method.

As others pointed out, starting with .NET 2.0 you cannot catch a StackOverflowException, however, from the MSDN documentation you know the previous method has the following behavior:

Ensures that the remaining stack space is large enough to execute the average .NET Framework function.

When the stack is not large enough according to this method then it will throw an InsufficientExecutionStackException exception that you can catch.

John Cummings
  • 1,949
  • 3
  • 22
  • 38
João Angelo
  • 56,552
  • 12
  • 145
  • 147
  • Have you tried that? "Ensures that the remaining stack space is large enough to execute the average .NET Framework function". In the OPs case can never be enough space--how would this method *known* that? – Peter Ritchie Sep 09 '12 at 16:11
  • Each recursion level would have to check anew, no? – DavidO Sep 09 '12 at 16:14
  • That part is from the MSDN documentation, I should have add a quote for it, I'll update the answer. As DavidO pointed out, the check would need to be performed at each step in order to be a valid workaround. – João Angelo Sep 09 '12 at 16:16
  • @DavidO Hmm, I guess that would do. But a call to `RuntimeHelpers.EnsureSufficientExecutionStack` on each call to a the recursive method? Yuck, I can only imagine the performance hit you'd get... – Peter Ritchie Sep 09 '12 at 16:16
  • If performance is an issue recursion probably wouldn't be the tool of choice. Anyway, I think that's the answer if the code can't be refactored to an iterative approach, or if the recursion can't be reigned in at an earlier stage. – DavidO Sep 09 '12 at 16:19
  • See also this (also left in a comment under the OP):"If you are calling a recursive method or plan to use a lot of stack space, you must use the RuntimeHelpers.ExecuteCodeWithGuaranteedCleanup method." -- http://msdn.microsoft.com/en-us/library/system.runtime.compilerservices.runtimehelpers.probeforsufficientstack.aspx – DavidO Sep 09 '12 at 16:20
  • @DavidO, if a `StackOverflowException` is thrown the process is terminated, so that method is not an option. – João Angelo Sep 09 '12 at 16:25
  • This looks like what I want, but it doesn't seem to be available in VS2005. I will just have to try another algorithm or restrict recursion depth. – Chavoux Luyt Sep 10 '12 at 14:41
1

Starting with .NET 2 you CANNOT catch StackOverflowException...

The only way to determine how much of your stack is already used means to use unsafe code which I strongly advise against... better use an explicit heap-based Stack<T>.

Yahia
  • 69,653
  • 9
  • 115
  • 144
-1

Actually you can catch the Stackoverflow execption, ofcourese the recursive method must do some cooperate You make a method like this:

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

Then call it like this

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

And this how process exception method works

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
  • 303
  • 4
  • 5