19

In many functional languages using a recursion is considered to be a good practice. I think it is good because of the way compiler optimizes functional language's code.

But is it a good practice to use recursion in C#, when creating an algorithm? Is it right to say in regards to C#, that recursive algorithms will result in your stack growing quite dramatically (if the amount of calls is very big) and this won't be any fast at all, and might result in stack overflow. Or there are also some optimization happening to make recursive functions efficient?

I would appreciate if you would give some comparison (speed, memory, readability) between algorithms which uses recursion in Functional languages and C#.

Improve this question
2
  • 5
    At the very least, use recursion when it makes sense (and you can, i.e. when it won't result in stack overflow) - e.g. for tree traversal and for algorithms that get very ugly/complex when converted into iteration. Commented Oct 21, 2010 at 9:49
  • stackoverflow.com/questions/491376/… Commented Jan 23, 2011 at 15:10

5 Answers 5

Reset to default
16

Not using recursion will anyway cause you to rewrite your algorithm using your own "Stack", which will eventually be subjected to similar conditions while execution.

You can customize stack size based on need of your algorithm, but if you look at WPF/Silverlight and normal UI related algorithms, they all are recursive in nature and every click, every key press and every notifications go through lot of recursive methods.

Check out Creating Thread with Custom Stack Size,

Although the speed may vary depending upon the algorithm and complexity, but creating separate non recursive algorithm will make task more complex as you will be doing all data store operations by yourself using lists, stacks etc.

This is quite design vs performance issue, if you want better performance, then your non recursive algorithm will execute faster, but it will take longer to design and implement such algorithm. Where else if you want a quicker solution then you can write recursive algorithm that will be slower in execution but if the difference is only few milliseconds or microseconds then its not worth doing it.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

-1 for completely missing the point. The problem with recursion in C# is that whichever stack size you decide on, you can still recurse beyond it. Recursion (which we understand as a function which directly or indirectly calls itself) is in the general case unbounded: You don't know ahead of time how deep the recursion is going to be.
@harms, that is obvious and everyone knows it, where else if stackoverflow occurs, it can even occur in your non recursive algorithms too considering every call will need some sort of pushing state of algorithm on stack, queue or list and that can overgrow too.
+1 for pointing out that algorithm state has to go somewhere.
I don't know why people are saying that the non recursion variant will be subject to limitation. A while(true) loop can run an unbounded number of iterations. The same is not true of a recursive loop.
6

Loop always outperfroms recursion since stack always has more overhead than your state. A lot of threading operations heavily walk the stack so you get further decline.

However, readability is a big plus so I will personally use recursion unless I need every drop of perfromance such as in image processing operations or I expect my stacks to grow very large - although stack overflow almost exclusively due to bugs.

Improve this answer

3 Comments

So if there are no infinite loops in your algorithms you won't run out of stack memory, even though that C# doesn't reuse function's stack frame when creating a recursive call?
No... And yes. If language supports tail-call recursion, then there is no stack beyond first call (which exists in the iterative version as well). C# is not such a language so iterative version will be more memory/speed-efficient.
Actually, while C# doesn't explicitly support tail recursion, the optimizer attempts to use it in place of standard recursion if there's no further work to do after the recursive call. I ran into this trying to reproduce a bug in this question: stackoverflow.com/questions/3915636/… Relying on this behaviour wouldn't be advised.
5

In Microsoft's current implementation of the C# compiler, tail call optimizations are not made. This makes functional algorithms which recurse deeply overflow the stack. While I would not recommend using deeply recursive algorithms in C#, methods that do not recurse deeply should not cause you any problem at all.

Improve this answer

3 Comments

almost but not quite correct. See my comment to @Aliostad's answer.
Tail call optimization is only done when you do not compile for 32-bit CPUs explicitly. community.bartdesmet.net/blogs/bart/archive/2010/07/07/…
i think they key is that tail optimizations aren't "guaranteed"
2

The reason recursion in functional languages is good practice isn't because of tail recursion optimizations; it's good practice because it's a powerful, simple way of expressing a lot of algorithms. The optimizations are just gravy, and anyway tail call optimizations aren't relevant to all recursive functions.

So with that in mind, it's perfectly great practice to build recursive methods in c#, if that's the most natural way of expressing your algorithm. Obviously, if it turns out to have stack depth issues, it might make sense to make it iterative. But to take a naturally recursive algorithm and make it iterative without first knowing it's an issue is premature optimization, and could make your code unnecessarily complicated and hard to read in exchange for little performance gain.

Improve this answer

Comments

1

When you need recursion, you need it, like for depth-first tree walking, or recursive-descent parsing.

If you have a choice, like using recursion instead of a loop, then maybe it's a function of what language you're in. Keep it simple.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.