When to use recursion instead of iteration?

Question

1.00/5 (2 votes)

See more:

I was wondering if there are some cases when using recursion might be better than iteration or the other way around?

What I have tried:

I know that theoretically almost(?) anything that can be done with recursion can also be done with iteration and vice versa. I also think that, computationally, recursion is less efficient. but I'm asking which is better purely for the purpose of simplifying the code and making the developer's job easier?

Posted 19-May-16 9:19am

Member 12527108

Updated 19-May-16 11:30am

v2

Add a Solution

3 solutions

Solution 3

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

Posted 19-May-16 11:30am

Sergey Alexandrovich Kryukov

Updated 19-May-16 13:44pm

v4

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Matt T Heffron · Accepted Answer · 2016-05-19T09:46:00

Recursion is rarely the better choice compared with iteration.
It might be more understandable in cases of some problems dealing with recursively defined data structures (that are known to be bounded size!).

However there are some problems that would be insanely difficult to represent as iteration. Consider the (purely academic) Ackermann–Péter function:

A(m, n) where m >= 0, n >= 0
  => n + 1                   if m == 0
  => A(m - 1, 1)             if m > 0 and n == 0
  => A(m - 1, A(m, n - 1))   if m > 0 and n > 0

Trying to structure this as iteration would be very difficult.
(It's also computationally immense. A(4, 2) has 19729 decimal digits.)

Now you're not very likely to have to deal with anything this esoteric, so I'd choose recursion when it makes the intent of the code more clear, it is known to be well bounded, and any computational inefficiency relative to iteration is not significant to the overall application.

Note that many optimizing compilers can convert tail recursion into an iteration implementation!

CPallini · Accepted Answer · 2016-05-19T09:59:00

Solution 2

The oldie-goldie Wirth's book[^] provides excellent insight on this very argument.

Posted 19-May-16 9:59am

CPallini

Comments

Sergey Alexandrovich Kryukov 19-May-16 17:34pm

Good idea, a 5.
However, I provided my own explanation and some characteristic examples, in some generalization of Solution 1.
—SA