AlgoMaster Logo

Palindrome Check (Recursive)

Last Updated: June 7, 2026

easy
3 min read

Understanding the Problem

A palindrome reads the same in both directions, so "racecar" and "abba" qualify, while "hello" does not. Stated in terms of the two ends: the first and last characters must match, and the same must then hold for the string between them.

That phrasing is recursive. To check "racecar", compare the outer 'r' and 'r', and if they match, check the inside part "aceca". Stripping its ends leaves "cec", and so on. Rather than building smaller strings, track two indices, one from the left and one from the right, and compare the characters they point to.

Key Constraints:

  • The empty string and single characters are palindromes. The base case must return true when the two indices meet or cross.
  • A single mismatched pair settles the answer immediately as false, so there is no need to keep checking once one pair fails.
  • Each step moves the indices one position inward, so they are guaranteed to meet, which terminates the recursion.

Approach 1: Recursion

Intuition

Use two indices, left at the first character and right at the last. If the characters differ, return false. If they match, the problem reduces to the same question on left + 1 and right - 1. A helper that takes the string and the two indices calls itself with the indices moved inward.

The recursion succeeds in two ways. If left and right cross, every pair matched, which covers even-length strings and the empty string. If left equals right, the indices landed on the single middle character, which has nothing to compare against. Either condition is the base case returning true. Each call moves the indices closer, so one is always reached unless a mismatch returns false first.

Algorithm

  1. Start with left at index 0 and right at the last index.
  2. If left is greater than or equal to right, return true. All pairs matched.
  3. If the characters at left and right differ, return false.
  4. Otherwise, recurse with left + 1 and right - 1.

Example Walkthrough

Input:

0
r
1
a
2
c
3
e
4
c
5
a
6
r
s

The indices start at left = 0 and right = 6. The characters are 'r' and 'r', which match, so the call recurses with left = 1, right = 5. Those are 'a' and 'a', a match, so it recurses with left = 2, right = 4, which are 'c' and 'c', another match. Now it recurses with left = 3, right = 3. The indices are equal, so the base case returns true. That true passes straight back up through every call, since none of them found a mismatch. The string "racecar" is a palindrome.

true
result

Code

Approach 2: Iterative Two Pointers

Intuition

The same inward comparison fits naturally into a loop. Keep two pointers, one at each end, and compare the characters they point to. If any pair differs, return false at once. If they match, step both pointers inward and continue. When the pointers meet or cross, every pair matched and the string is a palindrome. This keeps the work in one stack frame instead of one per pair.

Algorithm

  1. Set left to the first index and right to the last index.
  2. While left is less than right, compare the characters. If they differ, return false. Otherwise increment left and decrement right.
  3. If the loop finishes without a mismatch, return true.

Example Walkthrough

Input:

0
r
1
a
2
c
3
e
4
c
5
a
6
r
s

The pointers start at left = 0 and right = 6, where the characters 'r' and 'r' match, so both move inward. At left = 1, right = 5, the characters 'a' and 'a' match. At left = 2, right = 4, the characters 'c' and 'c' match. The pointers move to left = 3, right = 3, where left is no longer less than right, so the loop stops. No mismatch was found, so the answer is true, the same verdict the recursion reached.

true
result

Code