CS 111
Summer 2 2018

# Problem Set 3

## Preliminaries

In your work on this assignment, make sure to abide by the collaboration policies of the course.

If you have questions while working on this assignment, please come to office hours, post them on Piazza, or email `cs111-staff@cs.bu.edu`.

Make sure to submit your work on Apollo, following the procedures found at the end of the assignment.

due by 9:00 p.m. on Saturday, July 07, 2018

### Problem 1: Thinking recursively

10 points; individual-only

Try to do this part before class!

Put your answers for this problem in a plain-text file named `ps3pr1.txt`.

Consider the following recursive function:

```def mystery(a, b):
if a == b:
return a
else:
return b + mystery(a + 1, b - 2)
```
1. Trace the execution of `mystery(1, 7)`. You may use any reasonable approach, provided that you show all of the calls to the function.

2. What is the value returned by `mystery(1, 7)`?

3. During the execution of `mystery(1, 7)`, stack frames are added and then removed from the stack. How many stack frames are on the stack when the base case is reached? You should assume that the initial call to `mystery(1, 7)` is made from the global scope, and you should include the stack frame for the global scope in your count.

4. Give an example of specific values of `a` and `b` that would produce infinite recursion, and explain why it would occur.

You may find it helpful to use the Python Tutor visualizer to build intuition about how recursion works, to check your answers to parts 1-3 of this problem, and to test and debug the functions that you write in the later problems. For example, to test the `mylen` function that we discussed in lecture, you could paste the following into the visualizer:

```def mylen(s):
if s == '':
return 0
else:
len_rest = mylen(s[1:])
return 1 + len_rest

test = mylen('cs111')
print('test is', test)
```

### Problem 2: Fun with recursion, part I

40 points; pair-optional
See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.

In this problem you will write several functions that employ the power of recursion!

In IDLE, use the File -> New Window menu option to open a new editor window for your program, and save it using the the name `ps3pr2.py`. Make sure to specify the `.py` extension.

Important guidelines:

• Include comments at the top of the file that are similar to the ones that we gave you at the top of `ps1pr1.py`.
• Your functions must have the exact names specified below, or we wonâ€™t be able to test them. Note in particular that the case of the letters matters (all of them should be lowercase), and that some of the names include an underscore character (`_`).
• As usual, each of your functions should include a docstring that describes what your function does and what its inputs are.
• Make sure that your functions return the specified value, rather than printing it. None of these functions should use a `print` statement.
• Unless the problem states otherwise, the functions that you write must use recursion. They may not use any iterative constructs that you may be aware of (`for`, `while`, etc.), and they may not use list comprehensions.
• More generally, you should not use any Python features that we have not discussed in lecture or read about in the textbook.
• Your functions do not need to handle bad inputs – inputs with a type or value that doesn’t correspond to the description of the inputs provided in the problem.
• Leave one or two blank lines between functions to make things more readable.
• Test each function after you write it. Here are two ways to do so:
• Run your file after you finish a given function. Doing so will bring you to the Shell, where you can call the function using different inputs and check to see that you obtain the correct outputs.
• Add test calls to the bottom of your file. These will be called every time that you run the file, which will save you from having to enter the tests yourself.
• Here again, we encourage you to use the Python Tutor visualizer, as described at the end of the previous problem.

Here are the descriptions of the functions:

1. Write a function `copy(s, n)` that takes as inputs a string `s` and an integer `n`, and that uses recursion to create and return a string in which `n` copies of `s` have been concatenated together.

To force you to use recursion, you may not use the multiplication operator (`*`). Rather, you should use recursion to add together `n` copies of `s`. For example, `'hello'*3` is equivalent to `'hello'+'hello'+'hello'`, and you will need to use recursion to compute that sum.

If `n` is less than or equal to 0, the function should return the empty string (i.e., the string `''`, which does not have any spaces between the quotes).

Here are some test cases:

```>>> copy('da', 2)
>>> copy('Go BU!', 4)
'Go BU!Go BU!Go BU!Go BU!'
>>> copy('hello', 1)
'hello'
>>> copy('hello', 0)
''
>>> copy('hello', -7)
''
```

This function is similar to the `power` function from lecture.

2. Write a function `compare(list1, list2)` that takes as inputs two lists of numbers, `list1` and`list2`, and that uses recursion to compute and return the number of values in `list1` that are larger than their corresponding value in `list2`. In other words, the function should compare `list1[0]` with `list2[0]`, `list1[1]` with `list2[1]`, `list1[2]` with `list2[2]`, etc, and it should return the number of positions at which the value from `list1` is larger than the value from `list2`. For example:

```>>> compare([5, 3, 7, 9], [2, 4, 7, 8])
2
```

The above call returns `2`, because:

• in position 0, 5 > 2
• in position 1, 3 < 4
• in position 2, 7 == 7
• in position 3, 9 > 8

Thus, there are two positions (0 and 3) at which the value from `list1` is larger than the value from `list2`.

