In C# is it a good practice to use recursive functions in algorithms?

Question

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#.

Answer 1

http://stackoverflow.com/questions/491376/why-doesnt-net-c-eliminate-tail-recursion

Answer 2

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.

Answer 3

Hi,

Here this post Recursive iterator performance explaining the difference between recursive version vs non-recursive operation in detail. Results are interesting. Check out

Cheers

Answer 4

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 seperate 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 alrogithm 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 millseconds or microseconds then its not worth doing it.

Answer 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.

Answer 6

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.

Answer 7

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.