Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

What is better for performance to write the loop as linear e.g. for , while or write it as recursion ?

share|improve this question
8  
Why are you so concerned with performance that you're willing to alter small details of the code to get micro-efficiencies? –  David Thornley Mar 28 '11 at 20:11
2  
As i know ( CS background ) recursion most of the time is slower more memory used , but today one of my colleagues tell the opposite , just i need to know what other programmers know and practice . –  shox Mar 28 '11 at 20:18
2  
Test them both and see! –  Marcie Mar 28 '11 at 20:47
9  
Colleagues say all kinds of things. The first thing to understand about performance is it's not binary, and it's not absolute. It's relative. There are situations where a microsecond is slow, and a second is fast. As always, first see if you have a problem. Then find out what the problem is, relative to the big picture. Then IF the problem is recursion, and the compiler doesn't make a loop out of if, consider doing it yourself. (You're not alone. These forumns are full of people who ask micro-performance questions, unaware of the relativity of performance.) –  Mike Dunlavey Mar 29 '11 at 0:38

10 Answers 10

up vote 34 down vote accepted

Depends on a lot of factors.

For the vast majority of applications, whatever is easier for a human being to understand is the proper choice.

share|improve this answer
11  
Agreed... always favour readability / maintainability over performance until you can prove you need to optimize it! –  Stephen Bailey Mar 28 '11 at 20:11
1  
+1 - So few programmers argue this point... –  P.Brian.Mackey Mar 28 '11 at 20:15
5  
And, when in doubt, measure the actual implementation. –  S.Lott Mar 28 '11 at 20:20
1  
+1 ... wonder how many coders have chased fractions of seconds worth of performance increase while making it completely impossible for anyone to read their code! –  Jim Mar 28 '11 at 20:27
1  
@Jim: The real fun is when they do micro-optimizations while using suboptimal algorithms, sometimes incidentally obfuscating the algorithms. –  David Thornley Mar 29 '11 at 18:20

That may very likely depend on the language that you are using. The only real way to answer that is to simply benchmark it.

As for recursion - unless you are careful about tail recursion you not only need to consider time in performance metrics but also memory.

share|improve this answer
1  
+1 for tail recursion –  l0b0 Mar 29 '11 at 14:14
    
It might not only depend on the language, but on the platform, you're compiling for, as well as on the version of the compiler. A new version could use a new optimization. And it might depend on the samplesize - one method could be faster for small sample sizes but slower on larger samples. –  user unknown May 17 '11 at 2:38

In many languages/language implementations, all differences are pretty much eliminated by the compiler. In all others, the difference is laughable and absolutely not worth making tradeoffs on source code level - choose whatever is most readable and clean, nobody will notivce any difference. (Unless the code in question is the innermost loop of a performance-critical program. But such software shouldn't be written by you or anyone who asks such questions instead of profiling to (1) find out where to optimize and (2) how effective various "optimizations" are!)

One exception is that very deep recursion (the depth you only reach when you do recurse once per element and the argument is a huge collection - tree traversal etc. is completely find and in fact best solved by recursion) usually (except in a relatively clever language implementation if it's a tail call) results in stack overflows, so if that's a real danger, you'll have to eliminate the recursion manually (all recursive algorithms can be written iteratively, and vice versa).

share|improve this answer
    
+1 for StackOverflows. At least in Java having a recursive method that makes stacks thousands of lines deep is a very bad idea –  TheLQ Mar 28 '11 at 22:01
    
Pretty much all modern compilers for languages that allow recursion do tail call optimization. –  John R. Strohm Mar 29 '11 at 5:35
2  
@John: tail call optimization can only be applied to a subset of recursive functions, near tail call optimization and sometimes cross-functions tail call optimization kick in, but the vast majority of recursive functions do provoke function calls. –  Matthieu M. Mar 29 '11 at 8:29
    
@Matthieu M., if it is a recursive implementation of whatever otherwise would be a loop, it is naturally tail recursive. –  SK-logic Mar 29 '11 at 9:36
    
@SK-logic: You assume much about the programmers in this world, while it could be expressed in a form that would allow tail-recursion, I've seen much code that could only be described as obfuscated... –  Matthieu M. Mar 29 '11 at 9:41

As stated elsewhere - most of the time readability matters more than slicing and dicing performance to the Nth degree. If you want some handy rules of thumb I'd suggest this:

Use a FOR() {} loop when:

  • You know you want to iterate through a set/list/array a specific number of times and you will likely need an index value anyways.

Use a WHILE() {} loop when:

  • You will stop looping based on a non-numeric condition such as running off the end of a linked list and you aren't sure if you even want to loop one time.

Use a DO {} WHILE() loop when:

  • You will stop looping based on a non-numeric condition AND you know you want to run the contents of the loop at least once.

Use RECURSION when:

  • You need to do some heavy lifting on each iteration that will get messy if you do it in an unrolled loop AND you know you're not going to recurse too deeply.
  • Preferably you're working in a language that supports Tail Recursion

Most looping structures (FOR or WHILE) are implemented behind the scenes as 'compare and branch' - so the cost will be the same. The nitty-gritty differences to consider are:

FOR loop:

  • You typically have to allocate a stack variable which gets incremented N times. If you'd be doing this anyways, this is the most concise loop to use.
  • If you want to loop N times, you will end up performing N+1 conditional checks.

WHILE loop:

  • This loop requires you to perform your own increment logic so it is more flexible than a FOR loop.
  • If you want to loop N times, you will end up performing N+1 conditional checks.

DO WHILE() loop:

  • If you want to loop 0 times, then this loop is not for you.
  • If you want to loop N>0 times, then this loop will only run N conditional tests and lets you define your own increment logic, making it the best choice for performance.

RECURSION:

  • In iterative languages you do a lot of work each time you call a new function, so recursion is rarely best for performance. If your language supports tail recursion then its more or less equivalent to a WHILE loop.
share|improve this answer
    
+1 for usage and tail recursion. –  Aditya P Mar 29 '11 at 4:55
    
This might be true for some languages, but false for others. In Java, for example, you don't always get an index value, while using a for-loop. for (String s: words) ... In bash: for file in /etc/*; do fun $file; done –  user unknown May 17 '11 at 2:47

Souce: Wikipedia on recursion The answer is language dependent. For languages that are oriented towards iteration like C and Java, recursion is slower due to the overhead of function calls. For functional languages, which typically have lower overhead costs, the difference is often negligible.

One piece of good advice I've read is to try both and then test each for performance (if performance matters).

share|improve this answer
    
It depends on the compiler/interpreter as to whether recursion is slower. Many compilers optimize away recursive loops. –  dan_waterworth Mar 29 '11 at 8:48
    
Thanks, Dan! Much appreciate the comment. –  Ethel Evans Mar 29 '11 at 17:19

In my experience, more than the problem of iterative vs recursive functions, the biggest choke points tend to be external resource access, ie, databases, network connections, disk or screen I/O, which are much better candidates than any raw loops for optimization. It's sometimes the case that your loops spend a lot of time accessing external resources, and if that's the case, you can optimize there quite heavily. Many operations can be unrolled into parallel tasks that you can execute when the resource access completes.

If you're doing a lot of math, maybe you should consider ensuring your code does a mix of Floating Point and Integer operations, (A good compiler/processor will ensure these execute simultaneously on their respective processing units) or replacing expensive operations like sqrt with other ops, or approximations/lookup tables. (If you only ever need the square root of a whole number in a fixed range, or a sin/cosine of whole numbers of degrees, that's a GREAT candidate for a lookup table) Try to make sure you're not doing math serially if possible (result -> operand -> result -> operand) to allow the CPU to split the tasks over as many processing units as possible.

You might also consider breaking your task into chunks, and running each chunk in its own thread, or using a execution engine like Apple's Grand Central, Java's Executors, etc, which also allows you to take maximum advantage of multiple cores/processors. Again, how much to put into each chunk is a matter of profiling to see what the best chunk size is for your particular task.

Lastly, you might want to consider that your approach is simply wrong. There's usually more than one way to do a particular task, and you shouldn't get too hung up on any one way of doing it, even if it seems the most "elegant" or "perfect" solution. If only IBM's supercomputers can solve the problem in a reasonable period of time, no amount of loop optimization is going to help, and you should try a different approach.

IE: Ray traced graphics are beautiful, but if you're programming a game, use hardware accelerated raster graphics instead.

share|improve this answer

I remember back in high school when I was learning Java, me and a friend had a beef about which loop was better, while or for. I wrote a program to measure which one was faster and one of them run faster more often than the other. I don't remember which one it was, but I started to use that loop all the time even if it made more sense to use the other. I later realized that there are no measurable difference between the two and that the results I had seen was pretty much random. After that I started to use the loop that logically made more sense.

At the time I didn't even know of recursion, but since recursion eats memory and not just CPU cycles, loops are generally preferable from a performance perspective. However, if a problem is solved more elegantly with recursion I always use recursion.

To sum up:

For the vast majority of applications, whatever is easier for a human being to understand is the proper choice.

Quote from the most upvoted answer. I know I didn't really add any new information relevant to the question. I just wanted to tell this tale and reminisce about high school. Please don't downvote me for feeling the need to share my dorky story.

share|improve this answer

Recursion is generally slower. The stack manipulation on calls is a lot uglier/slower than the jumps that get executed as part of a loop. It's just the state of current processor design. However, some compilers will optimize the calls into jumps for you anyways. You might find that the exact same code is generated either way... :-)

Always profile your code to find out for sure.

share|improve this answer

Depends on how clever the compiler is. In theory there is no difference between tail recursive functions and loops so the compiler will probably convert the tail recursive function to a loop anyway. In case of more complicated recursive functions it's probably a good idea to rewrite them as loops if possible and if not then it's probably a good idea to use some kind of memoization technique to keep the stack depth as shallow as possible.

share|improve this answer

While iteration and recursion are functionally equivalent (isomorphic), their performance will differ depending on both the language and interpreter/compiler used.

From wiki:

In languages (such as C and Java) that favor iterative looping constructs, there is usually significant time and space cost associated with recursive programs, due to the overhead required to manage the stack and the relative slowness of function calls; in functional languages, a function call (particularly a tail call) is typically a very fast operation, and the difference is usually less noticeable.

This can certainly change given sufficiently advanced compilers given the previously mentioned isomorphism.

That said, the decision to use iteration or recursion in a specific case should not be based entirely (or even primarily) on performance concerns. Doing so often leads to premature optimization. Other tensions, such as readability, will usually be more important.

Even in the event that a particular iterative or recursive function is shown (by measurement) to be a hotspot, switching to recursion (or vice versa) is not guaranteed to yield performance improvements.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.