Skip to main content

Class 21 - Recursive functions by examples

Date: October 29, 2026

⚠️Homework
Homework 7 due November 1, 2026
‼️Ending Skills
Last week for skills: 10, 11

Skills: 7​

Notes (review before class)​

Lists: First and Rest​

  • Every non-empty list has a first element and a rest, which is itself a list: [1, 2, 3] has first 1 and rest [2, 3]; that has first 2 and rest [3]; that has first 3 and rest [], the empty list.
  • Lists are structured data: parts in a well-defined format, which programs can follow. (Tables are only somewhat structured: different tables have different column names.)

Accessors and Constructors​

Accessors take structured data apart, based only on its structure, not its contents: lst[0] is the first element, and lst[1:] is the rest (a slice from position 1 to the end, as with strings on Class 11):

l1 = [1, 2, 3]
e1 = l1[0]
l2 = l1[1:]
e2 = l2[0]
l3 = l2[1:]
e3 = l3[0]
l4 = l3[1:]

def test_first_and_rest():
    assert e1 == 1
    assert e2 == 2
    assert e3 == 3
    assert l2 == [2, 3]
    assert l3 == [3]
    assert l4 == []

Constructors build structured data. Adding a one-element list holding the first element to the front of the rest builds the same list:

def test_building_lists():
    assert [1, 2, 3] == [1] + ([2] + ([3] + []))
  • Verbose, and harder for humans to read, but it shows the structure that programs use. A list is either:
    • empty, written [], or
    • non-empty, written [f] + r (or with at least one value between the brackets): a first f, and a rest r that is also a list (so it is empty or non-empty, ...).
  • So lists are conditional data (as on Class 20).
  • Try: write ["lychee", "dates", "mango", "durian"] this way.

Examples over a List and Its Suffixes​

  • len and sum are built in (and PLL reports a name that hides a built-in), so ours are my_len and my_sum. One strategy works for both.
  • Always write at least two examples, one with [] and one non-empty; then more for the problem, and more to show how you think about solving it.
  • Use a list and each of its suffixes, lined up. ([9] is a sub-list of [7, 8, 9], the rest of its rest; [7] is not.)
def test_my_len():
    assert my_len([7, 8, 9]) == 3  # 1 + 2
    assert my_len([   8, 9]) == 2  # 1 + 1
    assert my_len([      9]) == 1  # 1 + 0
    assert my_len([       ]) == 0

Each answer is 1 (the first element's contribution) plus the length of the rest, which is the answer on the next line. Replace those lengths with the calls that produce them:

def test_my_len():
    assert my_len([7, 8, 9]) == 1 + my_len([8, 9])
    assert my_len([   8, 9]) == 1 + my_len([   9])
    assert my_len([      9]) == 1 + my_len([    ])
    assert my_len([       ]) == 0

The same for my_sum: my_sum([7, 8, 9]) is 7 + 8 + 9, which is 7 + my_sum([8, 9]):

def test_my_sum():
    assert my_sum([7, 8, 9]) == 7 + my_sum([8, 9])
    assert my_sum([   8, 9]) == 8 + my_sum([   9])
    assert my_sum([      9]) == 9 + my_sum([    ])
  • The last line forces my_sum([]) to be 0, the additive identity (adding it to a number gives that number).
  • In both, the answer for a list uses the function's answer on its rest.
  • Try: we now claim that my_len([7, 8, 9]) is 3, 1 + 2, 1 + my_len([8, 9]), and 1 + my_len([7, 8, 9][1:]). Check that you agree with each, and see how each comes from the one before it.

From Examples to Code: match on Lists​

Written with [1:], each non-empty example has the same shape, my_len(some_list) == 1 + my_len(some_list[1:]); only the empty one differs. To run different code for the two kinds of lists, use match:

match e:
    case []:
        ...
    case [f, *r]:
        ...  # can use f and r here
  • Python evaluates e (any expression whose value is a list), then:
    • if it is empty, runs the code under case []:;
    • otherwise, adds f (the first) and r (the rest) to the program directory, and runs the code under case [f, *r]:.
  • The * makes r the list of all the remaining elements, not a single one.
  • Any names will do; ones that fit the problem (like price, for a list of prices) help.

Each case comes straight from the examples:

def my_len(lst: list) -> int:
    """computes the number of elements in lst"""
    match lst:
        case []:
            return 0
        case [f, *r]:
            return 1 + my_len(r)

def my_sum(lst: list[float]) -> float:
    """adds up the numbers in lst"""
    match lst:
        case []:
            return 0
        case [f, *r]:
            return f + my_sum(r)
  • r is already the rest of lst, so there's no [1:].
  • The two are nearly the same: the structure of the data suggests the structure of the program.
  • lst: list makes an argument that isn't a list, like my_len(5), an error.

Strategy: Developing Functions Over Lists​

  1. Pick a concrete list with (at least) three elements. Write examples for it and each of its suffixes, including [].
  2. Rewrite each answer in terms of the first and rest of its input (no need to write [0] and [1:], but you should see the first and rest values).
  3. Write the pattern across the answers as code: a match, with each case based on your examples.

This works for any structured data, using its parts in place of first and rest.

Recap (20 mins)​

We want to add up the numbers in a list, up to the first 0 (or all of them, if there is no 0). Here are its examples, for a list and each of its suffixes, rewritten in terms of first and rest, and the function they lead to:

def add_till_zero(lst: list[float]) -> float:
    """adds up the numbers in lst, up to the first 0 (or all, if there is no 0)"""
    match lst:
        case []:
            return 0
        case [f, *r]:
            if f == 0:
                return 0
            else:
                return f + add_till_zero(r)

def test_add_till_zero():
    assert add_till_zero([7, 3, 0, 5]) == 7 + add_till_zero([3, 0, 5])
    assert add_till_zero([   3, 0, 5]) == 3 + add_till_zero([   0, 5])
    assert add_till_zero([      0, 5]) == 0
    assert add_till_zero([         5]) == 5 + add_till_zero([       ])
    assert add_till_zero([          ]) == 0
  • Rewrite each test's right side as a plain number, starting from the bottom. What is add_till_zero([7, 3, 0, 5])?
  • For the call add_till_zero([5]), which case runs, and what are f and r?
  • Which test is the reason for the if f == 0:? What would add_till_zero([7, 3, 0, 5]) be without it?

Class Exercises (35 mins)​

  1. Try to rewrite add_till_zero with a for loop. If you were able to, was it as easy as above? What made it more complicated? If you were unable to, that is fine, but why was it harder?
  2. Design a function strings_less_than that, given a list of strings as input, returns a list of strings that only includes those in the input whose length was less than a constant LEN_LIMIT.
  3. Rewrite strings_less_than using a for loop. Was it harder? Why or why not?
  4. Design a function find_error_suffix that takes as input a list of strings, which may include the string "error". If that string occurs, your function should return the suffix of the list starting with that string. If that string is not in the list, then it should return the empty list.
  5. Rewrite find_error_suffix using a for loop. If you were able to, was it as easy? What made it more complicated?

Wrap-up (5 mins)​

  • Lists are structured / conditional data.
  • By examining concrete examples we can figure out a recursive definition.
  • Certain patterns of code are easier to express recursively, but others are not.