I love recursion. I think it simplifies things a lot. Another may disagree; I think it also makes the code a lot easier to read. However, I've noticed that recursion is not used as much in languages such C# as they are in LISP (which by the way is my favorite language because of the recursion).
Does anybody know if there is any good reasons not use recursion in the languages such as C#? Is it more expensive than iteration?
Are they more expensive than iterations?
Yes they are. Many Lisp variants support the idea of a "tail-call optimisation" which allows many uses of a recursive function call to be converted into an iterative one (this is simplifying a bit). If tail-call is not supported, then a recursive function call will use progressively more memory on the stack.
Are they more expensive than iterations?
Yes they are. Recursion requires creating a new stack frame along with a call and return whereas iteration generally only requires a compare and branch making it substantially faster; however, compilers can perform tail-call optimization on certain recursive calls (namely tail calls) which allow them to reuse the stack frame making the recursive call much less expensive and effectively turning them into iteration. Scheme actually requires that scheme compilers implement tail-call optimization.
Functional languages such as Lisp and F# can implement many tail recursive functions internally as loops and are able avoid the stack overhead of a function call. C# doesn't have support for tail recursion, although F# does.
The compiler and the architecture of modern CPUs can do lots of optimizations with iteration that they can't do with recursion. For example, the ability of the processor to do optimistic computation. When the processor finds an iteration space it knows how long it will take. From the beginning, there is no real need to check each time before starting the next loop. So, they pipeline the operations. Since most CPUs can do several operations at the same time (through pipelining), you can solve the iteration space in less time than the recursion. This is even with tail-optimization because the CPU is actually processing about 4 loops at a time (for a x4 performance gain). This gain will depend on the architecture of the CPU. The architecture is likely to be a big part of the gain, with next gen CPUs pushing gains even further than that.
The true problem with recursion is that our hardware is VonNeumann based (achievable variant of the Turing machine), and not Lisp machines, although there are a few specialized Lisp hardware, you won't find any desktops with it :)
There are many pros and cons to using recursion. Definitely the code simplicity is the biggest one which also lends itself to better code maintainability and less bugs.
The biggest danger to recursion are edge cases were the algorithm spins out of control to break the function stack limit. Some languages, Progress's ABL language for one, has a parameter for the highest level of nested calls allowed. These are usually low and adding recursion to the mix could make an application break that limit.
In short, recursion should always be implemented with tight termination cases otherwise it can be very difficult to debug (because of unpredictability) and can cause serious issues in production code.
For the concerns with memory and speed, unless this is a method itself is short (time wise) being called many times it really doesn't matter what the performance is.
Example: If you use recursion to scan all the files and folders of a hard drive the performance impact that the recursion does is minuscule to the time it takes to hit the hard drive and grab the file system information. In this case recursion is probably preferred over iterative processing.
Another example: If you scan the nodes of a tree structure, an iterative process maybe more beneficial because we are not involving the function stack as much which means we are hitting less memory and probably letting the hardware use more caching. See Robert Gould's response for more details.
If an algorithm can be expressed most naturally in a recursive form, and if the stack depth is small (in the log(N) range, i.e. typically <20), then by any means use recursion. (Any performance gain due to iteration will be a small constant factor).
If there is any danger that the stack grows large, and if your language/compiler/runtime system doesn't guarantee the tail call optimization, you should avoid recursive algorithms.
Does anybody know if there is any good reasons not use recursion in the languages such as C#? Is it more expensive than iteration?
Yes, because C# doesn't support tail recursion. When using recursion for simple iteration through large collections, you can easily get a StackOverflowException and crash your application if you recurse too deeply.
The choice isn't based solely on the problem to be solved, but also on the language used. In C-style languages (Java, C#, or what have you) my knee-jerk response is to avoid recursion, as it looks completely alien to me (and I just can't think recursively), to say nothing of the potential for stack abuse. However, there are some problems for which it makes almost no sense to use anything other than recursion - tree traversal being a good example. An iterative solution is completely plausible, but the code would be bigger, buggier, and almost certainly less readable.
However, more dynamic language (such as Lisp or Python) go to great lengths to make recursion a more natural possibility. My personal response is to look for an iterative solution first, no matter what the problem, but varying mileage makes a horse race.
In the end, the best bet is probably to just write it. Chances are good that you'll throw it out once in any case.
If a problem can be reduced to an iteration, then I iterate.
If a problem calls for recursion (eg tree navigation) then I recurse.
That being said I primary make line of business apps in C# - I'm sure scientific programming has a different set of requirements.
Scheme is the only Lisp dialect I know of that requires tail-call optimization, and they tend to use recursion a lot. In other Lisp dialects that don't require this (like Common Lisp), I don't see recursion used any more than in any other language.
Recursion is (impossible/much harder) to parallelize than iteration
Modern cpus have multi-cores therefore direct optimization with parallel.for (and such techniques) gets much harder if you designed for recursion.
However parallelization is still quite obscure and relatively few people uses it yet.
Furthermore, I think recursive algos are easier to design and think of because they involve slightly less code and variables at the same time. I usually go for recursion when there is no performance necessity.
I think recursive functions have to be put on a stack - each time the function calls itself, another copy of that function goes on a function stack, and so on. The problem is that, at some point, the stack runs out of space to store functions, so if the numbers get to big, a recursive solution may not work. I know because it bit me in the ass - I had a great recursive function to free() my entire linked list, and then I did a test of it with the biggest linked list I could make and got an error (I believe it was a segfault - definitely should have been a stack overflow :) ).
Iterative functions don't have these errors - in machine language, they are expressed as simple 'jmp's or 'je's or so on, so they never run out of room on the function stack and are, effectively, cleaner.
This is an entirely subjective question, but if it wasn't for the fact that recursion has a limit built-in to your computer, I would say it is a much better solution. Some iterative solutions to problems just look ugly, while the recursive solution looks so much cleaner and nicer. But such is life.
When dealing with inherently linear data structure such as list or vector, one reason to prefer iterative construct over recursion is it conveys the intent of your code better. Oftentimes it requires more effort for the reader to discern the structure of your program when recursion is used indiscriminately when iteration suffices.
I'll just throw out there that in XSLT variables are read-only once created. Because of this, things that would be done with indexed for loops, like
for(int i=0; i < 3; i++) doIt(i);
are actually done with recursion. Something equivalent to
public rediculous(i) {
doIt(i);
if (i < 3) rediculous(i + 1);
}
I would actually provide an XSLT example here, but all that typing makes Baby Jesus cry.
