RECURSION - Introduction to Java Programming: Comprehensive Version - page 715

14
15 public static void main(String[] args) {
16 System.out.println( "Is moon a palindrome? "
17 + isPalindrome( "moon" ));
18 System.out.println( "Is noon a palindrome? "
19 + isPalindrome( "noon" ));
20 System.out.println( "Is a a palindrome? " + isPalindrome( "a" ));
21 System.out.println( "Is aba a palindrome? " + isPalindrome( "aba" ));
22 System.out.println( "Is ab a palindrome? " + isPalindrome( "ab" ));
23 }
24 }

Two overloaded isPalindrome methods are defined. The first, isPalindrome(String s) ,
checks whether a string is a palindrome, and the second, 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 define a second method that
receives additional parameters. Such a method is known as a recursive helper method .
Helper methods are very useful in designing recursive solutions for problems involving
strings and arrays. The sections that follow give two more examples.

recursive helper method

18.5.1 Recursive Selection Sort
Selection sort was introduced in Section 7.11. Recall that it finds the smallest element in the
list and swaps it with the first element. It then finds the smallest element remaining and swaps
it with the first element in the remaining list, and so on until the remaining list contains only
a single element. The problem can be divided into two subproblems:

Find the smallest element in the list and swap it with the first element.

■

Ignore the first element and sort the remaining smaller list recursively.

■

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

L ISTING 18.5

RecursiveSelectionSort.java
1 public class RecursiveSelectionSort {
2 public static void sort( double [] list) {

3 sort(list, 0 , list.length - 1 ); // Sort the entire list

4 }
5
6 private static void sort( double [] list, int low, int high) {
7 if (low < high) {
8 // Find the smallest number and its index in list[low .. high]
9 int indexOfMin = low;
10 double min = list[low];
11 for ( int i = low + 1 ; i <= high; i++) {
12 if (list[i] < min) {
13 min = list[i];
14 indexOfMin = i;
15 }
16 }
17
18 // Swap the smallest in list[low .. high] with list[low]
19 list[indexOfMin] = list[low];
20 list[low] = min;
21

helper method
base case