I'm about 3 weeks into one of my computer science courses using Python and the discussion turned to recursive programming. It sounds a bit mysterious and complicated, but it turns out writing recursive functions in Python is pretty easy. The instructor separated the process of writing recursive functions into a couple of steps. I talk about these steps while I write a recursive Python function to detect Palindromes.

Palindromes

From Wikipedia, a palindrome is a word, phrase, number, or other sequence of characters which reads the same backward or forward. I was amazed to find an entire site dedicated to a list of palindromes, which I used for my testing. Usually one ignores the spaces and punctuations in the phrases. Only the letters and numbers are significant and used to test for a valid palindrome.

Test Palindromes
  • Yo, banana boy!
  • Dee saw a seed.
  • No, it is open on one position.

My assignment is to write a recursive function to detect if a word or phrase is a palindrome.

The Algorithm

Once I strip out the spaces and punctuation from the phrases as well as make all the characters lowercase, "Yo, banana boy!", for example, is reduced to "yobananaboy".

At that point I just need to compare the first and last characters to see if they are the same. If they are, this could be a palindrome. If not, it is definitely not a palindrome. In this case, the first character is "y" and the last character is "y", so this could be a palindrome.

The next step would be to remove the first and last characters. The phrase would now be "obananabo". I would then compare the first and last characters in this new string. If they are the same this could be a palindrome. In this case, the first character is "o" and the last character is "o", so this could be a palindrome.

I continue this process over and over until there is 1 or less characters left in the phrase. A string of 1 or less characters is considered a palindrome, since it is the same both forward and backward.

Recursive Function

Now that I know the algorthm, I can write a recursive function to detect palindromes.

First, I need a base case. I need a case where the function stops making recursive calls. Based on the algorithm, this is when I have 1 or less characters. In these cases it is a palindrome, and I can return True.

if (len(phrase)) < 2:
    return True

Next, I need to simplify the problem into a simpler mathematical or logical expression and a call to the function that solves a smaller piece of the problem.

Looking at the algorithm, the simpler logical expression can be a comparison of the first and last characters of the phrase.

phrase[0] == phrase[-1]

I can then make a call to the function (I'll call the function is_palindrome) to solve a smaller portion of the string that does not include the current first and last characters.

is_palindrome(phrase[1:len(phrase) - 1])

When I put this together, the function I made looks like this.

def is_palindrome(phrase):
    # base case
    if len(phrase) < 2:
        return True

    # divide into easier calculation
    # and recursive call
    return phrase[0] == phrase[-1] and \
        is_palindrome(phrase[1:len(phrase) - 1])

The Program

I'm not finished. Turns out that is the easy part. I now need to create a program that requests a phrase from the user and strips out all the non-alphanumeric characters before calling the function. Although there are numerous ways to strip non-alphanumeric characters (the fastest probably being a regular expression), I choose a List Comprehension since it is a pretty cool feature in Python.

import string


def is_palindrome(phrase):
    # base case
    if len(phrase) < 2:
        return True

    # divide into easier calculation
    # and recursive operation
    return phrase[0] == phrase[-1] and \
        is_palindrome(phrase[1:len(phrase) - 1])


while True:
    data = raw_input('Enter text (q to quit): ')

    text = data.lower()

    if text == 'q':
        break

    # strip all non alphanumeric characters
    # using Python list comprehension
    text = ''.join([letter for letter in text
                    if letter in (string.ascii_lowercase + string.digits)])

    text_is_a_palindrome = is_palindrome(text)

    if text_is_a_palindrome:
        print "'{}' is a palindrome.".format(data)
    else:
        print "'{}' is not a palindrome.".format(data)

Conclusion

I've written a few recursive functions in Python for problem sets and exercises. I'll share those as it helps me to talk about them and may help others to see more examples of recursive functions to help clarify the process. After a few weeks of Python I am really starting to appreciate the language and enjoy it. At some point I'll share the syntactical mistakes I make coming from C# .NET. I am making the mistakes less and less, but they still pop up here and there. Hope this helps!

Posted by Koder Dojo

Hi, and welcome to Koder Dojo. I am learning Python out in the open as I participate in several free online computer science and programming courses using Python. I have been a professional web developer for many, many years using Microsoft Technology. I am currently programming in C#, .NET, ASP.NET MVC, Orchard CMS, JavaScript, and React.js. After starting and stopping to learn Python for many years, I decided this is the year to make it stick. It is helpful for me to write about what I learn! I hope my articles are interesting and entertaining to others.

Related Posts: