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 == 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.
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.
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.
Posted by Koder Dojo
I am learning Python and attending four online courses: 1) computer science and programming using Python, 2) algorithms, 3) data structures, and 4) cryptography. This is in addition to my day job as a C# ASP.NET MVC Web Developer. Python and the online courses are challenging, eye-opening, and a lot of fun. I am writing about my experience to help me sort it all out. I hope you find it useful!