Note that it is possible for the two lists to have different lengths, in which case the function should only compare the positions at which the two lists both have values.

```>>> compare([4, 2, 3, 7], [1, 5])      # 4 > 1; 2 < 5; can't compare 3 or 7
1
>>> compare([4, 2, 3], [1, 5, 0, 8])   # 4 > 1; 2 < 5; 3 > 0; can't compare 8
2
>>> compare([5, 3], [])
0
>>> compare([], [5, 3, 7])
0
```

This function is somewhat similar to the `mylen` function from lecture, but it needs to deal with lists instead of strings, and it needs to process two lists at the same time. You can find a modified version of `mylen` that handles both strings and lists here.

3. Write a function `letter_score(letter)` that takes a lowercase letter as input and returns the value of that letter as a scrabble tile. If `letter` is not a lowercase letter from ‘a’ to ‘z’, the function should return 0. This function does not require recursion.

Here is the mapping of letters to scores that you should use:

For example:

```>>> letter_score('w')
4
>>> print(letter_score('q'))
10
>>> letter_score('%')      # not a letter
0
>>> letter_score('A')      # not lower-case
0
```

We encourage you to begin with the following template:

```def letter_score(letter):
""" your docstring goes here """
assert(len(letter) == 1)

# put the rest of your function here
```

Note that we begin with an `assert` statement that validates the input for the parameter `letter`. If the condition given to `assert` is not true–in this case, if the input provided for `letter` has a length other than 1–then `assert` will cause your code to crash with an `AssertionError`. Using `assert` in this way can help you to find and debug situations in which you accidentally pass in incorrect values for the parameter of a function.

Hints:

• You will need to use conditional execution (`if-elif-else`) to determine the correct score for a given letter.

• You can greatly reduce the number of cases if you use the `in` operator, which tests for the presence of one string in another. For example:

```>>> letter = 'a'
>>> letter in 'happy'       # 'happy' does have an 'a'
True
>>> letter in 'recursion'   # 'recursion' does not have an 'a'
False
```

More generally, the `in` operator can be used to test for the presence of an element in any sequence – including a list. For example, given the variable `letter` above we could do:

```>>> letter in ['a', 'b', 'c']
True
```
4. Write a function `scrabble_score(word)` that takes as input a string `word` containing only lowercase letters, and that uses recursion to compute and return the scrabble score of that string – i.e., the sum of the scrabble scores of its letters. For example:

```>>> scrabble_score('python')
14
>>> scrabble_score('a')
1
>>> scrabble_score('quetzal')
25
```

Use your `letter_score` function and recursion to solve this problem. You may find it helpful to use the `num_vowels` function from lecture as a model. In that function, every vowel essentially had a value of 1, and every consonant had a value of 0. In this function, each letter has its letter score as its value.

5. At the bottom of your `ps3pr2.py` file, add at least one test call for each of the functions that you wrote for this problem. For example:

```test1 = copy('da', 2)
print('the first test returns', test1)
```

### Problem 3: Fun with recursion, part II

50 points; individual-only

This problem provides more practice in writing recursive functions.

In IDLE, use the File -> New Window menu option to open a new editor window for your program, and save it using the the name `ps3pr3.py`. Make sure to specify the `.py` extension. Follow the same guidelines that we gave you for problem 3, and make sure that all of your functions except `one_dna_to_rna` use recursion.

1. Write a function `double(s)` that takes an arbitrary string `s` as input, and that uses recursion to construct and return the string formed by doubling each character in the string. Here are three examples:

```>>> double('hello')
'hheelllloo'
>>> double('python')
'ppyytthhoonn'
>>> double('')
''
```
2. Write a function `weave(s1, s2)` that takes as inputs two strings `s1` and `s2` and uses recursion to construct and return a new string that is formed by “weaving” together the characters in the strings `s1` and `s2` to create a single string. In other words, the new string should alternate characters from the two strings: the first character from `s1`, followed by the first character from `s2`, followed by the second character from `s1`, followed by the second character from `s2`, etc. If one of the strings is longer than the other, its “extra” characters – the ones with no counterparts in the shorter string – should appear immediately after the “woven” characters (if any) in the new string.

```>>> weave('aaaaaa', 'bbbbbb')
'abababababab'
>>> weave('abcde', 'VWXYZ')
'aVbWcXdYeZ'
>>> weave('aaaaaa', 'bb')    # four extra 'a' characters at the end
'ababaaaa'
>>> weave('aaaa', 'bbbbbb')  # two extra 'b' characters at the end
'ababababbb'
>>> weave('aaaa', '')        # all of the 'a' characters are extra!
'aaaa'
>>> weave('', 'bbbb')        # all of the 'b' characters are extra!
'bbbb'
>>> weave('', '')
''
```

Hint: You will need more than one base case.

3. Write a function `index(elem, seq)` that takes as inputs an element `elem` and a sequence `seq`, and that uses recursion to find and return the index of the first occurrence of `elem` in `seq`. The sequence `seq` can be either a list or a string. If `seq` is a string, `elem` will be a single-character string; if `seq` is a list, `elem` can be any value. Don’t forget that the index of the first element in a sequence is 0.

