PD4CS

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
  1. 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[0])
  2. 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).
  3. 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[0]).

##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[0] #return that letter
    else:
        return reverseWordRecur01(word[1:]) + word[0]   

##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[0] #return that letter
    elif len(word) == 2: #base case 2: when there are two letters in the word
        return word[1] + word[0] #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[0]

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.