recursive stack size?

Question

class Program  
{
    static void Main(string[] args)
    {
        Test(0);
    }

    static void Test(int i)
    {
        if (i > 30000)
        {
            return;
        }
        Test(i + 1);
    }
}

Why getting recursive function and throwing StackOverflowException when calling this above sample.

(Because over the default recursive stack size ?)

but i wonder how to solve this problem .

Thanks.

Answer 1

You're getting an exception because 30,000 stack frames is a rather large number :-)

You solve it by using recursion in a more circumspect manner. The ideal problems to be solved recursively are those which reduce the "search space" quickly ^(a).

For example, binary tree traversal where your search space is halved each time you recur:

def find (searchkey, node):
    if node = NULL:
        return NULL
    if searchkey = node.key:
        return node
    if searchkey < node.key:
        return find (searchkey, node.left)
    return find (searchkey, node.right)

Adding two unsigned integers (and your own algorithm above) are not a good fit for recursion because you'll blow out your stack allocation long before the results are calculated.:

def add (a, b):
    if a = 0:
        return b
    return add (a-1, b+1)

---

^(a) Search space can be defined as your entire set of possible answers. You want to reduce it as quickly as possible.

And , as an aside, the ideal problems for recursion have nothing to do with stack space in a theoretical/mathematical sense, they're just any problem that can be expressed as:

• the same or similar problem with a "simpler" argument.
• a terminating condition with the "simplest" argument.

("simple" , in this sense, means approaching the terminating condition).

Theoretical/mathemeatical approaches wouldn't need to take stack space into account but we, as computer scientists, must. Reality sets limits :-)

See also When would I not use recursion? and Situations where you would convert recursion to iteration.

Answer 2

The problem is that you are doing too much recursion. Whatever you are doing that would use so many levels of recursion, should be solved using a loop instead.

Algorithms that work will with recursion doesn't use one level of recursion for each item. Typically you would split the work in half for each level, so 30000 items would need only 15 levels of recursion.

Answer 3

You are getting a StackOverflowException because your stack overflows somewhere within those 30k calls to Test. There is no way to 'solve' the problem, the stack size is limited (and pretty small as well). You could redesign your code to work in an iterative fashion.

for( int i = 0; i <= 30000; ++i )
{
    Test( i );
}

However, I assume that your actual use case is more complicated than that; otherwise there is no gain from recursion.

Answer 4

While you could specify the stack size for a new thread manually, I'd use a Stack<T> or a loop (that's really all that's needed for your simplified example) so you don't need recursion at all, i.e.:

Stack<int> stack = new Stack<int>();
stack.Push(1);
while(stack.Count > 0)
{
    int someValue = stack.Pop();
    //some calculation based on someValue
    if(someValue < 30000)
        stack.Push(someValue +1);
}

Answer 5

Take a look at this question: Way to go from recursion to iteration

If your recursion is going to be 30k+ levels deep... you probably want to turn it into an iterative algorithm. The answers in that question should help.