Important notes:

• If `elem` is not an element of `seq`, the function should return the special value `None`, which does not have any quotes around it.

• You may not use the `in` operator in this function.

Here are some examples:

```>>> index(5, [4, 10, 5, 3, 7, 5])
2
>>> index('hi', ['well', 'hi', 'there'])
1
>>> index('b', 'banana')
0
>>> index('a', 'banana')
1
>>> index('i', 'team')
>>>
```

Important: If you call your `index` function from the Shell and the function returns `None`, you will not actually see the `None` value after the function call. Instead, you will just see another Shell prompt, as shown above. To make sure that your function is returning `None`, you can either make the call as part of a `print` statement or compare the return value to `None`:

```>>> print(index('i', 'team'))
None
>>> index('i', 'team') == None
True
```

We recommend that you try both of these tests. Here are some other examples:

```>>> print(index('hi', ['hello', 111, True]))
None
>>> print(index('a', ''))      # the empty string
None
>>> print(index(42, []))       # the empty list
None
```

Hints:

• The closest model for this problem is the version of the `mylen` function that is able to handle both lists and strings.
• You will need more than one base case for this function.
• In the recursive case, the decision about what to return will need to take into account the result of the recursive call. As a result, it is especially important that you store in a variable the value that is returned by the recursive call.

DNA transcription! The last two functions are based on an incredible molecular feat called transcription, in which your cells create molecules of messenger RNA that mirror the sequence of nucleotides in your DNA. The RNA is then used to create proteins that do the work of the cell.

1. Write a function called `one_dna_to_rna(c)` that takes as input a single-character string `c` representing a DNA nucleotide and returns the corresponding messenger-RNA nucleotide. Here are the DNA-to-RNA conversions:

`'A'` in DNA becomes `'U'` in RNA.
`'C'` in DNA becomes `'G'` in RNA.
`'G'` in DNA becomes `'C'` in RNA.
`'T'` in DNA becomes `'A'` in RNA.

Any other input should return the empty string (`''`). This function does not require recursion.

Here are some examples:

```>>> one_dna_to_rna('C')
'G'
>>> print(one_dna_to_rna('T'))
A
>>> one_dna_to_rna('X')
''
>>> one_dna_to_rna('c')       # lower-case letters don't count
''
```

We encourage you to begin with the following template:

```def one_dna_to_rna(c):
""" your docstring goes here """
assert(len(c) == 1)

# put the rest of your function here
```

Here again, we begin with an `assert` statement that validates the input for the parameter `c`. If the condition given to `assert` is not true–in this case, if the input provided for `c` has a length other than 0–then `assert` will cause your code to crash with an `AssertionError`. Using `assert` in this way can help you to find and debug situations in which you accidentally pass in incorrect values for the parameter of a function.

2. Write a function called `transcribe(s)` that takes as input a string `s` representing a piece of DNA, and that uses recursion to construct and return a string representing the corresponding RNA. Any characters in the input that don’t correspond to a DNA nucleotide should not appear in the returned RNA string. (Note that if you implemented the previous function correctly, you shouldn’t need to do anything special here to ensure that non-DNA characters are removed.) For example:

```>>> transcribe('ACGT TGCA')
'UGCAACGU'
>>> transcribe('GATTACA')
'CUAAUGU'
```

Use your `one_dna_to_rna` function and recursion to solve this problem. As with the `scrabble_score` function, you may find it helpful to use the `num_vowels` function from lecture as a model, but in this case you will be adding together strings instead of numbers!

Don’t forget to test your functions using the approaches mentioned at the start of Problem 3. In particular, you are encouraged to add test calls to the bottom of the file, although doing so is not required for this problem.

You should use Apollo to submit the following files:

• your `ps3pr1.txt` file containing your solutions for Problem 1
• your `ps3pr2.py` file containing your solutions for Problem 2; if you worked with a partner, make sure that you each submit a copy of your joint work, and that you include comments at the top of the file specifying the name and email of your partner
• your `ps3pr3.py` file containing your solutions for Problem 3

Warnings

• Make sure to use these exact file names, or Apollo will not accept your files. If Apollo reports that a file does not have the correct name, you should rename the file using the name listed in the assignment or on the Apollo upload page.

• If you make any last-minute changes to one of your Python files (e.g., adding additional comments), you should run the file in IDLE after you make the changes to ensure that it still runs correctly. Even seemingly minor changes can cause your code to become unrunnable.

• If you submit an unrunnable file, Apollo will accept your file, but it will print a warning message. If time permits, you are strongly encouraged to fix your file and resubmit. Otherwise, your code will fail most if not all of our tests.

Here are the steps:

Note: If you encounter problems with Apollo, close your browser and try again. If possible, you may also want to wait an hour or two before retrying. If you are unable to submit and it is close to the deadline, email your homework before the deadline to `cs111-staff@cs.bu.edu`.