The Power of Recursion

               “To iterate is human, to recurse divine”. Recursion is indeed a powerful technique capable of simplifying various complex programming tasks. Perhaps one of the best known examples of this is the Towers of Hanoi Problem. In short the problem consists of three towers and disks of various sizes. These disks are stacked on one tower (smallest on top) and are to be moved to another tower using the third tower as auxiliary. Two rules that must be observed are a) only the top disk can be moved from any tower at a time and b) a larger disk cannot be placed on top of a smaller one. The task of writing an algorithm that will get us the set of moves that must be performed for moving n disks in the way defined above is not an easy one. However using recursion it can be hugely simplified. But before writing a recursive solution to the problem lets delve further into what recursion is and how it can be used to solve simpler problems.

               Recursion is the process of defining a problem in terms of itself. To understand this, consider the following situation. Suppose we need to find the factorial of a number say 3. Now 3! can be written as 3! = 3 X 2!. In general we can write n! as n! = n X (n-1)!. So we have represented the problem in terms of itself. Thus if we can compute (n-1)! then we can also find n! with just a single multiplication. Also we must consider a base case. This base case is where the problem must terminate. For the factorial example the base case would be 0! which is equal to 1. 0! factorial is chosen as the base case because this is the least number whose factorial can be calculated. Now, for the implementation part, we can make use of a function which calls itself (recursion). Note that since here we have a function that solves a problem by calling itself, we have in fact represented the problem in terms of itself i.e. we have represented the problem as:

                factorial(n)=n * factorial(n-1) .

A recursive function (function that calls itself) to accomplish the above task is shown below :

int factorial(int n){
     if(n==0) return 1;//The base case
     else return n*factorial(n-1);//The recursion
}

The following figure explains the working : 

               Each box represents a call to a function and the first line in each box shows the value with which it is called. Each call to the function will return a value indicated by the number beside the red arrow. The rest is self-explanatory.

               So, we were able to write a recursive solution to the factorial problem once we had figured out two crucial things

     1. The base case: the case where the recursion will terminate. (n = 0 in the above case).
     2. How the function represented in terms of itself. (factorial ( n ) = n * factorial (n -1 ) ).

               The above technique can be used to approach a recursive problem. Now consider another problem, finding the nth Fibonacci number. Fibonacci numbers start with 0 , 1 , . . . and each successive no is the sum of the previous two. The Fibonacci series thus goes like 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 . . . and so on. So for finding the nth Fibonacci number we can just sum the previous two. We can represent this as fib(n) = fib(n-1) + fib(n-2), where fib(int n) is a function that finds the nth Fibonacci number. Here the first two numbers remain constant so they constitute the base cases which are Fib(1)=0 & Fib(2)=1, representing the fact that the first Fibonacci number is 0 and the second Fibonacci number is 1. A recusive function for this can be written as :

int fib(int n){
     if(n==1) return 0 ; //Base case #1         
     else if(n==2) return 1 ; //Base case #2
     else return fib(n-1) + fib(n-2) ; // The recursion 
}

               Note that in both of the above problems we were never concerned with the actual theme of the problem (finding factorial of a number or finding the nth Fibonacci number). We assumed that a function would do that for us and just represented the problem in terms of itself and wrote a straightforward algorithm for it. The rest recursion did for us automatically. Such is the power of recursion.

               

               So to sum up, the idea behind recursion is that a problem can be solved by breaking it up into smaller pieces, solving each of those smaller pieces by breaking them up into even smaller pieces and so on till we reach a piece that can be solved non trivially(the base case).

               

               For the above two cases simpler iterative solutions are possible and perhaps more efficeitn, but for certain complex problems it is easier to write a recursive solution than an iterative one. The Towers of Hanoi problem illustrates this fact.

               Let us first state the Towers of Hanoi problem formally:  

                

               The problem consists of three pegs/towers and a number of disks of varying sizes which can be slid onto any peg/tower. Each disk is of a different size. Initially the disks are stacked on one of the towers (lets call it A) one atop another with the smallest one at the top. The goal is to move all disks from tower A to another tower (lets call this C), using the third tower (B) as auxiliary while obeying the following rules:

1. Only the top disk can be moved from a tower at any time.

2.  No disk must be placed on top of a smaller disk.

Let us consider a recursive strategy for moving n disks.

Step 1 :  Move n-1 disks from Tower A to Tower B

Step 2 :  Move 1 disk from Tower A to Tower C

Step 3 : Move n-1 disks from Tower B to Tower C

               This would solve the problem. (Note that here we are not concerned with how we would move the n-1 disks. The steps are shown visually in the figures below :

               The base case here would be that of a single disk which we can move directly from Tower A to Tower C. The towers are named A, B, C where B is the auxiliary tower. The recursive solution is shown below :

public void move( int numberofdisks, char firstTower, char auxTower, char finalTower )
{
     if(numberofdisks == 1){
          System.out.println("Move disk from "+firstTower+" to "+finalTower);  //#0
     }
     else{
          move(numberofdisks-1,firstTower,finalTower,auxTower);   //#1
          System.out.println("Move disk from "+firstTower+" to "+finalTower);  //#2
          move(numberofdisks-1,auxTower,firstTower,finalTower);  //#3
     }
} 

Explanation :

#0 : This illustrates the base case where a single disk can be moved from the first to the final tower directly.

#1 : This is Step 1 of the solution. Here we move n-1 disks from firstTower to auxTower using the finalTower as auxiliary. Note that in the function prototype auxiliary tower is denoted as the third parameter (first is the no. of disks), so here we had to use finalTower as auxiliary(third parameter) in the actual function call.

#2 : This is Step 2 of the solution.

#3 : This is Step 3 of the solution. Here we move n-1 disks from auxTower to finalTower using firstTower the as auxiliary. So here we had to use firstTower as auxiliary(third parameter) in the actual function call.

             For 3 disks the above program the function call move(3, ‘A’, ’B’, ’C’) displays the following steps :

Move disk from A to C
Move disk from A to B
Move disk from C to B
Move disk from A to C
Move disk from B to A
Move disk from B to C
Move disk from A to C

               “Move disk” obviously means moving the top disk from the tower.

               This above solution clearly demonstrates how easily recursion can be used to solve such complex problems. The use of recursion in an algorithm, however, has both advantages and disadvantages. The main advantage is usually simplicity. (for solving certain problems like the Towers of Hanoi, preorder/inorder/postorder traversal of binary trees etc.). Also some problems like displaying a list of all files of the system cannot be solved without recursion. The main disadvantage is often that the algorithm may require large amounts of memory if the depth of the recursion is very large.

               Recursive techniques are also widely used to implement important algorithms based on the Divide & Conquer approach like quicksort and merge sort as well as graph based algorithms like Depth First Search.