Recitation 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 0my-count([list: 7])
is 1my-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])
is1 + my-count([list: 8, 5])
- Notice: The first element is 3, and the rest is
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 0my-total([list: 6])
is 6my-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 typeList<T>
(whereT
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?