recursion versus iteration

Question

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.

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

---

⁺ I borrowed the sledgehammer analogy from Dijkstra's "Discipline of Programming".

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.

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

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)); 
   }
}

Most of the answers seem to assume that iterative = for loop. If your for loop is unrestricted (a la C, you can do whatever you want with your loop counter), then that is correct. If it's a real for loop (say as in Python or most functional languages where you cannot manually modify the loop counter), then it is not correct.

All (computable) functions can be implemented both recursively and using while loops (or conditional jumps, which are basically the same thing). If you truly restrict yourself to for loops, you will only get a subset of those functions (the primitive recursive ones, if your elementary operations are reasonable). Granted, it's a pretty large subset which happens to contain every single function you're likely to encouter in practice.

What is much more important is that a lot of functions are very easy to implement recursively and awfully hard to implement iteratively (manually managing your call stack does not count).

Yes, as said by Thanakron Tandavas,

Recursion is good when you are solving a problem that can be solved by divide and conquer technique.

For example: Towers of Hanoi

1. N rings in increasing size
2. 3 poles
3. Rings start stacked on pole 1. Goal is to move rings so that they are stacked on pole 3 ...But
   • Can only move one ring at a time.
   • Can’t put larger ring on top of smaller.
4. Iterative solution is “powerful yet ugly”; recursive solution is “elegant”.