CODEWITHSUNDEEP
c#recursionstackartificial-intelligencestack-overflow
Chavoux Luyt
Chavoux Luyt

Reputation: 113

Is there a way to check available stack size before recursive call? (C#)

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?

Upvotes: 11

Views: 4707

Answers (5)

Dr.Sai
Dr.Sai

Reputation: 393

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();
    }
}

Upvotes: -1

João Angelo
João Angelo

Reputation: 57718

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.

Upvotes: 2

Peter Ritchie
Peter Ritchie

Reputation: 35869

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/

Upvotes: 2

Yahia
Yahia

Reputation: 70379

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>.

Upvotes: 1

Danny Varod
Danny Varod

Reputation: 18098

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).

Upvotes: 2

Related Questions