CS21 Lab 10: Recursion

This lab is due Monday, November 29, before midnight

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

Solve problems using recursion.
Write test cases to check correctness.

Requirements

Write recursive solutions for each of the functions below. You should not have any for loops or while loops in your solutions.

For each program, you should write a main function that tests your recursive function on the example inputs and at least two additional test cases of your own design. We encourage you to write the test cases before implementing the recursive function. That way, you’ll have a good idea of what’s supposed to happen in advance. If your function’s behavior doesn’t match your expectations, tracing through the test case should help you to think through where the bug might be in your implementation.

You can test your functions either by printing out the function you are calling (and verifying the answers are correct by visual inspection) or by using assert (and having python check your answers for you):

# using print and then visually inspecting the output
lst = [2, 3, 5]
result = contains_number(lst, 3)
print("contains_number(%s, 3) = %s" % (lst, result))

# using assert and having python check your answers
assert contains_number(lst, 3) == True

If the condition after the assert evaluates to True, you won’t see any output because it behaved as expected. If the condition evaluates to False, you will see an AssertionError indicating that there is a problem with your recursive function’s implementation. If an assertion fails, you may find it helpful to print the result to see how it differs from expected.

Helpful syntax reminders

When working through these recursion problems, we’ll frequently be using strings and lists, which are both "collections" of things: strings are collections of characters, and lists are collections of arbitrary elements. As collections, both strings and lists offer some utilities to make it easier to work with them. We’ve seen these before, but they’ll come in handy for this lab, so here’s a brief refresher:

Concatenation (+ operator)

Strings and lists both support using the + operator for concatenation:

>>> s1 = "hello"
>>> s2 = "there"
>>> s1 + s2
'hellothere'

>>> l1 = [1, 2]
>>> l2 = [3, 4]
>>> l1 + l2
[1, 2, 3, 4]

Note that when concatenating collections, the values on both sides of the + operator must be of the same type (e.g., both strings or both lists). If you attempt to use + on different types, you might see a message like:

>>> s1 = "hello"
>>> l1 = [1, 2]
>>> s1 + l1
Traceback (most recent call last):
  File "", line 1, in 
TypeError: can only concatenate str (not "list") to str

Slicing

Both strings and lists support slicing, which allows you to access subsets of the string/list. When slicing a collection, you can express a range of indices from which to pull a subset of the collection. For example:

>>> s = "hello CS21"
>>> s[2:5]
'llo'

Here, the [2:5] says to extract from s the characters starting at index 2 up to (but not including) index 5. The same syntax works for lists:

>>> l = ["a", "b", "c", "d", "e", "f"]
>>> l[1:4]
['b', 'c', 'd']

For this lab, you may find that occasionally, you want to slice a collection to take all items starting from a certain index. Python supports a shorthand syntax to get all remaining items in the collection starting from an index:

>>> l = ["a", "b", "c", "d", "e", "f"]
>>> l[2:]
['c', 'd', 'e', 'f']

With this shorthand syntax, you don’t need to worry about how many items are in the collection if you just want to peel off item(s) from the front.

You can find more details and examples in the week 5 class notes.

1. first_integers

The first_integers function should take one parameter, N, and recursively compute the sum of the first N integers, returning the result.

For example:

first_integers(3) = 3 + 2 + 1 + 0 = 6

first_integers(7) = 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0 = 28

first_integers(0) = 0 = 0

You may assume that the user will pass in either a positive integer or zero — you don’t need to worry about handling a negative input.

For mathematical reasons that are beyond the scope of CS 21, the sum of the first N integers is equal to the formula:

N * (N + 1) / 2

Using the formula may help you to know what answers to expect from your function.

1.1. Test cases in main

Before implementing contains_number, write some test cases to help reason about how it should behave. Here are three examples. Your main function should have these and at least two additional test cases of your own design.

def main():
    assert first_integers(3) == 6
    assert first_integers(7) == 28
    assert first_integers(0) == 0

    # TODO: Add your test cases here.

2. contains_number

The contains_number function should take two parameters, a list and an integer, and return a Boolean to indicate whether the list contains (True) or does not contain (False) that integer. NOTE: for this function, you must use recursion — don’t use a loop or the in operator on the list.

2.1. Test cases in main

def main():
    lst = [2, 3, 5]
    assert contains_number(lst, 3) == True
    assert contains_number(lst, 7) == False
    assert contains_number([1, 3, 5, 7], 7) == True

    # TODO: Add your test cases here.

