21.10. Key Terms

[Page 641 ( continued )]

19.5. Recursive Helper Methods

The preceding recursive isPalindrome method is not efficient, because it creates a new string for every recursive call. To avoid creating new strings, you can use the low and high indices to indicate the range of the substring. These two indices must be passed to the recursive method. Since the original method is isPalindrome(String s) , you have to create a new method isPalindrome(String s, int low, int high) to accept additional information on the string, as shown in Listing 19.4.

Listing 19.4. Palindrome Using a Helper Method

 1   public static boolean   isPalindrome(String s) {  2   return   isPalindrome(s,     , s.length() -   1   );  3 }  4  5   public static boolean   isPalindrome(String s,   int   low,   int   high) {  6   if   (  high <= low  )  // Base case  7   return true   ;  8   else if   (  s.charAt(low) != s.charAt(high)  )  // Base case  9   return false   ; 10   else   11    return   isPalindrome(s, low +   1   , high -   1   );  12 } 

Two overloaded isPalindrome methods are declared. The first method, isPalindrome (String s) , checks whether a string is a palindrome, and the second method, isPalindrome (String s, int low, int high) , checks whether a substring s(low..high) is a palindrome. The first method passes the string s with low = 0 and high = s.length() “ 1 to the second method. The second method can be invoked recursively to check a palindrome in an ever-shrinking substring. It is a common design technique in recursive programming to declare a second method that receives additional parameters. Such a method is known as a recursive helper method .

---

[Page 642]

Helper methods are very useful to design recursive solutions for problems involving strings and arrays. The following sections present two more examples.

19.5.1. Selection Sort

Selection sort was introduced in §6.8.1, "Selection Sort." Recall that selection sort finds the largest number in the list and places it last. It then finds the largest number remaining and places it next to last, and so on until the list contains only a single number. The problem can be divided into two subproblems:

• Find the largest number in the list and swap it with the last number.

• Ignore the last number and sort the remaining smaller list recursively.

The base case is that the list contains only one number. Listing 19.5 gives the recursive sort method.

Listing 19.5. Recursive Sort Method

 1    public static void  sort(   double   [] list) {   2   sort(list, list.length -   1   );  3 }  4  5    public static void   sort(   double   [] list,   int   high) {  6   if   (high >   1   ) {  7  // Find the largest number and its index  8   int   indexOfMax =     ;  9   double   max = list[     ]; 10   for   (   int   i =   1   ; i <= high; i++) { 11   if   (list[i] > max) { 12         max = list[i]; 13         indexOfMax = i; 14       } 15     } 16 17  // Swap the largest with the last number in the list  18     list[indexOfMax] = list[high]; 19     list[high] = max; 20 21  // Sort the remaining list  22  sort(list, high -   1   );  23   } 24 } 

Two overloaded sort methods are declared. The first method, sort(double[] list) , sorts an array in list[0..list.length - 1] , and the second method, sort(double[] list, int high) , sorts an array in list[0..high] . The second method can be invoked recursively to sort an ever-shrinking subarray.

19.5.2. Binary Search

Binary search was introduced in §6.7.2, "The Binary Search Approach." For binary search to work, the elements in the array must already be ordered. The binary search first compares the key with the element in the middle of the array. Consider the following three cases:

• ---

  [Page 643]

• Case 1: If the key is less than the middle element, recursively search the key in the first half of the array.

• Case 2: If the key is equal to the middle element, the search ends with a match.

• Case 3: If the key is greater than the middle element, recursively search the key in the second half of the array.

Case 1 and Case 3 reduce the search in a smaller list. Case 2 is a base case when there is a match. Another base case is that the search is exhausted without a match. Listing 19.6 gives a clear, simple solution for the binary search problem using recursion.

Listing 19.6. Recursive Binary Search Method

 1   public static int   recursiveBinarySearch(   int   [] list,   int   key) {  2   int   low =     ;  3   int   high = list.length -   1   ;  4   return    recursiveBinarySearch(list, key, low, high)  ;  5 }  6  7   public static int    recursiveBinarySearch(   int   [] list,   int   key,  8    int   low, int high)  {  9   if   (low > high)  // The list has been exhausted without a match  10   return   -low -   1   ;  // Return -insertion point - 1  11 12   int   mid = (low + high) /   2   ; 13   if   (key < list[mid]) 14   return    recursiveBinarySearch(list, key, low, mid -   1   )  ; 15   else if   (key == list[mid]) 16   return   mid; 17   else   18   return    recursiveBinarySearch(list, key, mid +   1   , high)  ; 19 } 

The first method finds a key in the whole list. The second method finds a key in the list with index from low to high .

The first binarySearch method passes the initial array with low = 0 and high = list.length - 1 to the second binarySearch method. The second method is invoked recursively to find the key in an ever-shrinking subarray.