CS21 Lab8: Recursion

Due 11:59pm Tuesday, April 1 (No fooling!)

A skeleton version of the programs will appear when you run update21 in a terminal window. The program handin21 will only submit files in this directory.

You may work with a partner on this assignment. If you work with a partner, put your name and the name of your partner in the list of authors at the top of your program. Only one partner should run handin21 to submit the files for the group. Both partners will receive the same grade.


A palindrome is a sentence that contains the same sequence of letters reading it either forwards or backwards. A classic example is: "Able was I, ere I saw Elba." Another example is: "A man, a plan, a canal, Panama!"

In the file palindrome.py, write a recursive function called isPalindrome that returns True when a given string is a palindrome, and otherwise returns False. The basic idea is to check that the first and the last letters of the string are the same letter. If they are, then the entire string is potentially a palindrome, as long as everything between those letters is also a palindrome. There are a couple of special cases to check for. If either the first or last character of the string is not a letter, you can ignore that letter and check to see if the rest of the string is a palindrome. Also, when you compare letters, make sure that they are all the same case. The ideal solution will not require any additional helper functions other than the python string methods isalpha and lower.

Use your function in a main program that repeatedly prompts the user for a phrase and then reports whether or not it is a palindrome, as shown here:

This program will test if a series of phrases are palindromes.

Enter a phrase or 'quit' to end: wow
This is a palindrome!

Enter a phrase or 'quit' to end: mom
This is a palindrome!

Enter a phrase or 'quit' to end: wow mom
Sorry, this is not a palindrome.

Enter a phrase or 'quit' to end: wow, mom wow
This is a palindrome!

Enter a phrase or 'quit' to end: Able was I, ere I saw Elba.
This is a palindrome!

Enter a phrase or 'quit' to end: A man, a plan, a canal, panama.
This is a palindrome!

Enter a phrase or 'quit' to end: quit

Can you think of any other interesting palindromes? If so, add them as comments in your program.

Contrasting recursion and iteration

In the file recursion.py, complete each of the following functions. You will write two versions of each function, one that is an iterative solution and one that is a recursive solution.

You should not use any of the list class methods (such as append, insert, remove, etc). You should only need to use slicing and concatenation.

Once you are satisfied with your programs, hand them in by typing handin21 in a terminal window.