Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Quoted from MSDN about StackOverflowException:

The exception that is thrown when the execution stack overflows because it contains too many nested method calls.

Too many is pretty vague here. How do I know when too many is really too many? Thousands of function calls? Millions? I assume that it must be related in some way to the amount of memory in the computer but is it possible to come up with a roughly accurate order of magnitude?

I'm concerned about this because I am developping a project which involves a heavy use of recursive structures and recursive function calls. I don't want the application to fail when I start using it for more than just small tests.

share|improve this question
4  
It's relatively easy to convert a recursive function into a non-recursive function. Just stick your data on a Stack<T>. –  Brian Mar 6 '13 at 22:19
    
How big is "too many" is entirely up to you to define. For .NET, use editbin /stack:WHATEVER-NUMBER-YOU-LIKE yourexefile.exe. –  SK-logic Mar 7 '13 at 8:45
add comment

3 Answers

up vote 27 down vote accepted

I'm concerned about this because I am developping a project which involves a heavy use of recursive structures and recursive function calls. I don't want the application to fail when I start using it for more than just small tests.

Unless your language environment supports tail call optimization (and your recursion is a tail call), a basic rule of thumb is: recursion depth should be guaranteed to be O(log n), i.e. using algorithms or data structures based on divide-and-conquer (like trees, most sorting alogorithms, etc.) is OK, but anything linear (like recursive implementations of linked list handling) is not.

share|improve this answer
3  
+1. Very good answer, I have been implicitly using this rule but I was not aware of it. –  Giorgio Mar 6 '13 at 21:47
    
In this day and age, just about any production-quality compiler worthy of the adjective phrase will support tail call optimization. –  John R. Strohm Mar 6 '13 at 22:13
1  
@JohnR.Strohm However the OP has tagged the question .NET, so AFAIK only the 64-bit jitter does tail call optimization at the moment. –  Mark Hurd Mar 7 '13 at 1:09
1  
Just so there's no confusion, the x86 and x64 both always honor the CIL "tail." instruction prefix. So to summarize, in .NET land, F# does complete tail-call optimization, C# does not, and the x64 jitter does if it's "easy" (it can't be depended on). See blogs.msdn.com/b/clrcodegeneration/archive/2009/05/11/… –  Stephen Swensen Mar 7 '13 at 2:42
1  
True, but in some cases, like in an infamous IIS hosting ASP.NET, even a mere O(log n) recursion depth might fail because of their pathetic, unjustified, laughable tiny stack depth limit, which renders pretty much any recursion (or even a long chain of non-recursive nested calls) impossible. The only way around is to editbin the iis binary itself. –  SK-logic Mar 7 '13 at 8:48
show 3 more comments

By default, the CLR allocates 1 MB to the stack for each thread (see this article). So, it's however many calls it takes to exceed this amount. That will vary depending on how much space on the stack each call is using for things like parameters and local variables.

You can even make it throw a StackOverflowException with a single call if you're willing to be a bit unorthodox:

private static unsafe void BlowUpTheStack()
{
    var x = stackalloc byte[1000000000];
    Console.WriteLine("Oh no, I've blown up the stack!");
}
share|improve this answer
    
Unfortunately, this reasonable default is often violated (e.g., in asp.net). –  SK-logic Mar 7 '13 at 8:50
add comment

Since Cole Campbell noted memory size and Michael Borgwardt noted tail call optimization I won't cover those.

Another thing to be aware of is CPS which can be used to optimize several interwoven functions where tail call optimization is for single functions.

You can increase the size of the stack as we did here, and be aware that 64-bit code eats the stack faster than 32-bit code.

Of note is that we ran one of the examples under F# interactive for more than 40 hours without blowing the stack. Yes it was one function call that ran by itself continuously to successful completion.

Also, if you need to do code coverage to figure out where the problems occur and don't have code coverage with VS you can use, TestDriven.NET

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.