Unraveling the Mystery of Palindromes

A palindrome is a sequence of characters that reads the same forwards and backwards, whether it’s a word, phrase, or number. In this tutorial, we’ll explore how to write a simple function called isPalindrome(chars) that determines if a given sequence of characters is a palindrome.

Normalizing the String

Before we dive into the algorithms, let’s assume the input sequence is a string. To make our lives easier, we’ll remove non-alphanumeric characters and convert the string to lowercase. This ensures that palindrome phrases with spaces, for example, can pass the check. In JavaScript, we can use the regular expression /[^a-z0-9]/i to strip off non-alphanumeric characters from the string.

const normalizeString = (str) => str.toLowerCase().replace(/[^a-z0-9]/i, '');

Popular Algorithms

There are several algorithms to check if a string is a palindrome. Here are two of the most popular ones:

Reversed String Comparison

The simplest approach is to compare the string with its reversed string. If they match, it’s a palindrome; otherwise, it’s not. We can achieve this using built-in JavaScript methods and utilities.

const isPalindrome = (str) => {
  const normalizedStr = normalizeString(str);
  return normalizedStr === normalizedStr.split('').reverse().join('');
};

Loop with Character Comparisons

Another popular algorithm is to loop through the characters of the string, comparing each character with the corresponding character from the end of the string.

const isPalindrome = (str) => {
  const normalizedStr = normalizeString(str);
  for (let i = 0; i < normalizedStr.length / 2; i++) {
    if (normalizedStr[i]!== normalizedStr[normalizedStr.length - i - 1]) {
      return false;
    }
  }
  return true;
};

Recursive Algorithm

As you may know, many algorithms that can be implemented using a loop can also be implemented using recursion. Let’s explore how to reimplement the isPalindrome() function using recursion.

Terminal Conditions

We can identify two terminal conditions that can cause the recursion to stop and return a result immediately:

• If the string contains just one character, it’s a palindrome.
• If the first and last characters don’t match, the string cannot be a palindrome.

Basic Implementation

Here’s how our recursive solution works:

const isPalindrome = (str) => {
  const normalizedStr = normalizeString(str);
  const length = normalizedStr.length;

  if (length === 1) {
    return true;
  }
  if (normalizedStr[0]!== normalizedStr[length - 1]) {
    return false;
  }
  return isPalindrome(normalizedStr.slice(1, length - 1));
};

Implementation Improvements

Our function works as expected, but we can make some optimizations to further improve it:

• When an empty string is passed, our function currently returns true instead of false.
• We’re normalizing the input string again in each function invocation, which can be expensive for longer strings.

We can use an immediately invoked function expression (IIFE) to return an isPalindrome() function that implements workarounds for these issues.

const isPalindrome = (() => {
  const normalizeString = (str) => str.toLowerCase().replace(/[^a-z0-9]/i, '');
  return (str) => {
    const normalizedStr = normalizeString(str);
    const length = normalizedStr.length;

    if (length === 0) {
      return false;
    }
    if (length === 1) {
      return true;
    }
    if (normalizedStr[0]!== normalizedStr[length - 1]) {
      return false;
    }
    return arguments.callee(normalizedStr.slice(1, length - 1));
  };
})();

Further Optimization

So far, our recursive solution works fine and is already optimized for tail call elimination. However, if we want an optimized version that will work across all browsers, we can wrap our function in a trampoline.

const trampoline = (fn) => {
  while (true) {
    const result = fn();
    if (!result instanceof Function) {
      return result;
    }
    fn = result;
  }
};

const isPalindrome = (() => {
  const normalizeString = (str) => str.toLowerCase().replace(/[^a-z0-9]/i, '');
  return (str) => trampoline(function recurse(str) {
    const normalizedStr = normalizeString(str);
    const length = normalizedStr.length;

    if (length === 0) {
      return false;
    }
    if (length === 1) {
      return true;
    }
    if (normalizedStr[0]!== normalizedStr[length - 1]) {
      return false;
    }
    return recurse(normalizedStr.slice(1, length - 1));
  });
})();

Practically speaking, it’s unlikely to run into stack overflow issues with isPalindrome() like you could with a typical recursive function. Nonetheless, the optimization techniques we highlighted here could be used to delay stack overflow for most recursive functions.