Why use recursion if the same task can be accomplished with loop control structures?

Question

As I start learning recursion different questions are crossing my mind. Recursion uses more memory for the stack and it's usually slower due to maintaining the stack.

What is the benefit of using recursion if I still can use for loops? We describe actions to be repeated over and over until a condition is true, and we can use both recursion or for loops.

Why would I choose recursive version while I have faster control structures as an option?

Answer 1

Recursion uses more memory for the stack and it usually slower due to maintaining the stack

That statement is far from being universally true. It applies in situations when you do not need to save the state for more than a fixed number of levels, but that does not cover many important tasks that can be solved recursively. For example, if you want to implement a depth-first search on a graph, you need to make your own data structure to store the state that would otherwise go on the stack.

What is the benefit of using Recursion if I still can use for loop?

You get more clarity when you apply a recursive algorithm to a task that is best understood through recursion, such as processing recursively-defined structures. In cases like that, a loop by itself is no longer sufficient: you need a data structure to go along with your loop.

Why would I choose recursive version while I have faster control structure?

You wouldn't necessarily choose recursion when you could implement the same algorithm with faster control structures that are easy to understand. However, there are situations when you may want to code a recursion to improve readability, even though you know that you can code the algorithm using a loop, with no additional data structures. Modern compilers can detect situations like that, and "rewrite" your recursive code behind the scene to make it use iterations. This lets you have the best of both worlds - a recursive program that matches reader's expectations, and an iterative implementation that does not waste space on the stack.

Unfortunately, demonstrating examples of situations when recursion gives you clear advantages requires knowledge of advanced topics, so many educators take shortcuts by demonstrating recursion using wrong examples, such as factorials and Fibonacci numbers. One relatively simple example is implementing a parser for an expression with parentheses. You can do it in many different ways, with or without recursion, but the recursive way of parsing expressions gives you an amazingly concise solution that is easy to understand.

Answer 2

The great example of when the recursive solution is better than the itterative one is the tower of Hanoi. Consider the following two solutions -

Recursive (from this question):

public class Hanoi {

    public static void main(String[] args) {
        playHanoi (2,"A","B","C");
    }

    //move n disks from position "from" to "to" via "other"
    private static void playHanoi(int n, String from , String other, String to) {
        if (n == 0)
            return;
        if (n > 0)
        playHanoi(n-1, from, to, other);
        System.out.printf("Move one disk from pole %s to pole %s \n ", from, to);
        playHanoi(n-1, other, from, to);
    }

}

Iterative (copied from RIT):

import java.io.*;
import java.lang.*;

public class HanoiIterative{

    // -------------------------------------------------------------------------
    // All integers needed for program calculations.

    public static int n;         
    public static int numMoves;       
    public static int second = 0;     
    public static int third;          
    public static int pos2;           
    public static int pos3;
    public static int j;
    public static int i;

    public static void main(String args[]) {
     try{
         if( args.length == 1 ){
         System.out.println();
         n = Integer.parseInt(args[0]);         //Sets n to commandline int
         int[] locations = new int[ n + 2 ];    //Sets location size 

         for ( j=0; j < n; j++ ){               //For loop - Initially all
             locations[j] = 0;                  //discs are on tower 1
         }

         locations[ n + 1 ] = 2;                //Final disk destination
         numMoves = 1;                          
         for ( i = 1; i <= n; i++){             //Calculates minimum steps
             numMoves *= 2;                     //based on disc size then
         }                                      //subtracts one. ( standard
         numMoves -= 1;                         //algorithm 2^n - 1 )

         //Begins iterative solution. Bound by min number of steps.
         for ( i = 1; i <= numMoves; i++ ){     
             if ( i%2 == 1 ){                   //Determines odd or even.
             second = locations[1];
             locations[1] = ( locations[1] + 1 ) % 3;
             System.out.print("Move disc 1 to ");
             System.out.println((char)('A'+locations[1]));
             }

             else {                             //If number is even.
             third = 3 - second - locations[1];
             pos2 = n + 1;
             for ( j = n + 1; j >=2; j-- )   //Iterative vs Recursive.
                 if ( locations[j] == second )
                 pos2 = j;
             pos3 = n + 1;
             for ( j = n + 1; j >= 2; j-- )  //Iterative vs Recursive.
                 if ( locations[j] == third )
                 pos3 = j;
             System.out.print("Move disc "); //Assumes something is moving.

             //Iterative set. Much slower here than Recursive.
             if ( pos2 < pos3 ){
                 System.out.print( pos2 );
                 System.out.print(" to ");
                 System.out.println((char)('A' + third));
                 locations[pos2] = third;
             }
             //Iterative set. Much slower here than Recursive.
             else {
                 System.out.print( pos3 );
                 System.out.print(" to ");
                 System.out.println((char)('A' + second));
                 locations[ pos3 ] = second;
             }
             }
         }
         }
     }               //Protects Program Integrity.
     catch( Exception e ){
         System.err.println("YOU SUCK. ENTER A VALID INT VALUE FOR #");
         System.err.println("FORMAT : java HanoiIterative #");
     }               //Protects Program Integrity.
     finally{
         System.out.println();
         System.out.println("CREATED BY: KEVIN SEITER");
         System.out.println();
     }
     }
}//HanoiIterative
//--------------------------------------------------------------------------------

Im guessing you didnt really read that iterative one. I didnt either. Its much more complicated. You change change some stuff here and there, but ultimately its always going to be complicated and there is no way around it. While any recursive algorithm CAN be converted to iterative form, it is sometimes much more complicated code wise, and sometimes even significantly less efficient.