## 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...")``````

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.
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.