Palindromes

To identify (using recursion) if a word inputted by the user is a palindrome or not.

To better understand this project, we must first ask ourselves the question: What is a palindrome? By definition, a palindrome is any word that is exactly the same when written or read either forwards or backwards. For example, the words madam and racecar are both palindromes.

A palindrome is a word that is the same when read forwards and backwards.

Palindromes can also be phrases, or even number sequences. One prime example is the date featured in the image above. February 22nd, 2020, is an example of a palindrome. So is the phrase "No lemon, no melon". In essence, the possibility of palindromes are endless, as long as you adhere to the rule of forwards = backwards.

Purpose

This program aims to identify if a user inputted phrase is a palindrome. In this case, we will not be considering numerical palindromes; only phrases and words of type String. The code utilizes recursion in order to iterate through the String in order to identify palindromes.

But before doing so, the String phrase must contain characters (type char) of similar Unicode, meaning that all letters need to be either uppercase or lowercase. In this case, I chose to represent all char types as lowercase, in order for the program to be visually appealing and not appear as if the output is screaming at the user. In order to "transform" all Strings to lowercase and perform additional formatting (more on that), a sorting method is needed.

sorter(String str)

The purpose of the sorter() method is implied in the name - it sorts the letters of all user inputted phrases/words, transforming all chars to lowercase, and removing all spaces or unnecessary characters (such as ?,!,@,#,$, etc.).

The inherent java method .toLowerCase() is used on the targeted String, and the new, all lowercase string is saved in the variable "sort".

sorter(String str){
    String sort = str.toLowerCase();
    ...

Next, all spaces are removed via the inherent java method replaceAll(), which replaces all occurrences of one character with another character.

sorter(String str){
    String sort = str.toLowerCase();
    sort = sort.replaceAll(" ","");
    ...

In this piece of code, replaceAll() was used to replace all spaces (" ") with empty strings (""), effectively removing all spaces from the sort String. Lastly, the inherent java method isLetter(), which verifies if a character is a letter (A-Z) or not. This was used in a for-loop to remove the special characters I mentioned before.

sorter(String str){
    String sort = str.toLowerCase();
    sort = sort.replaceAll(" ","");
    for(int i = 0; i < sort.length(); i++){
        if(Character.isLetter(sort.charAt(i)) == false){
            sort = sort.replace(sort.substring(i, i+1), "");
        }
    }        
    return sort;
}

The final part of the sorter method essentially detects if a character is a letter, and if it is not, simply replaces it with the character directly after it. It can be thought of as "plucking out" the special character and then "shifting" the remaining part of the string to fill the gap.

EX: sorter("No lemon, No melon!") returns nolemonnomelon

Once the sorter() method is used, the boolean method pal() comes into play.

pal(String str, int start, int end)

In order to better this method, please access the Github Repository.

The pal() method accepts three arguments - a string, and two integers (type int) that each signify the start and end indexes of the string (This was done for simplicity sake, and the index arguments were later utilized in the isPal() method).

In synopsis, the pal() method checks the string for three possible occurences:

1. If the string is of length 1 (meaning start = end), then return true.

2. If the length is even (divisible by 2 without remainder; %2 = 0), then recourse through, shifting the "scope" to the 2nd and 2nd to last characters.

3. If the start and end character don't match, return false.

Step 2 is done for both strings of odd and even length, although it is necessary to isolate even-length palindromes. As a side note, the term "scope" may seem confusing, which calls for elaboration.

What I define as scope is the group of chars currently being compared, and everything between them. For example, if pal() were to run on "nolemonnomelon", it would first compare the first n of the string, and the last n of the string.

nolemonnomelon

Next, the scope would shrink to the second letters form either side.

nolemonnomelon

This continues to occur as long as the comparison is true, meaning the letters being compared are the same.

Lastly, as with all recursive techniques, the base case is reached, of either a single letter (in cases of odd-length palindromes) or a pair of letters (in cases of even length-length palindromes). Now do you see why it was important to isolate each case?

For the final letter, rule 1 is applied. For the pair of letters, they are simply compared, and, if the letters are the same, the next iteration reaches a point where the start equals the end, and true is returned.

isPal(String str)

The isPal() method is quite straightforward-it simply runs the pal() method on the provided string, while substituting the start and end arguments of pal() with the calculated indexes.

int n = str.length();
...
if (n == 0){
    return true;
}
return pal(str, 0, n-1);

Now, the reason as to why arguments of start and end were provided for pal() is revealed; in order for recursion to occur, the indexes must be reduced resulting in the "scope" I mentioned earlier.

This brings us to the final step - a Tester class.

Tester

The tester class for this program is the RecursivePalindromeTester class. In this class, code was added that:

• accepts user input via a Scanner class object,

• ask user to begin the palindrome testing,

• and properly displayed output based upon the return value of isPal() and pal().

An example run is shown below (Input is bolded):

Begin? (Y/N):
Y

Continue? (Y/N):
N

Please enter a word:
No lemon, No melon!

The word is a palindrome

Continue? (Y/N):
N

Have a nice day!

Final Thoughts

I really enjoyed working on this project, especially because my knowledge of recursion greatly increased during it. By far, the hardest method of the program was the pal() method, since I needed to account for several different occurrence, while considering possible discrepancies caused by variation of string length (odds and evens). In the end, I had a great experience, and quite a bit of fun testing the output once the code was written! I've walked away from this project a better programmer.