2

I have an algorithm that uses deep recursion. How many levels deep the recursion will go varies and depends on the input. To avoid stack overflow exceptions I keep count of the depth and terminate at a specific depth.

By a bit of experimentation I previously established that a level of 500 was the point at which to stop. However, now suddenly I get stack overflow exceptions at levels just over 300.

Can anyone shed a bit of light on which factors would affect this? Is it e.g. CPU and RAM? Or related to which other processes is running on the computer?

casperOne
  • 73,706
  • 19
  • 184
  • 253
Rask
  • 417
  • 6
  • 9
  • Why do you need to go so deep, if you can "safely" terminate at any arbitrary point? – Anon. Feb 03 '11 at 22:09
  • This doesn't directly answer your question, but F# (unlike C#/VB) supports tail-call recursion, which allows a properly-written recursive algorithm to recurse infinitely deep without ever getting a stack overflow exception. It may be worth writing your algorithm in F#, and calling it from the language you use now. – Joel Mueller Feb 03 '11 at 22:10
  • 2
    @Joel: Nitpick: F# optimizes tail-call recursive calls by effectively converting them to iterative statements (loops)... The other .NET languages still support tail-call recursion, they just do not convert it automatically. See this answer for more detail: http://stackoverflow.com/questions/310974/what-is-tail-call-optimization/310980#310980 – Gabriel Magana Feb 03 '11 at 22:16
  • ... I think if you're going 500 calls deep, you need to rethink your algorithm. –  Feb 03 '11 at 23:14
  • @Anon: I need to go that deep (in a limited number of cases) in order for the algorithm to find its solution. When I "safely terminate" it means that the algorithm would not have found a solution, which is preferable to the application crashing. – Rask Feb 04 '11 at 10:57
  • @Joel @gmagana: Thanks for the info on F# and tail call optimization. That may come in handy in the future. – Rask Feb 04 '11 at 10:59
  • @gmagana - The F# compiler actually emits a `tail.` IL instruction that is directly supported by the CLR. C# and VB do not. What F# does is more than just sneakily rewriting your recursive code into an iterative loop, although it may do that instead of using `tail.` in some cases. See here for some details: http://goo.gl/qT928 – Joel Mueller Feb 04 '11 at 17:17
  • Every recursive algorithm can be converted to an iterative one. Using recursion is expensive because of the stack frame allocated for each call. In case of an iteration you spare that overhead. Convert your implementation to an iteration. – balintn Dec 08 '17 at 01:13

3 Answers3

4

You get a StackOverflowException when you run out of stack space. Calling a method uses some stack space (called a stack frame), as does local variables used during that function. Recursion continually adds new stack frames without popping the old ones off (unless you're employing tail-call optimization, which C# doesn't do too well at).

Therefore, exactly when this will occur is dependent upon the number of method calls as well as what you're doing inside these methods.

casperOne
  • 73,706
  • 19
  • 184
  • 253
MikeP
  • 7,829
  • 33
  • 34
  • Thank you for your answer. I think to frame my question slightly differently then, how much stack space do I have and what factors can affect how much? – Rask Feb 04 '11 at 10:26
2

This Explaination is the basic reason behind StackOverflowException for languages java, C, C++.

Stackoverflow exception is caused genrally in any language due to recursive method calls.

Suppose you have an method which is calling itself or any other method for an infinite recursive loop then it will cause a Stacoverflowexception. The reason behind this is the method call stack gets filled and it wont be able to accommodate any other method call.

Method call stack looks like this picture.

enter image description here

Explanation -- Suppose Main method has five statements And third method has an call to methodA, then the execution of main method gets paused at statement3 and MethosA will be loaded into call stack. Then method A has a call to methodB. So methodB also gets loaded into the stack.

So in this way infinite recursive calls makes call stack getting filled. So it cant afford any more methods. So it throws StackOverflowException.

Nikhil Agrawal
  • 26,128
  • 21
  • 90
  • 126
1

The answer varies, see here: Stack capacity in C#

You would be wise to change your algorithm to not be recursive, it will not be easy to see how much you can recurse, and basically you are tempting fate if you attempt to predict a certian level of recursion depth. That and whatever estimation algorithm you use for the stack depth might break with the next .NET service pack.

Community
  • 1
  • 1
Gabriel Magana
  • 4,338
  • 24
  • 23