## 1. Introduction

In this tutorial, we’ll learn how to check if a string is a palindrome.

## 2. What’s a Palindrome?

**A palindrome is a string symmetric around the middle.** For example:

The first and last characters are the same, just as the second and the second-to-last, the third and the third-to-last, etc.

That yields a recursive definition. A string is a palindrome () if and is also a palindrome. The base cases are an empty string and a string of length one: we consider them palindromes. So, the recursive definition is:

### 2.1. Odd and Even Lengths

Does it cover the cases with even and odd string lengths? If is even, and is a palindrome, the recursive steps meet right between the middle elements and . Those constitute the last pair to check. Afterward, the next to handle is the empty string, whose length is 0 and is by definition a palindrome:

Similarly, if is odd, the last pair are and , the immediate predecessor and successor to the middle element . A string of length 1 is a palindrome, so the definition covers this case too:

## 3. 3. Recursive Algorithm to Check if a String Is a Palindrome

We’ll base the recursive algorithm on our definition:

First, we check for the base case. Then, if the current endpoints are the same, we continue checking the rest of the string. Otherwise, we return since we found a pair of characters that isn’t in line with the definition.

### 3.1. Complexity

**In the worst case, the string is a palindrome, so all the pairs have to be checked. Since there are pairs, the time complexity is .**

However, **if is very large, there’s a possibility to get a stack overflow error.** It happens when the recursion is so deep that it exhausts the entire call stack. We can address this issue by converting our recursive algorithm into an iterative one.

## 4. Iterative Algorithm

If we rewrite the recursive algorithm’s innermost if-statement as , we’ll get a tail recursion. We can convert it into an iterative algorithm:

In the iterative algorithm, we run the while-loop until hitting the base case or finding a pair that breaks the palindrome property. In each iteration, we check if the current endpoints ( and ) are the same. If so, we move one character to the right and one character to the left, applying the same check to the new endpoints. Otherwise, if , we exit the loop and return .

**The iterative algorithm works the same as the recursive one but isn’t prone to stack overflow.**

## 5. Conclusion

In this article, we presented recursive and iterative algorithms for checking if a string is a palindrome. The former follows the recursive definition of a palindrome but may cause a stack overflow if the input string is too long.