3. replace_letter

The replace_letter function takes a string, a target letter, and a replacement letter. The function should recursively work through the input string to ultimately produce a new string in which all instances of the target letter are replaced by the replacement letter.

3.1. Test cases in main

Before implementing replace_letter, write some test cases to help reason about how it should behave. Here are three examples. Your main function should have these and at least two additional test cases of your own design.

def main():
    assert replace_letter("hello", "e", "o") == "hollo"
    s = "Now is the best time"
    assert replace_letter(s, "e", "a") == "Now is tha bast tima"
    assert replace_letter("", "s", "z") == ""

    # TODO: Add your test cases here.

4. filter_larger_than

The filter_larger_than function takes two parameters, a list (of numbers) and an integer (max_value). It returns new list that excludes (filters out) any numbers in the original list that are larger than max_value.

4.1. Test cases in main

Before implementing filter_larger_than, write some test cases to help reason about how it should behave. Here are three examples. Your main function should have these and at least two additional test cases of your own design.

def main():
    assert filter_larger_than([7, 2, 5, 4, 6, 3], 5) == [2, 5, 4, 3]
    assert filter_larger_than([100, 200, 300], 10) == []
    assert filter_larger_than([], 15) == []

    # TODO: Add your test cases here.

5. split_string

The split_string function behaves like (a simplified version of) the .split() string method. Our version of split_string takes in only a string and produces a list that contains each chunk of the string as divided by spaces.

To simplify the implementation, you may assume:

The string will not contain any blank spaces at the beginning or end. That is, the first and last characters of the string will be visible characters (letters, numbers, or symbols).
The string will not contain consecutive spaces — there will be exactly one space separating visible characters within the string.

For our split_string function, we will only split on spaces — you do NOT need to worry about splitting on anything else (e.g., commas, semicolons, etc.).

For the split_string function only, you may use the in operator on a string (to determine if there are spaces in the string) and the string.index method (to find the index of the first space). Note that you want to use in to confirm that a string has spaces prior to calling .index. Otherwise, your program will generate an exception if you ask for the index of a character that doesn’t appear in the string. For example:

>>> s = "one two"
>>> " " in s
True
>>> s.index(" ")
3

>>> s = "nospaces"
>>> " " in s
False
>>> s.index(" ")
Traceback (most recent call last):
  File "", line 1, in 
ValueError: substring not found

5.1. Test cases in main

Before implementing split_string, write some test cases to help reason about how it should behave. Here are three examples. Your main function should have these and at least two additional test cases of your own design.

def main():
    assert split_string("Hello there!") == ["Hello", "there!"]
    assert split_string("This_has_no_spaces") == ["This_has_no_spaces"]
    assert split_string("") == []

    # TODO: Add your test cases here.

6. Optional Challenge: binary_search

This is an optional extra challenge. This part does not affect your grade, so please only attempt this after completing the rest of your lab.

So far, we’ve only seen an iterative version of binary search, but logically, it also makes sense to define binary search recursively by repeatedly calling the same binary_search function with different inputs. For this extra challenge, define a binary_search function that takes in an item to search for, a list to search within, a low index, and a high index. The function should return the index at which the item appears in the list or -1 if the item does not appear in the list.

If the item appears in the list more than once, you can return the index of the first one you find — it doesn’t necessarily have to be the first index in the list where the item appears.

You may assume that the list is already sorted prior to calling your binary_search function.

Like the other programs for this week, write a main function with several test cases to verify that your implementation works as expected.

7. Optional Challenge: ruler

This is an optional extra challenge. This part does not affect your grade, so please only attempt this after completing the rest of your lab.

Using the Zelle graphics library, use recursion to recursively draw the marks that you might find on a ruler. For example:

Ruler hash marks

Your function should take only three input parameters: the top point of the center line, the height of the center line, and a graphics window on which to draw the lines.

Like the other programs for this week, write a main function to test your ruler implementation.

Submitting your work

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.

Logging out

When you’re done working in the lab, you should log out of the computer you’re using. First quit any applications you are running, like the browser and the terminal. Then click on the logout icon ( or other logout icon ) and choose "log out".

If you plan to leave the lab for just a few minutes, you do not need to log out. It is, however, a good idea to lock your machine while you are gone. You can lock your screen by clicking on the lock xlock icon. PLEASE do not leave a session locked for a long period of time. Power may go out, someone might reboot the machine, etc. You don’t want to lose any work!