lab03 : Recursion

num ready? description assigned due
lab03 true Recursion Fri 01/26 11:59PM Mon 02/05 11:59PM

Learning Goals

In this lab, you’ll practice:

Before you get started, make sure to read up on recursion, specifically Chapter 4.2.

Instructions

For this lab, you will need to create two files:

There will be no starter code for this assignment, but rather function descriptions are given in the specification below.

It’s recommended that you organize your lab work in its own directory. This way all files for a lab are located in a single folder. Also, this will be easy to import various files into your code using the import / from technique shown in lecture.

Recursive function definitions and specifications

You will write five recursive functions for this lab. Each one is specified below. One example test will be given, but you should write 3 - 5 explicit tests for each function (think of edge cases and various interesting cases when writing your tests!).

Note: You must write each function recursively in order to receive any credit; you may receive a 0 for your implementation, even if Gradescope’s tests pass. For this lab, you may not (and need not) define additional helper functions.

# Example test
assert int_division(27, 4) == 6

# Example test
assert get_even_ints([1, 2, 3, 4, 5]) == [2, 4]

# Example test
assert count_vowels("This Is A String") == 4

# Example test
assert reverse_str("CMPSC9") == "9CSPMC"

Example test
assert remove_seq("Lolololol", "lol") == "Loo"
# The first "lol" is removed, which reduces the string 
# to: "Loolol". Then the 2nd "lol" is removed, which 
# reduces the string to: "Loo"

The fact that we are removing the occurences of the seq in the order they appear, means that in this function, we are not going back to recheck that we introduced a new seq in the earlier part of the string by removing its occurrence later. Here, we are assuming that the following function call remove_seq("ababcc", "abc") will return 'abc', not an empty string. (You can challenge yourself to see how your function needs to be modified to handle it recursively, but this is not part of this lab.)

Hints: Think of what your base case could be, test it - what’s the simplest case where you don’t need to do any work?

Which one of these cases would trigger your base case?

testFile.py pytest

This file will contain unit tests using pytest to test if your functionality is correct. Write your tests first in order to check the correctness of your recursive function. Again, Gradescope requires testFile.py to be submitted before running any autograded tests. You should write 3 - 5 tests per function.

The asserts will be marked 0 if some of the asserts in testFile.py fail.

Here’s the structue for the test file that you can use to get started:

# testFile.py

def test_int_division():
    # from lab03 import int_division
    # uncomment the above import post completion of function in lab03.py
    # write your assert statements here
    pass # remove this after writing asserts

def test_get_even_ints():
    # from lab03 import get_even_ints
    # uncomment the above import post completion of function in lab03.py
    # write your assert statements here
    pass # remove this after writing asserts

def test_count_vowels():
    # from lab03 import count_vowels
    # uncomment the above import post completion of function in lab03.py
    # write your assert statements here
    pass # remove this after writing asserts

def test_reverse_string():
    # from lab03 import reverse_str
    # uncomment the above import post completion of function in lab03.py
    # write your assert statements here
    pass # remove this after writing asserts

def test_remove_seq():
    # from lab03 import remove_seq
    # uncomment the above import post completion of function in lab03.py
    # write your assert statements here
    pass # remove this after writing asserts

Submission

Once you’re done with writing your recursive function definitions and tests, submit your lab03.py and testFile.py files to the Lab03 assignment on Gradescope. There will be various unit tests Gradescope will run to ensure your code is working correctly based on the specifications given in this lab.

If the tests don’t pass, you may get some error message that may or may not be obvious at this point. Don’t worry - if the tests didn’t pass, take a minute to think about what may have caused the error. If your tests didn’t pass and you’re still not sure why you’re getting the error, feel free to ask your TAs or Learning Assistants.

Troubleshooting

RecursionError: maximum recursion depth exceeded while calling a Python object

If you are getting the error above, check: