Python Algorithms - Revisiting Recursive Functions and Palindromes

Earlier I mentioned how my computer science and programming class using Python had a problem set asking me to develop a recursive function to detect Palindromes. Here is the function I mentioned in the previous post.

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])

Since the assignment required me to create a recursive function I didn't think about other solutions at the time. I do remember feeling really good about this solution, however, and how much I liked recursive functions. Everything looked like a potential recursive function :)

Interestingly enough, however, my algorithms course started a week ago, and the first week demonstrated the naive recursive function used to generate the Fibonacci sequence. This was rather eye-opening, and the new knowledge helped me get a more balanced perspective on recursive functions. It also has me looking at the recursive functions I have written in the past to see if there is a better algorithm.

Revisiting Palindromes

As I thought about the definition of a palindrome, a phrase that is the same forward and backward, I realized that and easy test for a palindrome is to reverse the letters in the phrase and compare it to the original phrase. If the two strings are the same, it is a palindrome. If the two strings are different, it isn't a palindrome. Therefore, the recursive function can be replaced with another algorithm.

def is_palindrome(phrase):
    phrase_reversed = phrase[::-1]
    return phrase == phrase_reversed

The expression, phrase[::-1], is slicing notation in Python and returns phrase with its letters reversed. I then compare the original phrase with its reversed form. If they are equal it is a palindrome and the function returns True, otherwise it is not a palindrome and the function returns False.

I like this version much better! Seems more intuitive and less complicated than its recursive counterpart. I probably would use this version if the original problem did not require me to write a recursive function.

Conclusion

In just 1 week my algorithms course has me re-thinking algorithms. It's complementing my computer science and programming course using Python really well.

Related Posts: