Recursion or Iteration?

Question

Is there a performance hit if we use a loop instead of recursion or vice versa in algorithms where both can serve the same purpose? Eg: Check if the given string is a palindrome. I have seen many programmers using recursion as a means to show off when a simple iteration algorithm can fit the bill. Does the compiler play a vital role in deciding what to use?

Solution 1

It is possible that recursion will be more expensive, depending on if the recursive function is tail recursive (the last line is recursive call). Tail recursion should be recognized by the compiler and optimized to its iterative counterpart (while maintaining the concise, clear implementation you have in your code).

I would write the algorithm in the way that makes the most sense and is the clearest for the poor sucker (be it yourself or someone else) that has to maintain the code in a few months or years. If you run into performance issues, then profile your code, and then and only then look into optimizing by moving over to an iterative implementation. You may want to look into memoization and dynamic programming.

Solution 2

Loops may achieve a performance gain for your program. Recursion may achieve a performance gain for your programmer. Choose which is more important in your situation!

Solution 3

Comparing recursion to iteration is like comparing a phillips head screwdriver to a flat head screwdriver. For the most part you could remove any phillips head screw with a flat head, but it would just be easier if you used the screwdriver designed for that screw right?

Some algorithms just lend themselves to recursion because of the way they are designed (Fibonacci sequences, traversing a tree like structure, etc.). Recursion makes the algorithm more succinct and easier to understand (therefore shareable and reusable).

Also, some recursive algorithms use "Lazy Evaluation" which makes them more efficient than their iterative brothers. This means that they only do the expensive calculations at the time they are needed rather than each time the loop runs.

That should be enough to get you started. I'll dig up some articles and examples for you too.

Link 1: Haskel vs PHP (Recursion vs Iteration)

Here is an example where the programmer had to process a large data set using PHP. He shows how easy it would have been to deal with in Haskel using recursion, but since PHP had no easy way to accomplish the same method, he was forced to use iteration to get the result.

http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html

Link 2: Mastering Recursion

Most of recursion's bad reputation comes from the high costs and inefficiency in imperative languages. The author of this article talks about how to optimize recursive algorithms to make them faster and more efficient. He also goes over how to convert a traditional loop into a recursive function and the benefits of using tail-end recursion. His closing words really summed up some of my key points I think:

"recursive programming gives the programmer a better way of organizing code in a way that is both maintainable and logically consistent."

https://developer.ibm.com/articles/l-recurs/

Link 3: Is recursion ever faster than looping? (Answer)

Here is a link to an answer for a stackoverflow question that is similar to yours. The author points out that a lot of the benchmarks associated with either recursing or looping are very language specific. Imperative languages are typically faster using a loop and slower with recursion and vice-versa for functional languages. I guess the main point to take from this link is that it is very difficult to answer the question in a language agnostic / situation blind sense.

Is recursion ever faster than looping?

Solution 4

Recursion is more costly in memory, as each recursive call generally requires a memory address to be pushed to the stack - so that later the program could return to that point.

Still, there are many cases in which recursion is a lot more natural and readable than loops - like when working with trees. In these cases I would recommend sticking to recursion.

Solution 5

Typically, one would expect the performance penalty to lie in the other direction. Recursive calls can lead to the construction of extra stack frames; the penalty for this varies. Also, in some languages like Python (more correctly, in some implementations of some languages...), you can run into stack limits rather easily for tasks you might specify recursively, such as finding the maximum value in a tree data structure. In these cases, you really want to stick with loops.

