CS21 Lab 10: Recursion

This lab is due Monday, Dec 2, before midnight

Special Note: if you want to work on this lab from home (or just from your laptop), please see our atom remote edit page for instructions on how to set up atom.

Goals

to master using recursion!

1. times 2

1.1. write the `times2(..)` function

In a file called double.py, write a times2(L,index) function that, given a list (L) and an index, doubles all values in the list from the given index to the end of the list. Include a main() function in double.py that tests your times2(..) function and shows that it works.

For example, calling times2(L,0) should double all values in the list. If I have this in main():

def main():
  L = [1,2,3,4]
  print(L)
  times2(L,0)
  print(L)

I should get this output:

$ python3 double.py
[1, 2, 3, 4]
[2, 4, 6, 8]

1.2. add some `assert()` statements

If you haven’t learned what the assert() function does yet, see our python reference section on asserts for a quick review.

Here’s an example of testing specific values in the list:

   L = [5,10,15,20]
   times2(L,2)       # only double the items at index 2 and index 3
   assert(L[0]==5)   # should be the same as it was
   assert(L[3]==40)  # should be doubled

If the assert tests pass, you won’t see any output. If they fail, you will see an AssertionError, and know that there is a problem with your recursive function.

Add at least 3 additional assert(..) statements to your main() function to help test your times2(L,index) function (i.e., keep what you have in main(), just add 3 asserts to the beginning or end of main).

Here are a few ideas for asserts you can add:

you can make a copy of the list with COPY = L.copy(). Copy the list, then double the whole list L, then check that all values are twice what they were (i.e., test that L[i]==2*COPY[i])
or make a copy, then call times2(..) with an index greater than the length of the list (e.g., times2(L,100)), then check that no values have changed
check that times2(L,0) works for a list of strings (e.g., calling the function with L = list("ABC") would make the list ["AA","BB","CC"])
check that if L=[], then times2(L,0) doesn’t change the list
check that times2(L,0) works if there is only 1 item in the list

2. inside-out

2.1. write the `insideout(..)` function

In a file called inside-out.py, write a function that uses recursion to turn a string "inside-out". Your function should first pull out the middle character of the string, then the middle character from the remaining string, and so on and so forth, until there is only 1 or fewer characters left. The recursion also puts the pulled-out characters together, in the order they were pulled out. Here’s a quick example, assuming the initial string is "CAT":

pull out the middle letter: "A", so the remaining string is "CT"
given the string "CT", pull out the middle letter. Since there is no true middle letter, use the one on the right (the "T")
this leaves us with just the "C", so putting them all together gives "ATC"

Below are a few sample runs. Include a short main() function to ask the user for a string, and then send that string to your insideout(..) function. Your insideout(..) function should return the inside-out string back to main() for printing.

$ python3 inside-out.py
word: swarthmore!
hmtorraew!s

$ python3 inside-out.py
word: ABCDEF
DCEBFA

$ python3 inside-out.py
word: 12345
34251

In this last example, the initial middle character is the "3". After that is pulled out, the remaining string is "1245". Note the function as written chooses the "4", leaving the string "125". The middle character in that string is the "2", etc.

2.2. all 5-letter inside-out words

Are there any 5-letter words that, after being turned "inside-out", are still valid English words? For example, if the original word is "salon", after turing it inside-out, we get "loans" (again, assuming we take the character on the right if there is no middle character).

Modify your main() function above to read in all 5-letter words (not using recursion) from the "/usr/share/dict/words" file and print out all 5-letter words that, when turned inside-out, are still valid words:

$ python3 inside-out.py
euros rouse
fiche chief
hales leash
lucre cruel
...
...

3. palindromes

Write a program called pals.py that asks the user for a phrase and determines whether it is a palindrome or not, ignoring punctuation, spaces, and case. Here are some sample runs of the program:

$ python3 pals.py
phrase: A nut for a jar of tuna
is a palindrome!

$ python3 pals.py
phrase: Was it a car or a cat I saw?
is a palindrome!

$ python3 pals.py
phrase: KevinLovesCamelCase?
Nope...

$ python3 pals.py
phrase: 1 2 3 4 3 2 1
is a palindrome!

To do this one, it is easier if you remove all of the non-alphanumeric characters first, then decide if the remaining string of letters and digits is a palindrome or not. Please write the following two recursive functions, then write main() to use the two functions.

3.1. recursive `justAlNum(phrase)`

Write a recursive function called justAlNum(phrase) that, given a phrase, returns a new phrase with only the alphabetic and numerical characters from the original phrase.

For example, calling justAlNum("hello!") would return "hello", and calling justAlNum("500 College Ave") would return "500CollegeAve".

Hint: use the isalnum() string method to determine if a given string character is a letter, a digit, or something else:

>>> "A".isalnum()
True
>>> "9".isalnum()
True
>>> "!".isalnum()
False

Add some test code to main() to make sure your function is working.

3.2. recursive `palindrome(S)`

Write a recursive function called palindrome(S) that, given a string (S), returns True if the string is a palindrome, and False if not.

For example, calling palindrome("hello") would return False, and calling palindrome("hannah") or palindrome("12344321") would both return True.

Add some test code to main() to make sure your function is working.

3.3. put it all together in `main()`

Use the above functions in main() to tell the user if their input phrase is a palindrome or not.

def main():
   phrase = input("phrase: ").strip().lower()
   newphrase = justAlNum(phrase)
   if palindrome(newphrase):
      print("*is* a palindrome!")
   else:
      print("Nope...")

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.