Using Recursion in C#

Question

Are there any general rules when using recursion on how to avoid stackoverflows?

fair point- I changed the question from "hard set" to "general" — Ted Smith, Mar 04 '09 at 14:29
I have replied to your comment on my answer, but I don't know if SO will notify you. So do go look at the comments. If SO does notify you, tell me. I'll delete this comment. — batbrat, Mar 04 '09 at 14:46
See this thread -> http://stackoverflow.com/questions/610743 :) — ZombieSheep, Mar 04 '09 at 15:26
@ZombieSheep, that's one of those jokes that takes a few seconds. :) — Michael Meadows, Mar 05 '09 at 18:08
@ZombieSheep: This happen when you write `Recursion` in Google. It says `Did you mean Recursion?`. — Nikhil Agrawal, Jul 24 '12 at 07:46

score 34 · Accepted Answer · edited Jan 20 '19 at 09:44

34

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.

edited Jan 20 '19 at 09:44

valiano

16,433
7
64
79

answered Mar 04 '09 at 14:18

Jon Skeet

1,421,763
867
9,128
9,194

I think that TCO only happens on 64-bit IIRC, for all other cases you need to still prefix the call with tail. And if you dont play with the rules, that might not even be tail called. – leppie Mar 04 '09 at 14:20
@leppie: Exactly the sort of rules I wasn't remembering :) I'll see if I can dig up the blog post on it. – Jon Skeet Mar 04 '09 at 14:24
@Jon here's one I found: http://blogs.msdn.com/davbr/pages/tail-call-jit-conditions.aspx – AwesomeTown Mar 04 '09 at 14:25
The 32-bit section mentions "tail. prefix does not exist in the IL stream" as a reason it won't optimize the tail call; I don't believe the C# compiler ever emits the tail IL (though other compilers like F# may). – AwesomeTown Mar 04 '09 at 14:29
@John Price: the JIT is free to do a tail call even if you do not specify so, as long as it is safe to do so. And thanks for that link (also saw it many moons ago). Oh and F# like Scheme is fully tail recursive. – leppie Mar 04 '09 at 14:48
@Jon, I agree with the last paragraph in your answer. If the logical limit of your recursion is not "knowable" then recursion is very likely the wrong route to take. – Michael Meadows Mar 06 '09 at 04:07
You can also specify an arbitrary stack size when creating a thread. See http://stackoverflow.com/questions/316938/stackoverflowexception-loading-xsltcompiledtransform/316950#316950 – leppie Jan 28 '11 at 11:59

Michael Meadows · Answer 2 · 2009-03-05T19:14:43.293

8

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.

edited Mar 05 '09 at 19:14

answered Mar 04 '09 at 14:21

Michael Meadows

27,796
4
47
63

Although I like this solution, wouldn't it be machine dependant? some systems would be able to handle more levels, and there's no way (no simple way) to determine it at run time. Also, if you're NEEDING that many stack frames, you would be crippling the program with this. – DevinB Mar 05 '09 at 13:14
You're right, but I would argue that the limit should be logical (based on the algorithm), not physical (based on the machine capabilities). Otherwise, you're going to hit the wall if you ever parallelize. – Michael Meadows Mar 05 '09 at 18:06
Also, if it's not a logical limit, then it's really just arbitrary and could result in results of variable preciseness. – Michael Meadows Mar 05 '09 at 18:07

score 7 · Answer 3 · answered Mar 04 '09 at 14:16

7

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.

answered Mar 04 '09 at 14:16

batbrat

5,155
3
32
38

