# Which is better ? Iterations or Recursions?

I've heard that any algorithm using iterations can be changed into one that uses recursions and vice-versa.

But which type of repetition is preferable for minimum amount of computational effort and resource consumption ? Iteration or Recursion ?

• Which is better? Apples or zucchinis? – Raphael Jan 12 at 11:13
• I had to look this up... Seems zucchinis have a bigger nutritional value... – Demis Jan 12 at 23:16

A straightforward answer would be "iteration", since recursion consumes stack memory and imposes computational overhead for calling functions.

However, in practice both implementations can be equivalent at machine code level due to compiler optimizations (such as tail call optimization). In general, you shouldn't really be concerned about these matters unless you have strong reasons to believe they are relevant in your particular case.

As a rule of thumb, you should concentrate on clarity and efficiency of your algorithm, and use constructions that look natural for the logic of your method. This recommendation is repeated virtually in all books on the subject, so please follow it.

P.S. You should also consider that certain algorithms require you to store certain local values on each iteration. Recursion gives you this capability "for free", so you should also consider that iterative procedures may need additional data structures comparing to their recursive equivalents.

• You may want to add that you can use the call stack for logic (say, DFS). An iterative equivalent might have to use an explicit stack which might incur more overhead than recursion! – Raphael Jan 12 at 11:14
• Well, technically you are right, of course. I'd say, this is a part of a "natural way of constructing your algorithm". OK, I will try to formulate this thought. – rg_software Jan 12 at 11:18
• True. I think my additional point is that the memory and runtime overhead of recursion can (and should) be used. This may actually be the deciding criterion for what to choose: iterating through a linked list doesn't require the "power" of recursion, DFS however does. – Raphael Jan 12 at 11:21
• Thank you. I was thinking about this while examining the algorithms of computing π and fibonacci sequences. I was wandering if the recursion method in a setup when the user didn't have to enter a number of recursions but instead just let the computer do its thing until a keyboard button was pussed ... whould that undetermined recursion depth just overflow the memory before it could spit a single digit ? – Demis Jan 12 at 23:11

It depends on the problem and the approach. For example, when you're computing a dp, and you won't use some of the calculated answers, it's better to do it with the recursive algorithm, because you will use more time and memory, computing them in the iterations in general. But for computing the n-th fibonacci sequence number, it is better to calculate using iteration. So it really depends on the problem itself. Generally, recursion may take more time, due to the more calls for a single calculation. for further information, please check this link and this file link.

• Fibonacci numbers suffer if you use the definition for recursion. Using a recursive function that take fib(n) and fib(n-1) and returns fib(n+1) and fib(n) recursive calculation is very fast. – gnasher729 Jan 12 at 11:43

Some problems are naturally calculated with a loop. Some problems are naturally calculated using recursion. Use whatever makes one particular problem easier. Try implementing Quicksort without recursion (much more difficult).