Homework 3: Recursion and Error Practice

For this homework, you’ll get practice with writing recursive functions. You will practice writing recursive functions that take strings and lists as input. You’ll also learn more about Python’s error messages.

The purpose of this assignment is to practice using recursion. Iterative solutions that are otherwise correct will not get credit. There are some basic checks for this in the autograder, but it will also be checked manually following the deadline. Additionally, we will confirm that you use the correct algorithm for binary search (other search algorithms that involve looking at every item in the list will not get credit).

You can download the template file for this assignment here.

Problem 1: Reversing a String

Write a recursive function called reverse that will reverse any string text passed in as an argument and return the reversed string.

While you may be tempted to approach this without using recursion, please don’t - we are trying to learn how to approach problems recursively!

Start this by identifying the base case. Think of the simplest string that you could pass to the function – one from which you can immediately return an answer.

Then think about the recursive case. Can you decompose the problem into a smaller version of the original problem and a simple operation using the result of solving that problem?

When you are done, you should be able to call reverse() and get the behavior specified in the comments:

reverse("yoda") # returns "adoy"
reverse("reverse") # returns "esrever"

Problem 2: Binary Search

Binary search is an efficient algorithm for finding elements in a sorted list. We will discuss the algorithm on Thursday October 5th in class. The basic steps of the algorithm are as follows:

Check if the element at the middle of the list matches the target element
If it does, return True
Otherwise, split the list in half as follows:
- If the target element comes before the element at the middle of the list, keep the first half of the list
- If the target element comes after the element at the middle of the list, keep the second half of the list
If the list is now empty, return False
Otherwise, repeat the process from step 1 with the new shorter list

See the following iterative implementation of binary search:

def binary_search_iterative(sorted_list, item):
    """
    Uses iteration to check if an item is in a sorted list

    Arguments:
        sorted_list (list): a sorted list of ints or strings
        item (string/int): an element to search for in the list

    Returns:
        bool: True if item is in the list, False otherwise
    """
    while len(sorted_list) > 0:
        middle_index = len(sorted_list) // 2
        if sorted_list[middle_index] == item:
            # item is in the sorted_list, return True
            return True
        elif item < sorted_list[middle_index]:
            # create a new list with only elements before middle_index and repeat
            sorted_list = sorted_list[:middle_index]
        else:
            # create a new list with only elements after middle_index and repeat
            sorted_list = sorted_list[middle_index + 1:]
    # we did not find the item, return False
    return False

Your task is to write a recursive function binary_search that takes a list sorted_list and an element item as input, and returns True if the element is in the list and False otherwise. You may take as much inspiration and syntax from the iterative version as you want, but you will need to replace the while loop-based approach with a recursive approach.

You might want to think about the conditions used in this loop: do any of them look like a base case? Do any of them look like recursive cases?

The function is expected to work with both lists of lowercase strings and lists of integers as input. It is assumed that item will have the same type as all of the elements in the sorted_list.

When you are done, you should be able to call binary_search() and get the behavior specified in the comments:

binary_search(["infection", "omission", "pardon", "prose", "scorn"], "infection") # returns True
binary_search(["infection", "omission", "pardon", "prose", "scorn"], "yoda") # returns False
binary_search([-849, -844, -175, 536, 911], -849) # returns True
binary_search([-849, -844, -175, 536, 911], 10) # returns False

Make sure that you only test your function on lists that have been sorted!

You will not get credit if you implement linear search instead of binary search (even though the autograder doesn’t have a check for that)!

Problem 3: Error Message Scavenger Hunt

Take a moment to run the following code in Thonny:

print(2 + " apples")

You should observe some angry-looking red text, including the phrase TypeError`. This is an indication that we have attempted an operation on incompatible types: Python doesn’t know how to add together the integer 2 and the string “ apples”. When an error is encountered, Python “raises” (shows) it to you, the user.

Your aim in this question is to write functions that raise errors! Specifically, I want you to write functions that contain code that raises specific errors. For example:

def raises_type_error():
    """
    a function that raises a TypeError
    a TypeError is the error raised by Python when an operator or function is applied to a value of an inappropriate type
    """
    return 2 + " apples"

Calling this function results in a TypeError being raised. In this problem, that’s what I want you to do!!

Follow this same pattern to fill in the functions below in your program. This code is also included in the template file.

TESTING YOUR FUNCTIONS:

To test your functions, you should call them one at a time and make sure that you observe the expected errors. After you’re confident in each function, you should delete or comment out the function call so that the rest of your script can run.

You should not change the number of parameters for any of these functions

def raises_module_not_found_error():
    """
    a function that raises a ModuleNotFoundError
    a ModuleNotFoundError is the error raised by Python when you attempt to import a module 
    that cannot be found
    """
    pass # replace pass with your code

def raises_index_error():
    """
    a function that raises an IndexError
    an IndexError is the error raised by Python when you attempt to access an index of a 
    string that is out of range (e.g. too long for the string)
    """
    pass # replace pass with your code

def raises_name_error():
    """
    a function that raises a NameError
    a NameError is the error raised by Python when you attempt to refer to a variable or 
    function that hasn't been defined yet
    """
    pass # replace pass with your code

def raises_zero_division_error():
    """
    a function that raises a ZeroDivisionError
    you can probably guess what this one means =)
    """
    pass # replace pass with your code

def raises_recursion_error():
    """
    a function that raises a RecursionError
    a RecursionError is the error raised by Python when you don't have a base case in your recursive function
    (or just go too deep in your recursive calls)
    """
    pass # replace pass with your code

Submission

Submit your assignment on gradescope as submission.py. All components (excluding style and double-checking that you used recursion) are auto-graded.