2.8. Simple Recursion

We have seen how we can control whether or not expressions are evaluated with if, and, or, and cond. We can also perform an expression more than once by creating a procedure containing the expression and invoking the procedure more than once. What if we need to perform some expression repeatedly, say for all the elements of a list or all the numbers from one to ten? We can do so via recursion. Recursion is a simple concept: the application of a procedure from within that procedure. It can be tricky to master recursion at first, but once mastered it provides expressive power far beyond ordinary looping constructs.

A recursive procedure is a procedure that applies itself. Perhaps the simplest recursive procedure is the following, which we will call goodbye.

 (define goodbye   (lambda ()     (goodbye))) (goodbye) ⇒

This procedure takes no arguments and simply applies itself immediately. There is no value after the ⇒ because goodbye never returns.

Obviously, to make practical use out of a recursive procedure, we must have some way to terminate the recursion. Most recursive procedures should have at least two basic elements, a base case and a recursion step. The base case terminates the recursion, giving the value of the procedure for some base argument. The recursion step gives the value in terms of the value of the procedure applied to a different argument. In order for the recursion to terminate, the different argument must be closer to the base argument in some way.

Let's consider the problem of finding the length of a list recursively. We need a base case and a recursion step. The logical base argument for recursion on lists is nearly always the empty list. The length of the empty list is zero, so the base case should give the value zero for the empty list. In order to become closer to the empty list, the natural recursion step involves the cdr of the argument. A nonempty list is one element longer than its cdr, so the recursion step gives the value as one more than the length of the cdr of the list.

 (define length   (lambda (ls)     (if (null? ls)         0         (+ (length (cdr ls)) 1)))) (length '()) ⇒ 0 (length '(a)) ⇒ 1 (length '(a b)) ⇒ 2

The if expression asks if the list is empty. If so, the value is zero. This is the base case. If not, the value is one more than the length of the cdr of the list. This is the recursion step.

Most Scheme implementations allow you to trace the execution of a procedure to see how it operates. In Chez Scheme, for example, one way to trace a procedure is to type (trace name), where name is the name of a procedure you have defined at top level. If you trace length as defined above and pass it the argument '(a b c d), you should see something like this:

 |(length (a b c d)) | (length (b c d)) | |(length (c d)) | | (length (d)) | | |(length ()) | | |0 | | 1 | |2 | 3 |4

The indentation shows the nesting level of the recursion; the vertical lines associate applications visually with their values. Notice that on each application of length the list gets smaller until it finally reaches (). The value at () is 0, and each outer level adds 1 to arrive at the final value.

Let's write a procedure, list-copy, that returns a copy of its argument, which must be a list. That is, list-copy returns a new list consisting of the elements (but not the pairs) of the old list. Making a copy may be useful if either the original list or the copy may be altered via set-car! or set-cdr!, which we discuss later.

 (list-copy '()) ⇒ () (list-copy '(a b c)) ⇒ (a b c)

See if you can define list-copy before studying the definition below.

 (define list-copy   (lambda (ls)     (if (null? ls)         '()         (cons (car ls)               (list-copy (cdr ls))))))

The definition of list-copy is similar to the definition of length. The test in the base case is the same, (null? ls). The value in the base case is (), however, not 0, because we are building up a list, not a number. The recursive call is the same, but instead of adding one, list-copy conses the car of the list onto the value of the recursive call.

There is no reason why there cannot be more than one base case. The procedure memv takes two arguments, an object and a list. It returns the first sublist, or tail, of the list whose car is equal to the object, or #f if the object is not found in the list. The value of memv may be used as a list or as a truth value in a conditional expression.

 (define memv   (lambda (x ls)     (cond       ((null? ls) #f)       ((eqv? (car ls) x) ls)       (else (memv x (cdr ls)))))) (memv 'a '(a b b d)) ⇒ (a b b d) (memv 'b '(a b b d)) ⇒ (b b d) (memv 'c '(a b b d)) ⇒ #f (memv 'd '(a b b d)) ⇒ (d) (if (memv 'b '(a b b d))     "yes"     "no") ⇒ "yes"

Here there are two conditions to check, hence the use of cond. The first cond clause checks for the base value of (); no object is a member of (), so the answer is #f. The second clause asks if the car of the list is the object, in which case the list is returned, being the first tail whose car contains the object. The recursion step just continues down the list.

There may also be more than one recursion case. Like memv, the procedure remv defined below takes two arguments, an object and a list. It returns a new list with all occurrences of the object removed from the list.

 (define remv   (lambda (x ls)     (cond       ((null? ls) '())       ((eqv? (car ls) x) (remv x (cdr ls)))       (else (cons (car ls) (remv x (cdr ls))))))) (remv 'a '(a b b d)) ⇒ (b b d) (remv 'b '(a b b d)) ⇒ (a d) (remv 'c '(a b b d)) ⇒ (a b b d) (remv 'd '(a b b d)) ⇒ (a b b)

This definition is similar to the definition of memv above, except remv does not quit once it finds the element in the car of the list. Rather, it continues, simply ignoring the element. If the element is not found in the car of the list, remv does the same thing as list-copy above: it conses the car of the list onto the recursive value.

Up to now, the recursion has been only on the cdr of a list. It is sometimes useful, however, for a procedure to recur on the car as well as the cdr of the list. The procedure tree-copy defined below treats the structure of pairs as a tree rather than as a list, with the left subtree being the car of the pair and the right subtree being the cdr of the pair. It performs a similar operation to list-copy, building new pairs while leaving the elements (leaves) alone.

 (define tree-copy   (lambda (tr)     (if (not (pair? tr))         tr         (cons (tree-copy (car tr))               (tree-copy (cdr tr)))))) (tree-copy '((a . b) . c)) ⇒ ((a . b) . c)

The natural base argument for a tree structure is anything that is not a pair, since the recursion traverses pairs rather than lists. The recursive step in this case is doubly recursive, finding the value recursively for the car as well as the cdr of the argument.

At this point, readers who are familiar with other languages that provide special iteration constructs, e.g., while or for loops, may wonder whether similar constructs are required in Scheme. Such constructs are unnecessary; iteration in Scheme is expressed more clearly and succinctly via recursion. Recursion is more general and eliminates the need for the variable assignments required by many other languages' iteration constructs, resulting in code that is more reliable and easier to follow. Some recursion is essentially iteration and executes as such; Section 3.2 has more to say about this. Often, there is no need to make a distinction, however. Concentrate instead on writing clear, concise, and correct programs.

Before we leave the topic of recursion, let's consider a special form of repetition called mapping. Consider the following procedure, abs-all, that takes a list of numbers as input and returns a list of their absolute values.

 (define abs-all   (lambda (ls)     (if (null? ls)         '()         (cons (abs (car ls))               (abs-all (cdr ls)))))) (abs-all '(1 -2 3 -4 5 -6)) ⇒ (1 2 3 4 5 6)

This procedure forms a new list from the input list by applying the procedure abs to each element. We say that abs-all maps abs over the input list to produce the output list. Mapping a procedure over a list is a fairly common thing to do, so Scheme provides the procedure map, which maps its first argument, a procedure, over its second, a list. We can use map to define abs-all.

 (define abs-all   (lambda (ls)     (map abs ls)))

We really do not need abs-all, however, since the corresponding direct application of map is just as short and perhaps clearer.

 (map abs '(1 -2 3 -4 5 -6)) ⇒ (1 2 3 4 5 6)

Of course, we can use lambda to create the procedure argument to map, e.g., to square the elements of a list of numbers.

 (map (lambda (x) (* x x))      '(1 -3 -5 7)) ⇒ (1 9 25 49)

We can map a multiple-argument procedure over multiple lists, as in the following example.

 (map cons '(a b c) '(1 2 3)) ⇒ ((a . 1) (b . 2) (c . 3))

The lists must be of the same length, and the procedure must accept as many arguments as there are lists. Each element of the output list is the result of applying the procedure to corresponding members of the input list.

Looking at the first definition of abs-all above, you should be able to derive, before studying it, the following definition of map1, a restricted version of map that maps a one-argument procedure over a single list.

 (define map1   (lambda (p ls)     (if (null? ls)         '()         (cons (p (car ls))               (map1 p (cdr ls)))))) (map1 abs '(1 -2 3 -4 5 -6)) ⇒ (1 2 3 4 5 6)

All we have done is to replace the call to abs in abs-all with a call to the new parameter p. A definition of the more general map is given in Section 5.4.

Exercise 2.8.1.

Describe what would happen if you switched the order of the arguments to cons in the definition of tree-copy.

Exercise 2.8.2.

Consult Section 6.3 for the description of append and define a two-argument version of it. What would happen if you switched the order of the arguments in the call to append within your definition of append?

Exercise 2.8.3.

Define the procedure make-list, which takes a nonnegative integer n and an object and returns a new list, n long, each element of which is the object.

 (make-list 7 '()) ⇒ (() () () () () () ())

[Hint: The base test should be (= n 0), and the recursion step should involve (- n 1). Whereas () is the natural base case for recursion on lists, 0 is the natural base case for recursion on nonnegative integers. Similarly, subtracting 1 is the natural way to bring a nonnegative integer closer to 0.]

Exercise 2.8.4.

The procedures list-ref and list-tail return the nth element and nth tail of a list ls.

 (list-ref '(1 2 3 4) 0) ⇒ 1 (list-tail '(1 2 3 4) 0) ⇒ (1 2 3 4) (list-ref '(a short (nested) list) 2) ⇒ (nested) (list-tail '(a short (nested) list) 2) ⇒ ((nested) list)

Define both procedures.

Exercise 2.8.5.

Exercise 2.7.2 had you use length in the definition of shorter, which returns the shorter of its two list arguments, or the first if the two have the same length. Write shorter without using length. [Hint: Define a recursive helper, shorter?, and use it in place of the length comparison.]

Exercise 2.8.6.

All of the recursive procedures shown so far have been directly recursive. That is, each procedure directly applies itself to a new argument. It is also possible to write two procedures that use each other, resulting in indirect recursion. Define the procedures odd? and even?, each in terms of the other. [Hint: What should each return when its argument is 0?]

 (even? 17) ⇒ #f (odd? 17) ⇒ #t

Exercise 2.8.7.

Use map to define a procedure, transpose, that takes a list of pairs and returns a pair of lists as follows.

 (transpose '((a . 1) (b . 2) (c . 3))) ⇒ ((a b c) 1 2 3)

[Hint: ((a b c) 1 2 3) is the same as ((a b c) . (1 2 3)).]