← Schedule

HW 6: Recursion & exceptions

CMSC 141: Introduction to Python

Due Sunday, August 2, 11:59pm

This homework has two short parts. First you'll write a handful of recursive functions, which are functions that call themselves. Then you'll use try/except to keep a program from crashing when the data is messy.

Neither part is large on its own. Recursion is the one that feels strange the first time, so the first part starts as small as it can and grows one step at a time. Do the exercises in order.

Goals

What this homework builds

This homework builds S12 (recursion) and S13 (exceptions). S12 is assessed on Quiz 6 and again on the final, so use this homework to get recursion solid now rather than waiting. S13 is first assessed on the final and graded leniently. The second part reads a file, which you've already practiced in Homeworks 3 and 4; here the new idea is handling the things that can go wrong while reading.

Getting started

From your coursework folder, pull the new files and move into the homework directory:

$ git pull
$ cd hw6
$ ls

You should see hw6.py (where your code goes) and one data file used in Part 2: readings.txt. Add your functions to hw6.py. You can test a single function as you go by running pytest from the hw6 directory.

Part 1: Recursion

A recursive function is one that calls itself on a smaller version of the same problem. Every recursive function needs two things: a base case, the smallest version that you answer directly without calling yourself, and a recursive case, where you do a little work and hand the rest off to another call on smaller input. If you forget the base case, the function calls itself forever. So write the base case first, every time.

Here is the whole idea in one example. To add up 1 + 2 + ... + n, notice that the answer for n is just n plus the answer for n - 1. The smallest case is n equal to 0, where the sum is 0.

def sum_to(n):
    """Return 1 + 2 + ... + n. Assume n >= 0."""
    if n == 0:        # base case: answer it directly
        return 0
    return n + sum_to(n - 1)   # recursive case: smaller problem

Trace it for n = 3: sum_to(3) is 3 + sum_to(2), which is 3 + (2 + sum_to(1)), which is 3 + (2 + (1 + sum_to(0))), which is 3 + 2 + 1 + 0, which is 6. That function is given to you in hw6.py as a worked example. The next five are yours.

Exercise 1: count_items

Write count_items(items) that returns how many things are in a list, without using len(). The base case is the empty list [], which has 0 items. Otherwise, a list has one item (its first one) plus however many are in the rest of it. You can get "the rest of the list" with items[1:], which is everything after the first item.

>>> count_items([])
0
>>> count_items([9, 8, 7])
3

Exercise 2: reverse_string

Write reverse_string(s) that returns the string s backwards. The base case is the empty string "", which reversed is just "". Otherwise, the reverse of a string is the reverse of everything-after-the-first-character, followed by the first character. As with lists, s[1:] is everything after the first character, and s[0] is the first character.

>>> reverse_string("")
''
>>> reverse_string("recurse")
'esrucer'

Exercise 3: count_char

Write count_char(s, ch) that returns how many times the single character ch appears in the string s. The base case is the empty string, which contains ch zero times. Otherwise, look at the first character: it counts for 1 if it equals ch and 0 if it doesn't, and then add on the count from the rest of the string.

>>> count_char("banana", "a")
3
>>> count_char("banana", "z")
0

Exercise 4: factorial

The factorial of a whole number n, written n!, is n * (n - 1) * ... * 2 * 1. So 4! is 4 * 3 * 2 * 1, which is 24. By convention 0! is 1. Factorial is a natural fit for recursion, because n! is just n times (n - 1)!.

Write factorial(n) recursively. The base case is n equal to 0 or 1, where the answer is 1. Otherwise, return n times the factorial of n - 1. Assume n >= 0.

>>> factorial(0)
1
>>> factorial(5)
120

Trace factorial(5) if it helps: it's 5 * factorial(4), which is 5 * (4 * factorial(3)), and so on down to factorial(1), which stops the chain.

Exercise 5: list_max

Write list_max(nums) that returns the largest number in a non-empty list, without using max(). The base case is a list with a single item, whose largest number is that one item. Otherwise, compare the first item against the largest of the rest of the list, and return whichever is bigger. Remember that nums[0] is the first item and nums[1:] is everything after it. You may assume the list has at least one number in it.

>>> list_max([9])
9
>>> list_max([3, 7, 2, 9, 4])
9
>>> list_max([-5, -2, -8])
-2

If you find yourself reaching for a for loop on any of these five, stop. The point of this part is to practice recursion, so each of them should call itself. You'll get the loop versions for free once you've seen both.

Part 2: Exceptions

When something goes wrong at run time, Python raises an exception and, by default, the program crashes. try/except lets you catch the problem and keep going. You put the risky code in the try block and what-to-do-instead in the except block:

try:
    value = int(line)
except ValueError:
    # int() failed because the line wasn't a number
    ...

int("70") works, but int("sensor error") raises a ValueError. Catching it means one bad line doesn't sink the whole program.

Exercise 6: total_valid_readings

The file readings.txt is supposed to hold one number per line, but real sensor logs are messy and some lines are junk:

72
68
sensor error
70
N/A
75

Write total_valid_readings(filename) that adds up only the lines that are whole numbers and skips the rest. Wrap the int(line) in a try/except ValueError; when a line can't be converted, skip it and move on (the continue statement jumps to the next line).

There's one more way this can fail: the file might not exist at all, which raises a FileNotFoundError when you try to open it. Handle that too, by returning 0 if the file isn't there.

>>> total_valid_readings("readings.txt")
285
>>> total_valid_readings("no_such_file.txt")
0

(72 + 68 + 70 + 75 is 285; the two junk lines are skipped.)

Requirements summary

In hw6.py: count_items, reverse_string, count_char, factorial, and list_max are each written recursively, with a base case and a recursive case and no loops. total_valid_readings sums the valid lines, skips the junk, and returns 0 for a missing file.

Testing your work

From inside the hw6 directory, run

uv run pytest

or test a single function with

uv run pytest -xvk factorial

This runs the tests in test_hw6.py against your hw6.py. Passing them all is a good sign your functions are correct.

Questionnaire

Fill out QUESTIONS-06.txt (in the hw6 folder) and submit it with your code. It isn't graded for correctness; it just tells me how the homework landed.

Submission

Submit hw6.py on Gradescope under "Homework 6." Run pytest from the hw6 directory first to check your work. Recursion is the part students most often want a second pass on, so if Part 1 isn't clicking, bring it to office hours before the quiz.