Python Program to Check Palindrome Using Recursion

You can check a palindrome using recursion in Python by defining a function that compares the first and last characters with if s[0] != s[-1]: return False and recursively calling itself on the substring s[1:-1] until the string length is 0 or 1, returning True.

Examples

Input"madam"

OutputTrue

Input"hello"

OutputFalse

Input"a"

OutputTrue

How to Think About It

To check if a string is a palindrome using recursion, think of comparing the first and last characters. If they are the same, then check the smaller string inside by removing these two characters. Repeat this until the string is empty or has one character, which means it is a palindrome.

Algorithm

1

Get the input string.

2

If the string length is 0 or 1, return True (base case).

3

Compare the first and last characters of the string.

4

If they are not equal, return False.

5

If they are equal, call the function recursively on the substring excluding the first and last characters.

6

Return the result of the recursive call.

Code

python

def is_palindrome(s):
    if len(s) <= 1:
        return True
    if s[0] != s[-1]:
        return False
    return is_palindrome(s[1:-1])

print(is_palindrome("madam"))
print(is_palindrome("hello"))
print(is_palindrome("a"))

Output

True
False
True

Dry Run

Let's trace the string "madam" through the code

1

Check base case

String is "madam", length > 1, continue

2

Compare first and last characters

First = 'm', Last = 'm', they match

3

Recursive call on substring

Call is_palindrome("ada")

4

Repeat steps for "ada"

First = 'a', Last = 'a', match, call is_palindrome("d")

5

Base case reached

String "d" length is 1, return True

6

Return True up the call stack

All checks passed, final result is True

Call	String	First Char	Last Char	Result
1	madam	m	m	Recurse
2	ada	a	a	Recurse
3	d	d	d	True

Why This Works

Step 1: Base Case

If the string length is 0 or 1, it is a palindrome by definition, so return True.

Step 2: Character Comparison

Compare the first and last characters; if they differ, the string is not a palindrome, so return False.

Step 3: Recursive Step

If the first and last characters match, call the function again on the substring without these characters to check the rest.

Alternative Approaches

Iterative approach

python

def is_palindrome_iterative(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

print(is_palindrome_iterative("madam"))

This uses a loop instead of recursion and is often more efficient with less memory use.

Using string reversal

python

def is_palindrome_reverse(s):
    return s == s[::-1]

print(is_palindrome_reverse("madam"))

This is the simplest method but does not use recursion.

Complexity: O(n) time, O(n) space

Time Complexity

The function compares pairs of characters moving inward, so it runs in linear time proportional to the string length.

Space Complexity

Each recursive call adds a new layer to the call stack, so space used is proportional to the string length.

Which Approach is Fastest?

The iterative approach is fastest and uses less memory, while recursion is elegant but uses more stack space.

Approach	Time	Space	Best For
Recursive	O(n)	O(n)	Learning recursion and elegant code
Iterative	O(n)	O(1)	Performance and memory efficiency
String reversal	O(n)	O(n)	Simplicity and quick checks