Learn
Recursion vs. Iteration - Coding Throwdown
Taco Cat

Palindromes are words which read the same forward and backward. Here’s an iterative function that checks whether a given string is a palindrome:

def is_palindrome(my_string): while len(my_string) > 1: if my_string[0] != my_string[-1]: return False my_string = my_string[1:-1] return True palindrome("abba") # True palindrome("abcba") # True palindrome("") # True palindrome("abcd") # False

Take a moment to think about the runtime of this solution.

In each iteration of the loop that doesn’t return False, we make a copy of the string with two fewer characters.

Copying a list of N elements requires N amount of work in big O.

This implementation is a quadratic solution: we’re looping based on N and making a linear operation for each loop!

Here’s a more efficient version:

# Linear - O(N) def is_palindrome(my_string): string_length = len(my_string) middle_index = string_length // 2 for index in range(0, middle_index): opposite_character_index = string_length - index - 1 if my_string[index] != my_string[opposite_character_index]: return False return True

Note these solutions do not account for spaces or capitalization in the input!

Instructions

1.

Implement your version of is_palindrome() which has the same functionality using recursive calls!

Folder Icon

Sign up to start coding

Already have an account?