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

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.

18.10 Describe the characteristics of recursive methods.
18.11 For the isPalindrome method in Listing 18.3, what are the base cases? How many
times is this method called when invoking isPalindrome("abdxcxdba") ?
18.12 Show the call stack for isPalindrome("abcba") using the method defined in
Listing 18.3.

✓ ✓

Check

Point

18.5 Recursive Helper Methods
Sometimes you can find a solution to the original problem by defining a recursive
function to a problem similar to the original problem. This new method is called a
recursive helper method. The original problem can be solved by invoking the recursive
helper method.

Key
Point

The recursive isPalindrome method in Listing 18.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 18.4.

L ISTING 18.4

RecursivePalindrome.java
1 public class RecursivePalindrome {
2 public static boolean isPalindrome(String s) {

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

4 }
5
6 private static boolean isPalindrome(String s, int low, int high) { helper method

base case

7 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 }