DSA Recursion on Strings

Recursion on strings solves a word problem by shrinking the word from both ends. A palindrome is a word that reads the same forwards and backwards.

Checking a palindrome

The outer letters must match before the middle is checked at all. A word of zero or one letter is the base case here.

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

print(is_palindrome("level"))
print(is_palindrome("lemon"))

Reversing a word

Reversal moves the head letter behind the reversed rest of the word. The rest is one letter shorter on every call.

def reverse(word):
    if len(word) <= 1:
        return word
    return reverse(word[1:]) + word[0]

print(reverse("cat"))
print(reverse("stop"))

Watching the word shrink

Each call removes the first and last letters together. The printed words shrink by two letters at a time.

def shrink(word):
    print(word)
    if len(word) > 2:
        shrink(word[1:-1])

shrink("racecar")

Example

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

def reverse(word):
    if len(word) <= 1:
        return word
    return reverse(word[1:]) + word[0]

words = ["level", "noon", "python", "racecar", "hello"]
for word in words:
    print(word, "palindrome:", is_palindrome(word), "reversed:", reverse(word))

Key points

String recursion shrinks the word until a base case remains.
A palindrome check can stop at the first pair of outer letters that differ.
Reversal by recursion places the head letter after the reversed rest.
The middle letter of an odd word never needs a partner.

In this example, five words go through both recursive tools. The palindrome tool compares the outer letters and then checks the smaller middle. It accepts level, noon and racecar, and rejects python and hello. The reversal tool places each head letter behind the reversed rest, so every printed reversal reads backwards.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

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

def reverse(word):
    if len(word) <= 1:
        return word
    return reverse(word[1:]) + word[0]

words = ["level", "noon", "python", "racecar", "hello"]
for word in words:
    print(word, "palindrome:", is_palindrome(word), "reversed:", reverse(word))

Exercise

What does the recursive reverse tool from this lesson return for the word dog?

dog god dgo ogd