CS21 Lab 10: Recursion

  • Due Saturday, April 25, before midnight

Goals

  • Use recursion to solve problems

1. Fun with strings

Open the file named stringRecursion.py. It provides three stubbed out functions, listed below with examples, and a main program to test them.

  • The function insert(string, add_char) creates a new string by inserting the given add_char in between each character of the original string.

    • insert("cash", "$") returns "c$a$s$h"

    • insert("hi", !") returns "h!i"

  • The function remove(string, del_char) creates a new string based on the original string where the del_char has been removed.

    • remove("mississippi", "i") returns "msssspp"

    • remove("swarthmore", "x") returns "swarthmore"

  • The function repeat(string, n) creates a new string where the original string is repeated n times.

    • repeat("yo", 2) returns "yoyo"

    • repeat("ohmy!", 3) returns "ohmy!ohmy!ohmy!"

1.1. Requirements

  • Write recursive solutions for each of these functions.

2. Recognizing palindromes

A palindrome is a word or phrase that reads the same forwards or backwards. Some examples of words that are palindromes include: "madam", "dad", and "wow". And here are some famous palindromatic phrases:

"A man, a plan, a canal, Panama!"
"Able was I ere I saw Elba."
"Never odd or even."

Notice that when recognizing strings that are palindromes we ignore non-alphabetic characters (such as numbers, punctuation and spaces) and we also ignore any distinction between upper and lower case letters.

Open the file palindrome.py, and write a recursive function called isPalindrome(text) that returns True when the given text is a palindrome and otherwise returns False.

Here are some examples of the isPalindrome(text) function:

  • isPalindrome("Race…​.Car") returns True

  • isPalindrome("Wooow!!!!!") returns True

  • isPalindrome("mama") returns False

Here is a sample run of entire program:

% python3 palindrome.py
This program tests words and phrases for palindromes
Enter some text (or 'quit'): cs21
This is NOT a palindrome.
Enter some text (or 'quit'): hello
This is NOT a palindrome.
Enter some text (or 'quit'): race car
This is a palindrome!
Enter some text (or 'quit'): Never odd or even!
This is a palindrome!
Enter some text (or 'quit'): a,b;B?A!
This is a palindrome!
Enter some text (or 'quit'): bye
This is NOT a palindrome.
Enter some text (or 'quit'): I
This is a palindrome!
Enter some text (or 'quit'): 12345
This is a palindrome!
Enter some text (or 'quit'): quit
Goodbye

You might be wondering why the string "12345" is classified as a palindrome. This is because once we eliminate all of the non-alphabetic characters we are left with an empty string, which is a palindrome.

2.1. Requirements

  • Your program should include a main function that continues prompting the user for some text until they enter "quit".

  • Your isPalindrome function must be defined recursively.

    • Start by thinking about your base case. What text could you immediately answer True for?

    • Then think about your recursive cases. How will you make some progress at solving the problem, and create a smaller version of the problem to recurse on?

  • Your function should ignore punctuation, spaces, and letter case.

    • You can use the isalpha() function to determine if a character is alphabetic. For example, if text="cs21", then text[0].isalpha() would return True and text[3].isalpha() would return False.

    • You can use the lower() function to convert strings or characters into lower case.

3. Extra Challenge: Finding palindromes in the dictionary

This problem is optional and should only be attempted when all of the required problems have been successfully completed.

The file named "/usr/share/dict/words" contains a list of legal English words. The words are stored one per line in alphabetic order. Many of these words are proper nouns and therefore begin with an upper case letter.

In the file dict_palindrome.py, write a program that opens this dictionary file and finds all of the words that are palindromes. You should ignore words that are of length 1 and those begin with an upper case letter.

Your program should produce output similar to what is shown below. We have omitted most of the palindromatic words so that you can find them yourself. We have also omitted the longest palindromatic word.

% python3 dict_palindrome.py
Found 61 palindromatic words in dictionary
['aha', ..., 'wow']
The longest palindromatic word is ? with length ?

3.1. Requirements

  • Copy and paste your isPalindrome function from the previous problem. Re-use this function in solving this problem.

  • When finding palindromes in the dictionary, ignore words that are of length 1 and any word that begins with an upper case letter. You can use the isupper() function to test for this. For example, if text="Hi", then text[0].isupper() will return True and text[1].isupper() will return False.

4. Answer the Questionnaire

Please edit the Questions-10.txt file in your cs21/labs/10 directory and answer the questions in that file.

Once you’re done with that, run handin21 again.

Turning in your labs…​.

Remember to run handin21 to turn in your lab files! You may run handin21 as many times as you want. Each time it will turn in any new work. We recommend running handin21 after you complete each program or after you complete significant work on any one program.