Program efficiency

  • When you start writing more complex computer programs, you need to think about program efficiency:

      • Two different computer program can perform the same task

      • One of the computer program can use less resources and is more efficient

  • Areas of efficiency:

      • Time:

        • A computer program can finish quicker

      • Memory usage:

        • A computer program can run with less memory

isPalindrome( ) revisited

Take a look at the recursive call to isPalindrome( ): 

   public static boolean isPalindrome(String w) 
   {
        if ( w.length() <= 1 )
        {   // base case
            return true;
        }
        else
        {
           int lastPos = w.length() - 1;

	   return  (w.charAt(0) == w.charAt(lastPos)) && 
                   isPalindrome( w.substring(1, lastPos) );
                                 ^^^^^^^^^^^^^^^^^^^^^^^
        }
   }

w.substring(1, lastPos) will create a new String (and increase usage of computer memory !!)

Reduce memory usage in recursion:   re-use variables

  • To avoid creating new objects in recursion, a common programming technique is:

    • Re-use the variable(s) (as much as possible)

  • Idea on re-using the parameter variable in isPalindrome( ): 

                  012345678901234
  String w = "ABCDEFGHGFEDCBA"   denote a substring with indexes
               <----------->
               w.substring(1,lastpos)

    Example:   we can denote the substring BCDEFGHGFEDCB of w using:

    • The starting position in the string w:   startPos = 1
    • The ending position in the string w:   endPos = 13

How to re-use the parameter variable in the isPalindrome() method

  • We will use the same string in every method invocation (avoid creating more strings)

  • We specify a substring using the startPos and endPos as parameters: 

      isPalindrome(w, startPos=0, endPos=14):

                    012345678901234
        String w = "ABCDEFGHGFEDCBA"
                    <--- input --->

  • A recursive call using a smaller substring will use a different startPos and endPos: 

      isPalindrome(w, startPos=1, endPos=13):

                    012345678901234
        String w = "ABCDEFGHGFEDCBA" 
                     <-- input -->

How to re-use the parameter variable in the isPalindrome() method

  • How can we detect the base cases ? (i.e.: strings with 0 or 1 char)

    A string with 1 character is when: startPos = endPos 

      isPalindrome(w, startPos=7, endPos=7):

                    012345678901234
        String w = "ABCDEFGHGFEDCBA"

    A string with 0 character is when: startPos > endPos 

      isPalindrome(w, startPos=7, endPos=6):

                    01234567890123
        String w = "ABCDEFGGFEDCBA"

  • Test for base cases:     startPos >= endPos

Recursive isPalindrome( ) method that re-uses the input string

Let's start by writing the code to handle the base cases: 

   public static boolean isPalindrome(String w, int startPos, int endPos) 
   {
      if (  )
      {  // Base case
         return true;
      }
      else 
      {
         if (w.charAt(startPos) != w.charAt(endPos))
             return false;
   
         boolean ans = isPalindrome(w, startPos+1, endPos-1);
	 return  ans;
      }
   }

Recursive isPalindrome( ) method that re-uses the input string

Check for base cases (= strings with 0 or 1 character): 

   public static boolean isPalindrome(String w, int startPos, int endPos) 
   {
      if ( startPos >= endPos )
      {  // Base case
         return true;
      }
      else 
      {
         if (w.charAt(startPos) != w.charAt(endPos))
             return false;
   
         boolean ans = isPalindrome(w, startPos+1, endPos-1);
	 return  ans;
      }
   }

Next we solve a smaller problem that will help us solve the original problem.

Recursive isPalindrome( ) method that re-uses the input string

Solve a smaller problem that will help us solve the original problem: 

   public static boolean isPalindrome(String w, int startPos, int endPos) 
   {
      if ( startPos >= endPos )
      {  // Base case
         return true;
      }
      else 
      {
         // Solve a smaller problem that helps us solve the original problem
         boolean helpSol = isPalindrome(w, startPos+1, endPos-1);
 


      }
   }

Then solve the original problem using the helpSol

Recursive isPalindrome( ) method that re-uses the input string

Solve the original problem using the helpSol: 

   public static boolean isPalindrome(String w, int startPos, int endPos) 
   {
      if ( startPos >= endPos )
      {  // Base case
         return true;
      }
      else 
      {
         // Solve a smaller problem that helps us solve the original problem
         boolean helpSol = isPalindrome(w, startPos+1, endPos-1);
 
         return (w.charAt(startPos) == w.charAt(endPos)) && helpSol

      }
   }

We need to adjust the way we invoke the new isPalindrome( ) method in main( )...

Recursive isPalindrome( ) method that re-uses the input string

The new (more efficient) isPalindrome( ) method is invoked with the 0 and length()−1: 

   public static void main(String[] args)
   {
       String s = "Some string";
       int  lastPos = s.length()-1;
       
       ans = isPalindrome(s, 0, lastPos);  // Different way to invoke isPalindrom( ) 
   }

   public static boolean isPalindrome(String w, int startPos, int endPos) 
   {
      if ( startPos >= endPos )
      {  // Base case
         return true;
      }
      else 
      {
         // Solve a smaller problem that helps us solve the original problem
         boolean helpSol = isPalindrome(w, startPos+1, endPos-1);
 
         return (w.charAt(startPos) == w.charAt(endPos)) && helpSol;
      }
   }

DEMO: demo/07-recursion/02-palindrome/Palindrome3.java

Recursive isPalindrome( ) method that re-uses the input string

We can also provide the original isPalindrome( ) to the user with the help of the new isPalinndrome( ): 

   public static void main(String[] args)
   {
       String s = "Some string";

       ans = isPalindrome(s);  // Original way to invoke isPalindrome( )
   }

   public static boolean isPalindrome(String w) // The original palindrome( ) method
   {
       int  lastPos = w.length()-1;

       return isPalindrome(w, 0, lastPos);
   }

   public static boolean isPalindrome(String w, int startPos, int endPos) 
   {
      if ( startPos >= endPos )
      {  // Base case
         return true;
      }
      else 
      {
         // Solve a smaller problem that helps us solve the original problem
         boolean helpSol = isPalindrome(w, startPos+1, endPos-1);
 
         return (w.charAt(startPos) == w.charAt(endPos)) && helpSol;
      }
   }

DEMO: demo/07-recursion/02-palindrome/Palindrome4.java