Check Palindromes using Recursion

Java 1.6.2011 No Comments

A palindrome is a word, phrase, number or other sequence of units that can be read the same way in either direction

Palindrome, Wikipedia

A popular problem is how to determine if a String is a Palindrome or not, the following will also assume we are only dealing with Palindromes of single words ie. no spaces or punctuation.

The way to determine this is to compare the characters on the left and right ends of the String. If they don’t match then its not a Palindrome. If they match then we need to compare the next two most inner characters. We continue this until we find a pair that don’t match or we reach the ‘middle’ of the String. If we reach the middle then we have a Palindrome.

Previously we covered how to check if a String is a Palindrome using a loop to check the characters in the String. An alternative is to use recursion to check the String.

As with all recursive solutions we need a base case, and rules to reduce all other cases towards the base case.

For our problem the base case is that any String with less than two characters is a Palindrome.

To reduce a String containing two or more characters towards our base case can be achieved by stripping off the first and last characters from the String. For the String to be a Palindrome the two characters need to be the same AND the remaining String also needs to be a Palindrome.

The Java code showing the use of recursion to check for a Palindrome is available for download by members only. Java mentors are also available to answer any questions you have about the solution.x

Leave a Reply

s2Member®