In term of performance : while , for … Loops VS recursion

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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).

Answer 4

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.

Answer 5

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).

Answer 6

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.

Answer 7

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.

Answer 8

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.

Answer 9

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.

Answer 10

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.