RECURSION - Introduction to Java Programming - page 746

12 System.out.println( "Is moon a palindrome? "
13 + isPalindrome( "moon" ));
14 System.out.println( "Is noon a palindrome? "
15 + isPalindrome( "noon" ));
16 System.out.println( "Is a a palindrome? " + isPalindrome( "a" ));
17 System.out.println( "Is aba a palindrome? " +
18 isPalindrome( "aba" ));
19 System.out.println( "Is ab a palindrome? " + isPalindrome( "ab" ));
20 }
21 }

Is moon a palindrome? false
Is noon a palindrome? true
Is a a palindrome? true
Is aba a palindrome? true
Is ab a palindrome? false

The substring method in line 8 creates a new string that is the same as the original string
except without the first and last characters. Checking whether a string is a palindrome is
equivalent to checking whether the substring is a palindrome if the two end characters in the
original string are the same.
20.10 Describe the characteristics of recursive methods.
20.11 For the isPalindrome method in Listing 20.3, what are the base cases? How many
times is this method called when invoking isPalindrome("abdxcxdba") ?
20.12 Show the call stack for isPalindrome("abcba") using the method defined in
Listing 20.3.

✓ ✓

Check

Point

20.5 Recursive Helper Methods
Sometimes you can find a recursive solution by slightly changing the original problem.
This new method is called a recursive helper method .

Key
Point

The recursive isPalindrome method in Listing 20.3 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 recur-
sive method. Since the original method is isPalindrome(String s) , you have to create
the new method isPalindrome(String s, int low, int high) to accept additional
information on the string, as shown in Listing 20.4.

L ISTING 20.4 RecursivePalindrome.java
1 public class RecursivePalindrome {
2
3

public static boolean isPalindrome(String s) {

return isPalindrome(s, 0 , s.length() - 1 );

4 }
5
6
7

private static boolean isPalindrome(String s, int low, int high) {

helper method
base case if (high <= low) // Base case

8 return true;

9 else if (s.charAt(low) != s.charAt(high)) // Base case

base case

10 return false;

11 else

12 return isPalindrome(s, low + 1 , high - 1 );

13 }
14