Ok Ted. In recursive functions, there are two parts -1. The part that reduces the problem and calls itself --recursive case. 2.The part that represents the smallest instance of the problem, that has a (usually) trivial answer -base case. – batbrat Mar 04 '09 at 14:39
The recursive calling ends and begins to rewind when a base case is reached. I was trying to say that the base condition should be reached at some point. – batbrat Mar 04 '09 at 14:40
http://en.wikipedia.org/wiki/Recursion_(computer_science) is a good place to look. – batbrat Mar 04 '09 at 14:41
For example factorial(n) = n * (n-1) * ... * 1. Here, the base case is 1 since factorial(1) = 1. Code: factorial(n): if n ==1: return 1 else return factorial(n-1) Note -This is a bad example of using recursion -- tail recursion. Still, it gets the point accross. – batbrat Mar 04 '09 at 14:44
So, unless n=1 is reached by the above code, it will recurse infinitely and cause a stack overflow – batbrat Mar 04 '09 at 14:45

score 4 · Answer 4 · answered Mar 04 '09 at 14:16

4

If you're finding yourself generating that many stack frames, you might want to consider unrolling your recursion into a loop.

Especially if you are doing multiple levels of recursion (A->B->C->A->B...) you might find that you can extract one of those levels into a loop and save yourself some memory.

answered Mar 04 '09 at 14:16

DevinB

8,231
9
44
54

+1, good answer. I've seen tree parsing done in a loop. Was much quicker and stack safe. – Dead account Mar 04 '09 at 15:14

score 4 · Answer 5 · answered Mar 04 '09 at 14:18

The normal limit, if not much is left on the stack between successive calls, is around 15000-25000 levels deep. 25% of that if you are on IIS 6+.

Most recursive algorhitms can be expressed iteratively.

There are various way to increase allocated stack space, but I'll rather let you find an iterative version first. :)

score 1 · Answer 6 · edited Jul 03 '12 at 13:54

1

I wrote a short article about this here. Basically, I pass an optional parameter called, depth, adding 1 to it each time I go deeper into it. Within the recursive method I check the depth for a value. If it is greater than the value I set, I throw an exception. The value (threshold) would be dependent on your applications needs.

edited Jul 03 '12 at 13:54

answered Jan 28 '11 at 11:25

Benjamin

291
3
12

score 1 · Answer 7 · answered Mar 04 '09 at 14:16

1

Other than having a reasonable stack size and making sure you divide and conquer your problem such that you continually work on a smaller problem, not really.

answered Mar 04 '09 at 14:16

Jeff Moser

19,727
6
65
85

score 1 · Answer 8 · answered Mar 04 '09 at 14:22

1

I just thought of tail-recursion, but it turned out, that C# does not support it. However the .Net-Framework seems to support it:

http://blogs.msdn.com/abhinaba/archive/2007/07/27/tail-recursion-on-net.aspx

answered Mar 04 '09 at 14:22

tanascius

53,078
22
114
136

Notice that the produced IL isn't everything that matters. The JIT *does* on occasions perform tail-call optimization on the IL code (see Jon's answer). – Konrad Rudolph Mar 04 '09 at 14:31

score 1 · Answer 9 · answered Mar 04 '09 at 15:00

The default stack size for a thread is 1 MB, if you're running under the default CLR. However, other hosts may change that. For example the ASP host changes the default to 256 KB. This means that you may have code that runs perfectly well under VS, but breaks when you deploy it to the real hosting environment.

Fortunately you can specify a stack size, when you create a new thread by using the correct constructor. In my experience it is rarely necessary, but I have seen one case where this was the solution.

You can edit the PE header of the binary itself to change the default size. This is useful if you want to change the size for the main thread. Otherwise I would recommend using the appropriate constructor when creating threads.

score 0 · Answer 10 · edited Jul 03 '12 at 13:54

Remember, if you have to ask about system limits, then you are probably doing something horribly wrong.

So, if you think you might get a stack overflow in normal operation then you need to think of a different approach to the problem.

It's not difficult to convert a recursive function into an iterative one, especially as C# has the Generic::Stack collection. Using the Stack type moves the memory used into the program's heap instead of the stack. This gives you the full address range to store the recursive data. If that isn't enough, it's not too difficult to page the data to disk. But I'd seriously consider other solutions if you get to this stage.

Using Recursion in C#

10 Answers10

Linked