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?

Solution 1

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.

Solution 2

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

---

+

Solution 3

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.

Solution 4

Besides being slower, recursion can also result in stack overflow errors depending on how deep it goes.

Solution 5

To write an equivalent method using iteration, we must explicitly use a stack. The fact that the iterative version requires a stack for its solution indicates that the problem is difficult enough that it can benefit from recursion. As a general rule, recursion is most suitable for problems that cannot be solved with a fixed amount of memory and consequently require a stack when solved iteratively. Having said that, recursion and iteration can show the same outcome while they follow different pattern.To decide which method works better is case by case and best practice is to choose based on the pattern that problem follows.

For example, to find the nth triangular number of Triangular sequence: 1 3 6 10 15 … A program that uses an iterative algorithm to find the n th triangular number:

Using an iterative algorithm:

//Triangular.java
import java.util.*;
class Triangular {
   public static int iterativeTriangular(int n) {
      int sum = 0;
      for (int i = 1; i <= n; i ++)
         sum += i;
      return sum;
   }
   public static void main(String args[]) {
      Scanner stdin = new Scanner(System.in);
      System.out.print("Please enter a number: ");
      int n = stdin.nextInt();
      System.out.println("The " + n + "-th triangular number is: " + 
                            iterativeTriangular(n));
   }
}//enter code here

Using a recursive algorithm:

//Triangular.java
import java.util.*;
class Triangular {
   public static int recursiveTriangular(int n) {
      if (n == 1)
     return 1;  
      return recursiveTriangular(n-1) + n; 
   }

   public static void main(String args[]) {
      Scanner stdin = new Scanner(System.in);
      System.out.print("Please enter a number: ");
      int n = stdin.nextInt();
      System.out.println("The " + n + "-th triangular number is: " + 
                             recursiveTriangular(n)); 
   }
}

View more solutions

Comments

[Bernhard Barker]

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.

[SomeWittyUsername]

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

[SomeWittyUsername]

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.

[SomeWittyUsername]

@dasblinkenlight It might be theoretically possible to reduce multiple loops to a single one, but not sure about this.

[Bernhard Barker]

@icepack Yes, it is possible. It may not be pretty, but it's possible.

[trumpetlicks]

Im not sure I agree with your 1st statement. CPUs themselves dont really model recursion at all, it is the instructions being run on the CPU that model recursion. secondly, a loop structure doesnt (necessarily) have a dynamically growing and shrinking dataset, where a recursive algorithm usually will for each level deep the recursion must step.

[Steve Jessop]

I'm pretty sure that I can explain factorials as clearly with recursion as by iteration (and users of functional programming languages would probably say more clearly). But it's just an example, so it doesn't really matter, the point is that if you can see an iterative/recursive solution to your problem, then you can write iterative/recursive code to solve it, and the code will bear a closer resemblance to the solution you thought of.

[Breako Breako]

@dasblinkenlight why is recursive better for explaining divide and conquer and iteration for everything else?

[Sergey Kalinichenko]

@BreakoBreako I wouldn't limit it to "divide and conquer": although very often it is the case, there are inherently recursive algorithms that are not of the "divide and conquer" type. For example, topologically sorting a directed graph can be easily coded with recursion, yet it is not a "divide and conquer" problem. Similarly, there's a whole class of dynamic programming problems that can be solved using recursion and memoization, which are not necessarily of the "divide and conquer" variety.

[comingstorm]

You could view the call stack as the original automated memory management. Algorithms that require a single stack almost always map naturally into a recursive implementation, while any non-recursive implementation will need to implement and manage the stack manually...

[Bernhard Barker]

Any recursive code can be converted to functionally identical iterative code using stacks. The difference you're showing is the difference between two approaches to solve the same problem, not the difference between recursion and iteration.

[Bernhard Barker]

It is always possible to convert a recursive algorithm to an iterative one (using stacks). You might not end up with a particularly simple loop, but it is possible.

[Yeikel]

Can you please provide me an example where recursion makes the code more maintainable? In my experience, it is always the other way around. Thank you

[jdelman]

I appreciate the attempt at providing an authoritative answer and I'm sure the author is intelligent but "trust me" isn't a helpful response to a meaningful question whose answer is not immediately obvious. There are very straightforward algorithms for doing an iterative depth-first search. See the example at the bottom of this page for a description of an algorithm in pseudocode: csl.mtu.edu/cs2321/www/newLectures/26_Depth_First_Search.htm‌​l

[Matt]

@Yeikel Write a function f(n) that returns the nth Fibonacci number.

[Andrestand]

An interesting example. I guess you know the paper by M.C. Er "The Towers of Hanoi and Binary Numerals". Also treated in a fantastic video by 3brown1blue.