How many are too many nested function calls?

Question

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.

It's relatively easy to convert a recursive function into a non-recursive function. Just stick your data on a `Stack`. — Brian, Mar 06 '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 07 '13 at 08:45

Michael Borgwardt · Accepted Answer · 2013-03-07T07:59:31.767

29

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.

edited Mar 07 '13 at 07:59

answered Mar 06 '13 at 21:04

Michael Borgwardt

51,037
13
124
176

3

+1. Very good answer, I have been implicitly using this rule but I was not aware of it. – Giorgio Mar 06 '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 06 '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 07 '13 at 01: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 http://blogs.msdn.com/b/clrcodegeneration/archive/2009/05/11/tail-call-improvements-in-net-framework-4.aspx – Stephen Swensen Mar 07 '13 at 02:42
@JohnR.Strohm you'd hope, and yet neither Java nor C# do tail call optimization (though, as Mark Hurd pointed out, the x64 jitter will *sometimes* do it for C# and other .NET languages that don't do it themselves) – Stephen Swensen Mar 07 '13 at 02:45
@John R. Strohm: Languages like Java or C# do not have a strong need for tail-call optimization because when you want to linearly scan a collection of objects you use a plain old loop. Tail-call optimization is needed more strongly in languages like Scheme or Haskell that use recursion in this case (and, indeed, Haskell has no loops). Normally, I think it is OK if a language provides only one metaphor for a specific class of tasks. – Giorgio Mar 07 '13 at 08:24
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 07 '13 at 08:48
@SK-logic: It's not even configurable? That's nasty... – Michael Borgwardt Mar 07 '13 at 09:51

score 17 · Answer 2 · answered Mar 06 '13 at 20:58

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!");
}

Unfortunately, this reasonable default is often violated (e.g., in asp.net). — SK-logic, Mar 07 '13 at 08:50

score 2 · Answer 3 · edited Apr 12 '17 at 07:31

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

How many are too many nested function calls?

3 Answers3