Recursion:   a divide-and-conquer problem solving technique

  • Recall:   the fundamental principe of the divide-and-conquer technique:

      1. Divide a (complex) problem into smaller simpler problems

      2. Solve (= conquer) the smaller simpler problems individually

    We used the divide-and-conquer technique in developing the Calendar program:

  • Recursion is also a divide-and-conquer technique.

  • Special characteristics of recursion are:

      • The original problem is divided into one or more smaller problems....

      • Each of smaller problem has the same formulation as the original problem

When can we use recursion ?
 

Suppose we need to solve some problem of size n:

 
 

 

When can we use recursion ?
 

Consider the other identical (but) smaller problems:

 
 

Suppose that we (already) have the solutions for all the smaller problems, i.e.: we do not need to solve them

When can we use recursion ?
 

If we can use the solutions of the smaller problems to find Solution(n) (= solution of the original problem):

 
 

Then:   we can use recursion to solve the Problem(n)

The difficulty in using recursion
 

The main difficulty of using recursion is to find a way to use the smaller solutions to construct Solution(n):

 
 

The "combine" step is problem-dependent

Example: why we can use recursion to compute the factorial function
 

Suppose we need to compute factorial(10):

 
 

 

Example: why we can use recursion to compute the factorial function
 

Suppose we have the solution for the smaller problem factorial(9):

 
 

Question:   can we use   362880   to compute factorial(10) ?

Example: why we can use recursion to compute the factorial function
 

We can compute factorial(10) using the value 362880 as follows:   10! = 10 × 362880

 
 

Therefore:   we can use recursion to solve the factorial problem

The factorial( ) function revisited

How to write factorial( ) as a divide-and-conquer algorithm: 

   int factorial(int n)
   {
     
     

    
     
     
     
        
                             
	
                    
      
     
   }

Let's write the factorial( ) method again, but this time exposing the divide-and-conquer technique

The factorial( ) function revisited

The base case(s) is unchanged: 

   int factorial(int n)
   {

   

      if ( n == 0 )
         return 1;           // Base case

   
  
                           
	
                    
      
    
   }

In the divide step, we delegate someone else to solve some smaller problem(s) that can be used to solve the original problem

The factorial( ) function revisited

Divide:   tell someone else to solve the smaller problem factorial(n-1): 

   int factorial(int n)
   {
      int helpSol;     // Solution to the smaller problem


      if ( n == 0 )
         return 1;           // Base case
      else
      {
         helpSol = factorial(n-1); // Tell someone to solve this
                                   // (We receive the solution in helpSol) 
	
                         
        
      }
   }

Next:   in the conquer step, we use helpSol to find solution for the original problem

The factorial( ) function revisited

Conquer:   we solve factorial(n) using helpSol: 

   int factorial(int n)
   {
      int helpSol;     // Solution to the smaller problem
      int mySol;       // Solution to my problem

      if ( n == 0 )
         return 1;           // Base case
      else
      {
         helpSol = factorial(n-1); // Tell someone to solve this
                                   // (We receive the solution in helpSol)
	 mySol = n*helpSol;        // Solve original problem using the 
                                   // solution of the smaller problem 

      }
   }

Finally, we return the solution...

The factorial( ) function revisited

The factorial(n) method written as a divide-and-conquer algorithm: 

   int factorial(int n)
   {
      int helpSol;     // Solution to the smaller problem
      int mySol;       // Solution to my problem

      if ( n == 0 )
         return 1;           // Base case
      else
      {
         helpSol = factorial(n-1); // Tell someone to solve this
                                   // (We receive the solution in helpSol)
	 mySol = n*helpSol;        // Solve my problem using the 
                                   // solution of the smaller problem 
         return(mySol);
      }
   }

DEMO: demo/07-recursion/01-factorial/DivideAndConquer.java

Important insight to help you understand (and write) recursive methods

You must distinguish between:

  • The factorial( ) method that solves the original problem            and
  • The factorial( ) method that solves a smaller problem

I like to use the roles   you   and your helper to make the distinction: 

   int factorial(int n)  <--- This factorial( ) represents "YOU" 
   {
      int helpSol;
      int mySol;

      if ( n == 0 )
         return 1;
      else
      {
         helpSol = factorial(n-1);   <--- This factorial( ) is your "helper" 
                            // This factorial( ) solves a smaller problem
	 mySol = n*helpSol; 

         return (mySol);
      }
   }

What happens in recursion:   recursion will run another copy of the same method

Simplifying the factorial( ) function

Previously:   the factorial(n) method written as a divide-and-conquer algorithm: 

   int factorial(int n)
   {
      int helpSol;     // Solution to the smaller problem
      int mySol;       // Solution to my problem

      if ( n == 0 )
         return 1;           // Base case
      else
      {
         helpSol = factorial(n-1); // Tell someone to solve this
                                   // (We receive the solution in helpSol)
	 mySol = n*helpSol;        // Solve my problem using the 
                                   // solution of the smaller problem 
         return(mySol);
      }
   }

We can simplify the algorithm with substitution...

Simplifying the factorial( ) function

Substitute helpSol with factorial(n-1) : 

   int factorial(int n)
   {
      int helpSol;     // Solution to the smaller problem
      int mySol;       // Solution to my problem

      if ( n == 0 )
         return 1;           // Base case
      else
      {
         helpSol = factorial(n-1); // Tell someone to solve this
                                   // (We receive the solution in helpSol)
	 mySol = n*factorial(n-1); // Solve my problem using the 
                                   // solution of the smaller problem 
         return(mySol);
      }
   }

We can simplify the algorithm further with short-circuiting some computations...

Simplifying the factorial( ) function

Return the result   n*factorial(n-1) directly: 

   int factorial(int n)
   {
      int helpSol;     // Solution to the smaller problem
      int mySol;       // Solution to my problem

      if ( n == 0 )
         return 1;           // Base case
      else
      {
         helpSol = factorial(n-1); // Tell someone to solve this
                                   // (We receive the solution in helpSol)
	 return  n*factorial(n-1); // Solve my problem using the 
                                   // solution of the smaller problem 
         return(mySol);
      }
   }

We can simplify the algorithm with substitution...

Simplifying the factorial( ) function

Result: we get back the original factorial( ) method 

   int factorial(int n)
   {
      
      

      if ( n == 0 )
         return 1;           // Base case
      else
      {
         
                                   
	 return  n*factorial(n-1); // Solve my problem using the 
                                   // solution of the smaller problem 
         
      }
   }