Reversing the string “Hello” produces the string “olleH”. The problem was discussed in Loops – Python » Example 5: Palindromes. A word is a palindrome when it is identical to its reversal (e.g., racecar). In the loop post, a for-loop is used to generate the reversed word.
Can we write a recursive program reversing a string? Yes. We describe three recursive approaches.
Let’s say word is the string we want to reverse.
- Base cases
- Base case provides the exit condition of the program.
- If we have a string of length 0, we return the empty string. This is more a check for correct input than a base case for the recursion.
- String word has length 1 (i.e., it consist of a character). There is nothing to reverse. Return the string as is.
- One of the programs includes a string of length 2 as one of the base cases. In this case, we need to reverse the two characters.
- Here is how the three recursive functions operate
- Recursive version 01. Remove the first character in string word and recursively reverse the remaining string. Then, append the removed first character to the end of the returned string. See function reverseWordRecur01 where recursion happens in the statement return reverseWordRecur(word[1:]) + word)
- Recursive version 02. Split the string into two parts, a first half and a second half. In function reverseWordRecur02 the variables firstPart and secondPart represent these two strings. Swap the first and last character of string word and reverse the work in between.Then invoke return reverseWordRecur02(secondPart)+reverseWordRecur02(firstPart).
- Recursive version 03. Swap the first and last character of string word and reverse the work in between.See function reverseWordRecur03 where recursion happens in the statement return word[len(word)-1] + reverseWordRecur03(word[1:len(word)-1]) + word).
##reversingString.py #Reversing a string #non-recursive version def reverseWord(word): revWord = "" #start reversed word as blank x = len(word) - 1 #find the length of the input word for i in range(x,-1,-1): #start at end of word & move backwards letter = word[i] #get the letter revWord = revWord + letter #add it to end of revWord return revWord ##recursive version 01 def reverseWordRecur01(word): #check if the word is empty to avoid run time error if word == "": return "" #if the word is empty, return an empty string if len(word) == 1: #base case: when there is only one letter in the word return word #return that letter else: return reverseWordRecur01(word[1:]) + word ##recursive version 02 def reverseWordRecur02(word): #check if the word is empty to avoid run time error if word == "": return "" #if the word is empty, return an empty string if len(word) == 1: #base case 1: when there is only one letter in the word return word #return that letter elif len(word) == 2: #base case 2: when there are two letters in the word return word + word #reverse the 2 letters else: length = len(word) mid = length / 2 firstPart = word[0:mid] #get the first half of the word secondPart = word[mid:] #get the second half of the word return reverseWordRecur02(secondPart) + reverseWordRecur02(firstPart) #reverse the first part and the second part ##recursive version 03 def reverseWordRecur03(word): if word == "" or len(word)== 1: return word #if the word is empty, return an empty string else: return word[len(word)-1] + reverseWordRecur03(word[1:len(word)-1]) + word word = raw_input("Enter a word: ") print "The original word was",word print "Result of non-recursive version:",reverseWord(word) print "Result of recursive version 01 :",reverseWordRecur01(word) print "Result of recursive version 02 :",reverseWordRecur02(word) print "Result of recursive version 03 :",reverseWordRecur03(word)
Let students trace the recursive calls on example words for all three functions. Then, let students discuss the three different approaches and explain them in their own words.