Palindrom String

Write a recursive function is_palindrome(s) that returns True if the string reads the same forward and backward, and False otherwise. Input: "racecar" → True. Input: "hello" → False. You must use recursion.

Check if $s[\text{left}] = s[\text{right}]$, then recursively check the inner substring $s[\text{left}+1\ldots\text{right}-1]$. The base case is when the pointers cross ($\text{left} \geq \text{right}$) — a single character or empty string is always a palindrome.

1. Pass left and right pointer indices along with the string.
2. Base case: if left >= right, return True.
3. If s[left] != s[right], return False immediately.
4. Otherwise, recurse with left + 1 and right - 1.

• Not passing the left and right pointers, trying to slice the string instead
• Using left > right as the base case instead of left >= right (misses the single-character case)
• Forgetting to handle case sensitivity if required
• Creating new string slices at each level, adding $O(N)$ per call

This shows how the same algorithm (two-pointer palindrome check) can be expressed iteratively ($O(1)$ space) or recursively ($O(N)$ space). The recursive "check boundaries, recurse inward" pattern also appears in binary search and divide-and-conquer.