Practice 8 — Recursion on Lists

Skills: 5

Reading: 5.3

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(empty) is 0
• my-count([list: 7]) is 1
• my-count([list: 3, 8, 5]) is 3
  • Notice: The first element is 3, and the rest is [list: 8, 5], which has count 2
  • So we can say: my-count([list: 3, 8, 5]) is 1 + my-count([list: 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(empty) is 0
• my-total([list: 6]) is 6
• my-total([list: 6, 4, 2]) is 6 + (total of [list: 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:

fun my-count(l :: List<Any>) -> Number:
  cases (List) l:
    | empty => # YOUR CODE HERE
    | link(f, r) => # YOUR CODE HERE
  end
where:
  my-count(empty) is 0
  my-count([list: 7]) is 1
  my-count([list: 3, 8, 5]) is 3
end

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:

fun function-name(l :: List<T>) -> R:
  cases (List) l:
    | empty => <base-case-expression>
    | link(first, rest) => <combine first and recursive call on rest>
  end
end

Explanation:

• The input list l 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?