Solving problems using recursion

  • All recursive methods have the following characteristics:

      1. The recursive method uses an if-else or a switch statement that leads to different cases of execution.

      2. There are one or more base cases (= the simplest problems) are used to stop the recursion.

      3. Every recursive call reduces the original problem, bringing it increasingly closer to a base case until it becomes that case.

Thinking recursively....

  • Recursive thinking is quite "natural"

  • Example:

      • Finish drinking a cup of coffee ....

  • A recursive method that would simulate "finish drinking a cup of coffee" will look like this: 

      public static void  drinkeCoffee(Cup cup)
{
   if ( cup.isEmpty( ) ) // Check if cup is not empty
   {
      return;            // Done, just return
   }
   else
   {
      cup.takeOneSip();  // Take one sip
      drinkCoffee(cup);  // Drink again (cup now has LESS coffee !)
   }
}

Problem 1: print a message n times using recursion

  • Write a recursive method that prints out an (input) message exactly n times:             

       public static void nPrintln(String message, int times) 
   {
      if ( times == 0 ) 
      {
         return;
      }
      else
      {
         System.out.println(message);
	 nPrintln(message, times - 1);
      }
   }

Problem 1: print a message n times using recursion

  • Base case: when number of times = 0, we can stop the recursion:                          

       public static void nPrintln(String message, int times) 
   {
      if ( times == 0 ) 
      {
         return;
      }
      else
      {
         System.out.println(message);
	 nPrintln(message, times - 1);
      }
   }

Problem 1: print a message n times using recursion

  • Otherwise: we reduce the problem to a smaller (but similar) problem and recurse: 

       public static void nPrintln(String message, int times) 
   {
      if ( times == 0 ) 
      {
         return;
      }
      else
      {
         System.out.println(message); // Reduce the problem
	 nPrintln(message, times-1);  // So that we can recurse
      }
   }

Problem 1: print a message n times using recursion    DEMO 

   public static void main(String[] args)
   {
      nPrintln("Hello World", 4);
   }

   public static void nPrintln(String message, int times) 
   {
      if ( times == 0 ) 
      {
         return;
      }
      else
      {
         System.out.println(message); // Reduce the problem
	 nPrintln(message, times-1);  // So that we can recurse
      }
   }

Problem 2: write a recursive isPalindrome() method   Reducing to a smaller palindrome

  • Consider a palindrome: 

         ABCDEFGHGFEDCBA

  • If you remove the first and last letter of a palindrome, you get a smaller palindrome: 

         ABCDEFGHGFEDCBA
      <----------->
      smaller palindrome

Problem 2: write a recursive isPalindrome() method   Base cases

  • If you keep removing the first and last letter from a palindrome: 

         ABCDEFGHGFEDCBA
      BCDEFGHGFEDCB 
       CDEFGHGFEDC  
        DEFGHGFED   
         EFGHGFE    
          FGHGF   
           GHG    
            H  <--- easy palindrome !!

    You will get a word that has 0 or 1 character.

  • Base (simple) cases:

    • A word of length = 0 or 1 is always a palindrone !!!

Recursive method to determine if a word is a palindrome

Let write the code for the base case first: 

   public static boolean isPalindrome(String w) 
   {
        if ( w.length() <= 1 )
        {   // base case
            return true;
        }
        else
        {
            // Reduce the problem
            int lastPos = w.length() - 1;
            if ( w.charAt(0) != w.charAt(lastPos) )
                return false;   // w is not a palindrome
            
            // After reducing problem with 1 step, use recursion
            boolean ans = isPalindrome( w.substring(1, lastPos) );
            return ans;
        }
   }

 

Recursive method to determine if a word is a palindrome

A word of length ≤ 1 is always a palindrome: 

   public static boolean isPalindrome(String w) 
   {
        if ( w.length() <= 1 )
        {   // base case
            return true;
        }
        else
        {
            // Reduce the problem
            int lastPos = w.length() - 1;
            if ( w.charAt(0) != w.charAt(lastPos) )
                return false;   // w is not a palindrome
            
            // After reducing problem with 1 step, use recursion
            boolean ans = isPalindrome( w.substring(1, lastPos) );
            return ans;
        }
   }

Next: in order to use recursion, we must reduce the problem to a smaller one.

Recursive method to determine if a word is a palindrome

A word of length ≤ 1 is always a palindrome: 

   public static boolean isPalindrome(String w) 
   {
        if ( w.length() <= 1 )
        {   // base case
            return true;
        }
        else
        {
            // Reduce the problem: check 1st and last char
            int lastPos = w.length() - 1;
            if ( w.charAt(0) != w.charAt(lastPos) )
                return false;   // w is not a palindrome
            
            // We still need to check the rest of the word !
            boolean ans = isPalindrome( w.substring(1, lastPos) );
            return ans;
        }
   }

After reducing the problem, we can use recursion (we have a smaller version of the original problem)

Recursive method to determine if a word is a palindrome

Use recursion to solve the correct smaller problem: 

   public static boolean isPalindrome(String w) 
   {
        if ( w.length() <= 1 )
        {   // base case
            return true;
        }
        else
        {
            // Reduce the problem: check 1st and last char
            int lastPos = w.length() - 1;
            if ( w.charAt(0) != w.charAt(lastPos) )
                return false;   // w is not a palindrome
            
            // After reducing problem with 1 step, use recursion
            boolean ans = isPalindrome( w.substring(1, lastPos) );
            return ans;
        }
   }

Next slide contains code that you can run in BlueJ

Recursive method to determine if a word is a palindrome   DEMO 

   public static void main(String[] args)
   {
      boolean r = isPalindrome("abcba");
   }

   public static boolean isPalindrome(String w) 
   {
        if ( w.length() <= 1 )
        {   // base case
            return true;
        }
        else
        {
            // Reduce the problem: check 1st and last char
            int lastPos = w.length() - 1;
            if ( w.charAt(0) != w.charAt(lastPos) )
                return false;   // w is not a palindrome
            
            // After reducing problem with 1 step, use recursion
            boolean ans = isPalindrome( w.substring(1, lastPos) );
            return ans;
        }
   }