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 0 as the base case, for lists the most common base case is null. With 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:

  1. Be very optimistic! Since lists themselves are recursive data structures, most problems involving lists can be solved with recursive procedures.

  2. 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.

  3. 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.

  4. 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.