5.4 List procedures
Since the List data structure is defined recursively, it is natural to
define recursive procedures to examine and manipulate lists. Whereas
most recursive procedures on inputs that are Numbers usually used
the base case, for lists the most common base case is
numbers, we make progress by subtracting
1; with lists, we make
progress by using
cdr to reduce the length of the input List by one
element for each recursive application. This means we often break
problems involving Lists into figuring out what to do with the first
element of the List and the result of applying the recursive procedure
to the rest of the List.
We can specialize our general problem solving strategy from Chapter 3 for procedures involving lists:
Be very optimistic! Since lists themselves are recursive data structures, most problems involving lists can be solved with recursive procedures.
Think of the simplest version of the problem, something you can already solve. This is the base case. For lists, this is usually the empty list.
Consider how you would solve a big version of the problem by using the result for a slightly smaller version of the problem. This is the recursive case. For lists, the smaller version of the problem is usually the rest (
cdr) of the List.
Combine the base case and the recursive case to solve the problem.
Next we consider procedures that examine lists by walking through their elements and producing a scalar value.Section 5.4.2 generalizes these procedures. In Section 5.4.3, we explore procedures that output lists.