Practice 8 — Recursion on Lists

Skills: 7

Reading: the Notes section of Class 22

Recursion on Lists

Lists are structured data with two parts: a first element and the rest (which is itself a list). Although we've computed with lists using for loops, another approach is to process lists recursively.

Discovering Patterns Through Examples

Example 1: Computing the Count of Elements

Step-by-Step Examples:

• my_count([]) is 0
• my_count([7]) is 1
• my_count([3, 8, 5]) is 3
  • Notice: The first element is 3, and the rest is [8, 5], which has count 2
  • So we can say: my_count([3, 8, 5]) is 1 + my_count([8, 5])

An empty list has count 0, and a non-empty list's count is 1 plus the count of its rest.

Example 2: Finding the Total of Elements

Step-by-Step Examples:

• my_total([]) is 0
• my_total([6]) is 6
• my_total([6, 4, 2]) is 6 + (total of [4, 2]), which is 6 + 6 = 12

For a non-empty list, the total equals the first element plus the total of the rest.

From Examples to Code

If the list is empty, return the "base case" value. If the list is non-empty, then combine the first element with the recursive call on the rest.

Writing the Code for my_count

Design a recursive function my_count that counts the elements in a list:

def my_count(lst: list) -> int:
    match lst:
        case []:
            pass  # YOUR CODE HERE
        case [f, *r]:
            pass  # YOUR CODE HERE

def test_my_count():
    assert my_count([]) == 0
    assert my_count([7]) == 1
    assert my_count([3, 8, 5]) == 3

Writing the Code for my_total

Design a recursive function my_total that sums the numbers in a list.

The General Recursive Template

Write the general pattern:

def function_name(lst: list[T]) -> R:
    match lst:
        case []:
            <base-case-expression>
        case [first, *rest]:
            <combine first and recursive call on rest>

Explanation:

• The input list lst is of type list[T] (where T is the type of the elements)
• The function returns a value of type R
• For the empty list, we return a base case
• For a non-empty list, we combine the first element with the result of processing the rest

Practice with the Template

Writing a Filter Function

Design a recursive function that keeps only even numbers from a list.

Wrap-Up

• When might recursion be cleaner than using a for-loop?
• What happens if you forget the base case in a recursive function?