Recursive Skeletons

Summary

We develop techniques for implementing recursive functions starting with a simple skeleton for recursion over lists. We also introduce pattern matching as an elegant way of capturing case analysis on the shape of data.

So far we have studied a low-level, operational perspective on recursion. This perspective, powered by our mental model of computation, allows us to understand how recursion definitions operate. However, knowing how recursion works and being able to trace code execution is decidedly different from designing recursive functions which requires us to (a) solve a problem in a recursive manner and (b) translate that solution into a recursive function. We’ll tackle both these problems in this reading by developing a simple template or skeleton for recursive functions over lists.

The Components of a Recursive Function

Recall the code for recursively computing the sum of a list from the previous reading:

;;; (sum numbers) -> integer?
;;;    numbers : listof integer?
;;;
;;; Returns the sum of the numbers.
(define sum
  (lambda (numbers)
    (if (null? numbers)
        0
        (+ (car numbers) (sum (cdr numbers))))))

In the reading, we gave a recursive definition of a list. A list is either:

• Empty (or null), or
• Non-empty, consisting of a head element (retrieved with car) and its tail, the rest of the list (retrieved with cdr).

Note that every list is covered by this definition because every list is either empty or non-empty. Furthermore, note that this definition is recursive because in the non-empty case, we have a (smaller) occurrence of a list, the thing that we are defining! Because of this, we call the empty case the base case since it contains no occurrences of lists. The non-empty case is called the recursive case precisely because it contains a recursive occurrence of a list.

Because we have defined our data, a list, to be drawn from a finite set of cases, operations over that data can be defined in terms of case analysis over these possibilities. In other words, the definition of sum mirrors the recursive definition of a list.

• In the case where the list is empty, there are no numbers to add, so the sum is 0.
• In the case where the list is non-empty, the sum of the numbers can be expressed as the result of adding (a) the head element and (b) the sum of the rest of the list.

The implementation of sum expresses this decomposition precisely:

• In the base case (numbers is null), we return 0.
• In the recursive case, the result is the head of the list ((car numbers)) plus the sum of the rest of the list ((sum (cdr numbers))).

How do we know that (sum (cdr numbers)) produces the sum of the rest of the list? We saw with our mental model of computation that the call indeed works, but checking it over and over again with our mental model is burdensome. Instead, from a design perspective, we’re going to assume that a recursive function call to the tail of the list produces the intended result. This is called our recursive assumption and is the cornerstone of our decomposition using recursion.

An Recursive Skeleton for Lists

In summary, when we perform recursive decomposition for a problem involving lists, we decompose the problem into two cases based on the recursive definition of lists:

• We solve the problem in the case where the list is empty, the base case.
• We solve the problem in the case where the list is non-empty, the recursive case.

In the non-empty case, we know that, by virtue of the non-emptiness of list, we can use car and cdr to retrieve the head and tail of the list, respectively. Furthermore, our recursive assumption tells us that we can call the recursive function on the tail of the list and get back a correct value.

Translating this pattern into Racket code is straightforward and gives us a basic recursive skeleton for lists to work with:

(define my-recursive-function
  (lambda (l)
    (if (null? l)
        ; The base case
        ; The recursive case
        )))

Because we frequently use the head and tail of the list extensively in the recursive case, we can also use let-bindings to avoid excessive nesting of function applications:

(define my-recursive-function
  (lambda (l)
    (if (null? l)
      ; The base case
      (let ([head (car l)]
            [tail (cdr l)])
           ; The recursive case
           ))))

Let’s apply this template to build a basic recursive function: recursively computing the length of the list. However, let’s not jump into code just yet. Let’s first write out the recursive decomposition and come up with an algorithm for recursively computing the length of a list. And then we’ll translate that algorithm into code.

Our recursive template tells us that we should proceed by case analysis on the list. So we have two sub-problems to solve:

• The base case: compute the length of a list that is empty.
• The recursive case: compute the length of a list that is non-empty.

The base case is straightforward: the length of an empty list is zero. In general, we will find the base case to be straightforward to solve.

In the recursive case, we know the list is non-empty. Therefore, there is a head element and a corresponding tail of the list. Furthermore, our recursive assumption tells us that we can compute the length of the tail of the list.

How do we proceed from here? A picture is very helpful for understanding our options. In the recursive case, we know the list has the following shape:

The list has been decomposed into a head element and a tail that represents the unknown part of the list. What is the length of this list? From the physical layout of the list, we can further decompose the problem into two parts:

• The contribution of head to the list’s length: each element contributes 1 to the overall length, so this value is 1.
• The contribution of tail to the list’s length: this is precisely what we assumed we could compute with our recursive assumption!

And our intuition about length tells us that the length of the overall list is the sum of these two expressions. Graphically, this would look as follows:

With our algorithm complete, we can now translate it into Racket code. We’ll use the let version of the skeleton to illustrate its usage:

;;; (length lst) -> exact-nonnegative-integer?
;;;    lst : list?
;;;
;;; Returns the length of lst.
(define length
  (lambda (lst)
    (if (null? lst)
        0
        (let ([head (car lst)]
              [tail (cdr lst)])
             (+ 1 (length tail))))))

Recall that one of our design goals is to write programs that are correct from inspection. In particular, when we have a recursive design, we want our code to look like that design. Let’s see how our definition of length fares in this respect Below, we have replicated the definition of length with the recursive design in-lined in comments:

(define length
  (lambda (lst)
    (if (null? lst)                   ; A list is either empty or non-empty.
        0                             ; + The empty list has zero length.
        (let ([head (car lst)]        ; + A non-empty list has a head and tail
              [tail (cdr lst)])       ; element.
             (+ 1 (length tail))))))  ;   The length of a non-empty list is one
                                      ;   plus the length of the tail.

Not too bad! Like our design, the code is clearly conditioned on whether lst is empty or non-empty. Furthermore, the results of the cases clearly implement the cases of our design, so we can believe our implementation is correct as long as we believe our design is correct.

Self Checks

Check 1: Try On A Skeleton (‡)

Apply this recursive template for lists to begin writing a recursive implementation for (list-contains v l) that takes a value v and a list l and returns #t if and only if v is an element of l. In a comment, explicitly write out your recursive decomposition of this function similarly to how we derived length above. Remember to solve the problem for both the base case and recursive case!