Section 12.1 Recursive Thinking
A palindrome is a word, phrase, or sentence that reads the same, backward or forward, excluding spaces, punctuation, and letter case. For example, "racecar" and "Was it a car or a cat I saw?" are well-known palindromes. How might you write a program to test whether a String is a palindrome?
An iterative algorithm for checking that a String is a palindrome involves simultaneously iterating from the first character and the last character towards the center of the string. On each iteration we must test that corresponding characters are equal. The moment an equality test fails, we know that the String is not a palindrome.
// Palindrome.java
public class Palindrome {
// Iterative implementation of palindrome checking
public static boolean isPalindrome(String lets) {
// Loop from 0 to center of lets
for (int i=0; i < lets.length()/2; i++) {
// Compute last char index from first and length
int j = lets.length()-1-i;
// Fail if char mismatch
if ( lets.charAt(i) != lets.charAt(j) ) {
return false;
}
}
return true;
}
public static void main(String[] args) {
// Palindrome tests
String pal1 = "RACECAR";
String pal2 = "WASITACARORACATISAW"; // Was it a car or a cat I saw?
String pal3 = "TURNYOURWOUNDSINTOWISDOM"; // Turn your wounds into wisdom.
System.out.println( isPalindrome(pal2) );
System.out.println( isPalindrome(pal3) );
}
}
isPalindrome(…) Iterative Implementation
Listing 12.1.1 is an iterative implementation of a method that tests a String for a palindrome. This program iterates
i starting at 0 and continues while i < lets.length()/2 (half the String length). Within the loop we calculate the other character index to compare as j = lets.length()-1-i.When testing Strings having an even number of chars, pairs of character indexes to compare move inward toward each other and meet at adjacent points. For example when
lets.length() == 6, the index of the first char is 0 and the last is 5. In other words, when i == 0, j = 6-1-0 = 5; we are comparing the first and last chars of the String. When i == 1, j = 5-1-1=4, and when i == 2, j == 3, and our iteration is complete.For a String with an odd number of chars, say 7, the loop extent does not change, but iteration terminates with one lone character at the center.
lets.length()/2 is still 3 because we lose the fractional part with integer division. The variable i starts at 0 and again increments to 1 and then 2. The value of j is computed as 7-1-0 == 6 and decrements to 5 and 4. The char at index 3 is not tested. This is not a problem because this is the middle char, which is a singleton and can be ignored because it has no char that must be matched.The following test of our iterative implementation produces the expected results.
javac Palindrome.java java Palindrome true false
What about a recursive version of
isPalindrome(String lets)? Can you identify a way to determine if a String is a palindrome having as part of the solution a test that a substring of the main String is a palindrome?The first step is to check that the first and last characters in the String are equal. What’s left is to continue with the chars in the middle. In a way, we are checking that the middle chars themselves constitute a smaller palindrome. Why not use the same
isPalindrome(…) method to test this inner substring, without the first and last chars? Wouldn’t this solve our problem? In other words, we can say that a String is a palindrome if the first and last chars are equal and the remaining part of the String without the end characters is also a palindrome. A String of length 1 is a palindrome by definition because the first and last characters are identical.
Listing 12.1.2 is a recursive program that implements this idea.
// Palindrome.java
public class Palindrome {
// Recursive implementation of palindrome checking
public static boolean isPalindrome( String lets ) {
System.out.println(lets); // Show string tested
if (lets.length() <= 1) { // BASE CASE 1
return true;
}
else if ( lets.charAt(0) == lets.charAt(lets.length()-1)) {
String smaller = lets.substring( 1, lets.length()-1);
return isPalindrome( smaller ); // RECURSIVE CASE
} else {
return false; // BASE CASE 2 (no match)
}
}
public static void main(String[] args) {
// Palindrome tests
String pal1 = "RACECAR";
String pal2 = "WASITACARORACATISAW"; // Was it a car or a cat I saw?
String pal3 = "TURNYOURWOUNDSINTOWISDOM"; // Turn your wounds into wisdom.
System.out.println( isPalindrome(pal2) );
System.out.println( isPalindrome(pal3) );
}
}
isPalindrome(…) Recursive ImplementationWe start our method by checking for special cases. Any String of length 1 (or even 0) is automatically considered a palindrome, by definition. There is nothing more to do so we return
true immediately. This is called the base case.Otherwise, the String is a palindrome if the characters at both ends are equal and the substring excluding the end characters is also a palindrome. To test for the smaller palindrome, we invoke the same method, passing the smaller substring and returning whatever the recursive method returns as the overall result. This is called the recursive case.
In the test of our recursive method we print the intermediate Strings tested in order to watch our method recurse and the String reduce in length.
javac Palindrome.java java Palindrome WASITACARORACATISAW ASITACARORACATISA SITACARORACATIS ITACARORACATI TACARORACAT ACARORACA CARORAC ARORA ROR O true TURNYOURWOUNDSINTOWISDOM false
How do these two implementations compare? More initial thought and planning was required for the iterative version to ensure we calculated the indexes correctly. Arguably, once you see it, the recursive version is more elegant. The recursive version of
isPalindrome(…) says that Strings of length 0 or 1 are a palindrome by definition, and if the end characters are equal then the answer is delegated to testing if the central substring constitutes a palindrome.We’ve constructed a way to solve the problem in terms of itself. This is recursion.
Recursive methods always handle one or more recursive cases and one or more bases cases. An if-statement is commonly used to identify these cases, but the cases are not always obvious. Nevertheless, at least one of each case must be handled, always.
Recognize how
isPalindrome(…) in Listing 12.1.2 stops executing. The String being tested gets shorter by two on each recursive call. This makes progress toward moving us closer to the base case of a String with 1 or even 0 chars. We must always be moving toward the base case condition to avoid an infinite recursion. For example, what would happen if we swapped the order of the first two branches in the if-statement of Listing 12.1.2? Trace the modified program and make a prediction.
