How to avoid a stack overflow?

Question

I compile my code using CSharpCodeProvider, and dynamically create instance of some class in result assembly. Than I call some method. If the method has recursion I get StackOverflowException and my app terminates.

How do I avoid this?

using System;
using System.Runtime.Remoting;
namespace TestStackOverflow
{
    class Program
    {
        class StackOver : MarshalByRefObject
        {
            public void Run()
            {
                Run();
            }
        }

        static void Main(string[] args)
        {
        AppDomain domain = AppDomain.CreateDomain("new");

        ObjectHandle handle = domain.CreateInstance(typeof (StackOver).Assembly.FullName, typeof (StackOver).FullName);
        if (handle != null)
        {
            StackOver stack = (StackOver) handle.Unwrap();
            stack.Run();
        }

    }
}
}

Related:

What is a stack overflow?

Answer 1

StackOverflow indicates that your recursion is going too deep and the stack is running out of memory. For example:

public class StackOver
{
    public void Run() 
    { 
        Run(); 
    }
}

This will result in a stack overflow because StackOver::Run() will be called over and over until there is no memory left.

I suspect in your case, you may be missing a termination condition or you are running too many recursion iterations.

If you are trying to keep the application running, try:

namespace TestStackOverflow
{
    class Program
    {
        class StackOver : MarshalByRefObject
        {
            public bool Run()
            {
                return true; // Keep the application running. (Return false to quit)
            }
        }

        static void Main(string[] args)
        {
            // Other code...

            while (stack.Run());
        }

    }
}

Answer 2

Every time you call a method foo from method bar, bar is added to the call stack. The call stack is used to keep track of where the code was before the method was called so it can return there when foo is done.

The following recursive function

int Factorial(int n) {
    if (n == 0) { return 1; }
    return n * Factorial(n - 1);
}

after several recursions of the call Factorial(5) the call stack would look like this:

Factorial(5) -> Factorial(4) -> Factorial(3) -> Factorial(2) -> Factorial(1)

At this point n is 1, and so the function stops calling the recursive case and instead returns 1. The program then starts winding back up the call stack and the whole thing returns 120.

Without the call stack the program wouldn't know where to go back to when it had finished executing a method.

Now suppose that base case wasn't there, and it was just looked like this:

int Factorial(int n) {
    return n * Factorial(n - 1);
}

After several recursions of the call Factorial(5) the call stack would look like this:

Factorial(5) -> Factorial(4) -> Factorial(3) -> Factorial(2) -> Factorial(1) -> Factorial(0) -> Factorial(-1) -> Factorial(-2) -> Factorial(-3) -> Factorial(-4) -> Factorial(-5) -> Factorial(-6) -> Factorial(-7) -> Factorial(-8) -> Factorial(-9) -> Factorial(-10) -> Factorial(-11) -> Factorial(-12) -> Factorial(-13) -> Factorial(-14) -> Factorial(-15) etc…

Because there is no point at which the code stops calling itself it will carry on forever, and the call stack will grow and grow and grow taking up more and more memory until it exceeds the memory it has been allocated and the StackOverflow exception is thrown.

There are 2 ways to stop this from happening, the best depends on the situation.

1 Provide a base case. Make sure there is some condition that is eventually reached which stops the function from calling itself. In the Factorial case it's that n == 1, but it could be that a certain amount of time has passed, that it has recursed a certain number of times, that some result of some computation is within some bounds, whatever. As long as it stops recusing before the stack is too big.

2 Remove the recursion and re-write it without. Any recursive algorithm can be re-written as a non-recursive algorithm. It may not be as clean and elegant, but it can be done. In the factorial argument it may be something like:

int Factorial(int n) {
    int result = 1;

    for (int i = 0; i < n; i += 1) {
        result *= n;
    }

    return result;
}

If the aim is to continually run the same function again and again, then you can re-write the recursive

void Foo() {
    // Some code
    Foo();
}

as

void Foo() {
    while (true) { // Some code }
}

Answer 3

Run is calling Run. That is the infinite recursion.

    class StackOver : MarshalByRefObject
    {
        public void Run()
        {
            Run(); // Recursive call with no termination
        }
    }

Answer 4

Ok. It doesn't matter use CSharpCodeProvider or not. I'm loading assembly using Reflection in another domain. I think domains was created for security reason. How can I safe the app from terminating???

using System;
using System.Runtime.Remoting;
namespace TestStackOverflow
{
    class Program
    {
        class StackOver : MarshalByRefObject
        {
            public void Run()
            {
                Run();
            }
        }

        static void Main(string[] args)
        {
        AppDomain domain = AppDomain.CreateDomain("new");

        ObjectHandle handle = domain.CreateInstance(typeof (StackOver).Assembly.FullName, typeof (StackOver).FullName);
        if (handle != null)
        {
            StackOver stack = (StackOver) handle.Unwrap();
            stack.Run();
        }

    }
}
}

Answer 5

The only way to avoid stack overflows with recursive functions is to have a clear exit condition that will eventually be met regardless of the input. Either you define a maximum depth and stop making recursive calls once you reach it, or you make sure that the data that you examine is finite (and within reasonable limits), or a combination of both.

Answer 6

I dont have a good background of CSharpCodeProvider but I know that recursively implemented algorithm could be implemented with a loop

Answer 7

If recursion causes a stack overflow, then the problem is not related to compiling the class -- a recursive function needs a terminating condition, because C# doesn't (usually) optimize tail calls.