Using Recursion in C#
How many times you will be able to recurse will depend on:
- The stack size (which is usually 1MB IIRC, but the binary can be hand-edited; I wouldn't recommend doing so)
- How much stack each level of the recursion uses (a method with 10 uncaptured
Guid
local variables will be take more stack than a method which doesn't have any local variables, for example) - The JIT you're using - sometimes the JIT will use tail recursion, other times it won't. The rules are complicated and I can't remember them. (There's a blog post by David Broman back from 2007, and an MSDN page from the same author/date, but they may be out of date by now.)
How to avoid stack overflows? Don't recurse too far :) If you can't be reasonably sure that your recursion will terminate without going very far (I'd be worried at "more than 10" although that's very safe) then rewrite it to avoid recursion.
It really depends on what recursive algorithm you're using. If it's simple recursion, you can do something like this:
public int CalculateSomethingRecursively(int someNumber)
{
return doSomethingRecursively(someNumber, 0);
}
private int doSomethingRecursively(int someNumber, int level)
{
if (level >= MAX_LEVEL || !shouldKeepCalculating(someNumber))
return someNumber;
return doSomethingRecursively(someNumber, level + 1);
}
It's worth noting that this approach is really only useful where the level of recursion can be defined as a logical limit. In the case that this cannot occur (such as a divide and conquer algorithm), you will have to decide how you want to balance simplicity versus performance versus resource limitations. In these cases, you may have to switch between methods once you hit an arbritrary pre-defined limit. An effective means of doing this that I have used in the quicksort algorithm is to do it as a ratio of the total size of the list. In this case, the logical limit is a result of when conditions are no longer optimal.
I am not aware of any hard set to avoid stackoverflows. I personally try to ensure -
1. I have my base cases right.
2. The code reaches the base case at some point.