True, in practice, recursion is rarely the better choice (Solution 1, by Matt T Heffron).
Matt's explanation and rationale are correct and reasonable, but they can be generalized, to certain extent.
There are problems which are recursive by their nature. Therefore, the solution of such problems expressed through formal programming recursion is always easy to create, understand, debug and maintain.
It's good to understand the concept of recursion in the wide sense of this word
vs. some meaning specific to computing:
Recursion — Wikipedia, the free encyclopedia[
^],
Recursion (computer science) — Wikipedia, the free encyclopedia[
^].
So the benefit of a recursive solution is certain "ease of programming". But is it enough? No. The recursive solution should be at least acceptable in terms of 1) performance, 2) the amount of memory required; it's important to understand that the memory requirements are always reduced to how many stack frames can be created at the same time until
stack overflow exception is thrown.
For an iterative solution the major criteria is the programming problem, as explained in Solution 1, and performance and memory requirements are much more relaxed than with recursion.
Let's consider two recursive examples, one is a bad choice for a recursive solution, and one is good.
First one is
factorial. Actually, this is a popular example of recursive solution. Probably, in bad (and very widespread) computer science teaching, this is the most efficient example aimed to denounce recursion completely. :-) It's a way to choose the worst example of a recursive solution and create a false impression that recursion is always wrong. Indeed, the iterative solution for the factorial calculation is even simpler than recursive; and the iteration solution is infinitely better than recursive. The logic of such people is truly amazing.
The second example is my all-time favorite example where recursion is really good. Imagine that you have to model some class hierarchy using some metadata. You may have the set of classes and need to walk the inheritance hierarchy. It can be related to
reflection or not; it does not matter. With reflection, each set element used to represent a class could be the instance of the type metadata class, such as .NET
System.Type
instance, but it could be anything else. One of the example of the problem solved on such set is some code or pseudo-code generation with the requirement that each class declaration should be placed below the declaration of its parent class (which is a requirement for some languages like C++). With recursive, this is not a problem at all. You take the base class(es) of each current class, if any, and recursively call the function appending the declaration to your output string. This way, the order of output declaration is always preserved, no matter what is the order on input.
Why is recursion much better in this case than another approach? Because you don't bother about order at all, it is preserved automatically. Why won't performance memory consumption and stack overflow make any issues? Because we only need to handle practically sensible class hierarchies, which would probably be compiled, and so on. The depth of such hierarchy physically are unlikely to be so high as to present any problems for the stack and stack memory. Effectively, "ease of programming" of recursions gives a lot of benefits (despite the fact that a non-recursive solution is still possible), and the issues of performance and memory consumption don't present any problems.
[EDIT]
I almost forgot to mention the importance of
tail recursion (also mentioned in Solution 1), a special case of recursion where the implementation (say, of a particular compiler or code optimizer) can avoid adding stack frames by replacement of actual calls with jumps. This technique is called
tail call elimination and can be used for radical optimization of recursion, which makes the solution extremely efficient:
Tail call — Wikipedia, the free encyclopedia[
^].
—SA