Writing good recursive functions can reduce the performance penalty somewhat, assuming you have a compiler that optimizes tail recursions, etc. (Also double check to make sure that the function really is tail recursive---it's one of those things that many people make mistakes on.)

Apart from "edge" cases (high performance computing, very large recursion depth, etc.), it's preferable to adopt the approach that most clearly expresses your intent, is well-designed, and is maintainable. Optimize only after identifying a need.

View more solutions

Comments

[Warrior]

Iteration is better than recursion.

[Mateen Ulhaq]

@Warrior Not always. With chess programs, for example, it's easier to read recursion. An "iterative" version of the chess code wouldn't really help speed, and might make it more complicated.

[Wayne Conrad]

Why should a hammer be favored over a saw? A screwdriver over an awl? A chisel over an auger?

[Maxpm]

@Wayne I don't know. That's why I'm asking. :P

[Wayne Conrad]

There are no favorites. They're all just tools, each with their own purpose. I would ask, "which sorts of problems is iteration better at than recursion, and vice versa?"

[sidgeon smythe]

Recursion should be favoured over iteration ("regular iteration"? what's irregular iteration?) when the recursive code is easier to grasp, and therefore maintain. This is often.

[Maxpm]

@Mike @gnovice This question was intended to focus on why recursion is already (seemingly) favored over iteration, not when to choose one over the other. I'll edit it to make that more clear.

[Keng]

"What's So Good About Recursion?"...It's recursive that's what. ;o)

[R.. GitHub STOP HELPING ICE]

False premise. Recursion is not good; in fact it's very bad. Anyone writing robust software will try to eliminate all recursion since, unless it can be tail-call optimized or the number of levels bounded logarithmically or similar, recursion almost always leads to stack overflow of the bad kind.

[SK-logic]

@R, have you ever heard of stackless languages?

[Maxpm]

@SK-logic Fun fact: EVE Online is written in Stackless Python.

[rassa45]

You will want to keep in the expence and speed of function calls in the language and compiler you are using

[Binil Thomas]

Algorithms whose correctness can be proved by induction tend to write themselves naturally in recursive form. Coupled with the fact that tail recursion is optimized by compilers, you end up seeing more algorithms expressed recursively.

[Liran Orevi]

There are JVM's for Java that optimize tail-recursion. ibm.com/developerworks/java/library/j-diag8.html

[Ben Hardy]

Actually, compiled Scala tail-recursive function boil down to a loop in the bytecode, if you care to look at them (recommended). No function call overhead. Secondly, tail-recursive functions have the advantage of not requiring mutable variables/side effects or explicit loops, making correctness far easier to prove.

[Ben Hardy]

Unless you write it in Scala ;-)

[Ben Hardy]

Unless of course your compiler optimizes tail calls like Scala.

[Sid Kshatriya]

Thats not true always. Recursion can be as efficient as iteration for some cases where tail call optimization can be done. stackoverflow.com/questions/310974/…

[rajya vardhan]

completely agree with ugasoft here... it depends on recursion-depth....and the complexity of its iterative implementation... you need to compare both and see which is more efficient... There's no thumb-rule as such...

[Maxpm]

I actually find the iterative version easier to understand. To each his own, I suppose.

[SK-logic]

@Maxpm, a high order recursive solution is much better: foldl (*) 1 [1..n], that's it.

[Siddhartha]

The calculation twice could actually be avoided through memoization.

[Kevin Meredith]

re: tail recursion is optimized by compilers But not all compilers support tail recursion..

[CoderDennis]

I think you've got the compiler optimization backward. Compilers will optimize recursive functions into an iterative loop when possible to avoid the stack growth.

[Nickz]

Fair point, it was backwards. However I'm not sure that's still applicable for tail recursion.

[Marcus Clements]

Recursive code can be extremely difficult to follow, especially if the order of the parameters change or the types with each recursion. Iterative code can be very simple and descriptive. The important thing is to code for readability (and therefore reliability) first, whether iterative or recursive, then optimise if necessary.

[Myst]

The test is invalid because you are calling the function inside the loop function - this invalidates one of the loop's most prominent performance advantages which is the lack of instruction jumps (including, for function calls, stack assignment, stack popping etc'). If you were performing a task within a loop (no just called a function) vs. performing a task within a recursive function you would get different results. (P.S. performance is a question of the actual task algorithm, where sometimes instruction jumps are cheaper then the computations required to avoid them).

[Aipi]

Did you know that you were cited into a book because of your answer phrase? LOL amazon.com/Grokking-Algorithms-illustrated-programmers-curio‌​us/…

[Vladyslav Startsev]

blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.ht‌​ml is dead but you can find it here github.com/juokaz/blog.webspecies.co.uk/blob/master/_posts/…

[StaceyGirl]

"Stack overflow will only occur if you're programming in a language that doesn't have in built memory management" - makes no sense. Most languages use stack of limited size, so recursion will lead to a failure pretty soon.

[dsteinhoefel]

...and many algorithms do not "write themselves" naturally in tail-recursive form, even though there's a straightforward recursive notation