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.
