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.
2
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.
8
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!");
}
1
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