If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content

Using recursion to determine whether a word is a palindrome

A palindrome is a word that is spelled the same forward and backward. For example, rotor is a palindrome, but motor is not.
How can you use recursion to determine whether a word is a palindrome? Let's start by understanding what's a base case. Consider the word a. It's a palindrome. In fact, we don't have to think of palindromes as actual words in the English language (or whatever language you'd like to consider). We can think of a palindrome as just any sequence of letters that reads the same forward and backward, such as xyzyzyx. We call a sequence of letters a string. So we can say that any string containing just one letter is by default a palindrome. Now, a string can contain no letters; we call a string of zero letters an empty string. An empty string is also a palindrome, since it "reads" the same forward and backward. So now let's say that any string containing at most one letter is a palindrome. That's our base case: a string with exactly zero letters or one letter is a palindrome.
What if the string contains two or more letters? Here's where we'll have our recursive case. Consider the palindrome rotor. Its first and last letters are the same, and this trait must hold for any palindrome. On the other hand, if the first and last letters are not the same, as in motor, then the string cannot possibly be a palindrome. So now we have a way to declare that a string is not a palindrome: when its first and last letters are different. We can think of this situation as another base case, since we have the answer immediately. Going back to when the first and last letters are the same, what does that tell us? The string might be a palindrome. Then again, it might not be. In the string rater, the first and last letters are the same, but the string is not a palindrome. Suppose we strip off the first and last letters, leaving the string ate. Then the first and last letters of this remaining string are not the same, and so we know that rater is not a palindrome.
So here's how we can recursively determine whether a string is a palindrome. If the first and last letters differ, then declare that the string is not a palindrome. Otherwise, strip off the first and last letters, and determine whether the string that remains—the subproblem—is a palindrome. Declare the answer for the shorter string to be the answer for the original string. Once you get down to a string with no letters or just one letter, declare it to be a palindrome. Here's a visualization of that for two words that we discussed:
How would we describe that in pseudocode?
  • If the string is made of no letters or just one letter, then it is a palindrome.
  • Otherwise, compare the first and last letters of the string.
  • If the first and last letters differ, then the string is not a palindrome.
  • Otherwise, the first and last letters are the same. Strip them from the string, and determine whether the string that remains is a palindrome. Take the answer for this smaller string and use it as the answer for the original string.

This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.

Want to join the conversation?

  • leafers seed style avatar for user Ivykww
    Can someone explain how to calculate the time complexity of the "Challenge: is a string a palindrome?". I'm thinking it would be Theta(n) but can someone please verify?
    (8 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Assuming worst case scenario (the string is a palindrome)

      Cost of checking string:
      - cost of: final check for 0 or 1 length string: c1 ( a constant)
      - for every 2 additional letters:
      cost of: check for length + checking first and last character match: c2

      So the cost is: c1+ n/2*c2 or Theta(n)
      (8 votes)
  • leaf blue style avatar for user Krueger, Anna
    Can someone explain pseudocode further?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • blobby green style avatar for user Martin
      Hello Anna. The pseudocode is very detailed, there is probably no way to explain it further. Try to look at my implementation in Java and compare it with the pseudocode. If you still won't understand anything, feel free to ask. :)

      private boolean isPalindrom(String str) {
      if (str.length() == 0 || str.length() == 1){
      return true;
      } else {
      if (str.charAt(0) != str.charAt(str.length() - 1)){
      return false;
      } else {
      return isPalindrom(str.substring(1, str.length()-1));
      }
      }
      }
      (7 votes)
  • leaf green style avatar for user Hugo Zaanen
    How can no words or no letters be a palindrome?
    (3 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user asfand.asfand
    Can you please tell me in which language the challenge is written?
    (1 vote)
    Default Khan Academy avatar avatar for user
  • leafers seed style avatar for user Nicholas Cloyde
    I'm feeling lost on Step 1 of the challenge. Can someone help me on base case 1?
    // base case #1
    if (0 <= 1){ return true;}
    (2 votes)
    Default Khan Academy avatar avatar for user
  • leafers seed style avatar for user Nathanael Sovitzky
    // base case #2
    if(firstCharacter===lastCharacter) {

    str.slice(firstCharacter, lastCharacter);
    }

    If the first and last characters are the same, slice them out. What am I missing?
    (1 vote)
    Default Khan Academy avatar avatar for user
  • aqualine ultimate style avatar for user Tausif Iqbal
    How do i find the strings length?
    (1 vote)
    Default Khan Academy avatar avatar for user
  • female robot grace style avatar for user ayush saini
    i'm facing problem in recursive case.Can anyone tell me , after striking off the first and the last character by calling the middleCharacters function, how should i proceed with the resulting string. Means, how should i proceed with "oto"...
    (0 votes)
    Default Khan Academy avatar avatar for user
  • blobby blue style avatar for user iTzSc0rqion
    I'm stuck on step 3. What should I do? Here is my code:

    // Returns the first character of the string str
    var firstCharacter = function(str) {
    return str.slice(0, 1);
    };

    // Returns the last character of a string str
    var lastCharacter = function(str) {
    return str.slice(-1);
    };

    // Returns the string that results from removing the first
    // and last characters from str
    var middleCharacters = function(str) {
    return str.slice(1, -1);
    };

    var isPalindrome = function(str) {
    // base case #1
    if (str.length <= 1) {
    return true;
    }
    // base case #2
    if (firstCharacter(str) !== lastCharacter(str)) {
    return false;
    }
    // recursive case
    return true;
    };

    var checkPalindrome = function(str) {
    println("Is this word a palindrome? " + str);
    println(isPalindrome(str));
    };

    checkPalindrome("a");
    Program.assertEqual(isPalindrome("a"), true);
    checkPalindrome("motor");
    Program.assertEqual(isPalindrome("motor"), false);
    checkPalindrome("rotor");
    //Program.assertEqual(isPalindrome("rotor"), true);
    (1 vote)
    Default Khan Academy avatar avatar for user
  • starky seed style avatar for user Lara Ayoubi
    how can this be used in maths, (palindromic numbers) and how can they be used in our daily lives
    (1 vote)
    Default Khan Academy avatar avatar for user