Write a recursive function that returns true if a string reads the same
forwards and backwards. Compare the outer characters and recurse inward. An empty
string and a single character are palindromes.
isPalindrome(s)
isPalindrome("racecar") // → true
isPalindrome("abba") // → true
isPalindrome("hello") // → false
isPalindrome("") // → true
A palindrome check is naturally about comparing the outside edges of a string and working inward — a strong hint that recursion (shrinking from both ends at once) fits well here, even though a two-pointer loop would also work. The recursive framing: a string is a palindrome if its first and last characters match, and everything between them is also a palindrome.
Two situations are short enough to answer immediately: an empty string, and a string with exactly one character. Both trivially read the same forwards and backwards, so both return true right away. Since each call strips two characters (one from each end), the recursion lands on either an empty string or a single character depending on whether the original length was even or odd — so you need both cases covered.
For a longer string, check the two outer characters first: if the first and last don't match, stop and return false immediately — no amount of checking the middle can fix a mismatch at the edges. If they do match, trust a recursive call on the substring with both ends stripped to determine whether the middle is a palindrome, and return whatever that call returns.
Checking "abba": first and last are both 'a' — match — recurse on "bb". First and last of "bb" are both 'b' — match — recurse on "" (both stripped away). "" hits the base case and returns true. That flows back up unchanged through "bb" and then "abba". Contrast with "abca": first and last are both 'a' — match — recurse on "bc". Here 'b' and 'c' don't match, so this call returns false directly, and that flows straight back up.
The recursive structure mirrors the actual definition of a palindrome — same outer characters, and a palindrome in between — so the code reads as a direct statement of that definition. It also short-circuits nicely: the moment any pair fails to match, the whole chain resolves to false without further comparisons. In the worst case (a true palindrome) you make about n/2 calls, but a mismatch near the outside is caught almost immediately. The cost, as with the other recursive string problems here, is O(n) stack depth and new substrings at each level — an iterative two-pointer scan would use O(1) extra space, but this builds the same base-case/recursive-case instincts you'll need for trees and nested structures where there's no simple loop equivalent.
def is_palindrome(s):
if len(s) <= 1:
return True
if s[0] != s[-1]:
return False
return is_palindrome(s[1:-1])
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.