Learning Recursion in JavaScript Part 4 - Palindromes

April 11, 2019

Ah, recursion, one of those intimidating programming topics that make many developers’ heads spin 🤯 . These types of problems can be difficult to conceptualize, especially when you’re under pressure during an interview. I know I’ve felt that before! Well, that’s why I am writing this blog post series on recursion, to help you and me learn it better. As I’ve spent more time learning about it, I’ve come to find it a fascinating topic and appreciate how elegantly you can use it to solve certain types of problems.

Here are the other posts in this series if you haven’t checked those out yet:

  1. The Obligatory Factorial Function
  2. Sum an Array of Numbers 3 Ways
  3. Flattening Arrays
  4. Palindromes

For this fourth post in this series on recursion, we’re going to look at palindromes. If you’re not familiar with a palindrome, it is a word, phrase, or sequence that reads the same backward as forward. For example, “madam”, “noon”, “eve”, and “level” are palindromes.

In this post, we’re going to write a function that checks if a string is a palindrome.

Manually Checking if a Word is a Palindrome

Before we write any code, how would we check if a string is a palindrome manually? A simple way would be to check the first and last characters of the string and see if they are the same. If they are, we move in a letter on both sides and check if those letters are the same. We can keep doing that until we’ve gone through all of the letters or there is one letter left. If at any point the letters that we are comparing don’t match, we know that the word is not a palindrome.

Let’s take the word “noon” for example. Is the first letter “n” the same as the last letter “n”? Yes, so we’ll move in a letter. Is the second letter “o” the same as the third letter “o”? Yes. There are no more letters to check. The word “noon” is a palindrome.

Let’s look at the word “level” now. What’s different with this word is that there are an odd number of letters. Is the first letter “l” the same as the last letter “l”? Yes, so we’ll move in a letter. Is the second letter “e” the same as the fourth letter “e”? Yes, so we’ll move in a letter. “v” is the only letter remaining as it is the middle letter. The word “level” is a palindrome.

Our Base Case

Looking at our two examples, we can identify our base. Our base case is when we’ve gone through all of the letters for an even numbered word length or there is one letter left for an odd numbered word length. In code, that would look like the following:

function isPalindrome(string) {
  if (string.length <= 1) {
    return true;
  }

  // ...
}

The Recursive Case

Now that we have our base case, let’s start implementing the steps we went through above where we compare letters on the left and right, moving from the outside towards the inside.

function isPalindrome(string) {
  if (string.length <= 1) {
    return true;
  }

  let [ firstLetter ] = string;
  let lastLetter = string[string.length - 1];

  if (firstLetter === lastLetter) {
    let stringWithoutFirstAndLastLetters = string.substring(1, string.length - 1);
    return isPalindrome(stringWithoutFirstAndLastLetters);
  } else {
    return false;
  }
}

And that’s all there is to it. Let’s step through some examples.

Example 1: isPalindrome('noon') // true

Invocation firstLetter lastLetter Recursive call
isPalindrome('noon') n n isPalindrome('oo')
isPalindrome('oo') o o isPalindrome('')
isPalindrome('')     Base case met. true is returned.

With the word “noon”, the recursion will stop during the third invocation of isPalindrome since the string is empty, and true will be returned.

Example 2: isPalindrome('eve') // true

Invocation firstLetter lastLetter Recursive call
isPalindrome('eve') e e isPalindrome('v')
isPalindrome('v')     Base case met. true is returned.

Example 3: isPalindrome('no0n') // false

Invocation firstLetter lastLetter Recursive call
isPalindrome('no0n') n n isPalindrome('o0')
isPalindrome('o0') o 0 false is returned.

Conclusion

Stay tuned for the next post in my series on recursion, as we’ll continue to look at more examples and facets of recursion.

Disclaimer: Any viewpoints and opinions expressed in this article are those of David Tang and do not reflect those of my employer or any of my colleagues.