recursion versus iteration

Question

Is it correct to say that everywhere recursion is used a for loop could be used? And if recursion is usually slower what is the technical reason for ever using it over for loop iteration?

And if it is always possible to convert an recursion into a for loop is there a rule of thumb way to do it?

Tom Moertel's blog has four excellent posts on converting recursive code to iterative code: blog.moertel.com/tags/recursion.html — Jul 24 '15 at 16:30

Denys Séguret 192k 21 343 402 · Accepted Answer · 2013-10-11 14:13:54Z

Recursion is usually much slower because all function calls must be stored in a stack to allow the return back to the caller functions. In many cases, memory has to be allocated and copied to implement scope isolation.

Some optimizations, like tail call optimization, make recursions faster but aren't always possible, and aren't implemented in all languages.

The main reasons to use recursion are

that it's more intuitive in many cases when it mimics our approach of the problem
that some data structures like trees are easier to explore using recursion (or would need stacks in any case)

Of course every recursion can be modeled as a kind of loop : that's what the CPU will ultimately do. And the recursion itself, more directly, means putting the function calls and scopes in a stack. But changing your recursive algorithm to a looping one might need a lot of work and make your code less maintainable : as for every optimization, it should only be attempted when some profiling or evidence showed it to be necessary.

To add on it - recursion is closely related to the term of reduction which plays a central role in many algorithms and in CS in general. — Mar 28 '13 at 17:19

dasblinkenlight 395k 36 412 717 · Answer 2 · 2013-03-28 17:20:36Z

Is it correct to say that everywhere recursion is used a for loop could be used?

Yes, because recursion in most CPUs is modeled with loops and a stack data structure.

And if recursion is usually slower what is the technical reason for using it?

It is not "usually slower": it's recursion that is applied incorrectly that's slower. On top of that, modern compilers are good at converting some recursions to loops without even asking.

And if it is always possible to convert an recursion into a for loop is there a rule of thumb way to do it?

Write iterative programs for algorithms best understood when explained iteratively; write recursive programs for algorithms best explained recursively.

For example, searching binary trees, running quicksort, and parsing expressions in many programming languages is often explained recursively. These are best coded recursively as well. On the other hand, computing factorials and calculating Fibonacci numbers are much easier to explain in terms of iterations. Using recursion for them is like swatting flies with a sledgehammer: it is not a good idea, even when the sledgehammer does a really good job at it⁺.

⁺ I borrowed the sledgehammer analogy from Dijkstra's "Discipline of Programming".

Recursion is usually more expensive (slower / more memory), because of creating stack frames and such. The difference may be small when applied correctly for a sufficiently complex problem, but it's still more expensive. There are possible exceptions such as tail recursion optimization. — Mar 28 '13 at 17:17
I'm not sure about a single for loop in every case. Consider a more complex recursion or a recursion with more than single variable — Mar 28 '13 at 17:18
@dasblinkenlight It might be theoretically possible to reduce multiple loops to a single one, but not sure about this. — Mar 28 '13 at 17:22
@icepack Yes, it is possible. It may not be pretty, but it's possible. — Mar 28 '13 at 17:23

Thanakron Tandavas 2,817 2 10 31 · Answer 3 · 2013-12-12 19:36:37Z

Question :

And if recursion is usually slower what is the technical reason for ever using it over for loop iteration?

Answer :

Because in some algorithms are hard to solve it iteratively. Try to solve depth-first search in both recursively and iteratively. You will get the idea that it is plain hard to solve DFS with iteration.

Another good thing to try out : Try to write Merge sort iteratively. It will take you quite some time.

Question :

Is it correct to say that everywhere recursion is used a for loop could be used?

Answer :

Yes. This thread has a very good answer for this.

Question :

And if it is always possible to convert an recursion into a for loop is there a rule of thumb way to do it?

Answer :

Trust me. Try to write your own version to solve depth-first search iteratively. You will notice that some problems are easier to solve it recursively.

Hint : Recursion is good when you are solving a problem that can be solved by divide and conquer technique.