lab03 : Recursion

num ready? description assigned due
lab03 true Recursion Tue 04/23 11:59PM Tue 04/30 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.

Hint: Think of how you would manually count how many times you could repeatedly take away div from num. Each time you subtract, that’s akin to taking one step of recursion.

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

Hint: Check the first number of the list. If it’s even, include it in your result list. Then, let recursion handle the rest of the list.

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

Hint: Start with the first character. If it’s a vowel, count one; if not, don’t. Either way, proceed to the rest of the string recursively.

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

Hint: In a string, the reverse of all but the first character, followed by the first character, results in the full string reversed. Use this pattern for your recursion.

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

Hint: Compare the start of text to seq. If they match, remove seq from text and continue recursively without the first part of text. If they don’t match, keep the first character of text and continue to check the rest.

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: