next up previous
Contents Next: Recursion on Nested Up: Programming Techniques Previous: A Word about

Recursion on Simple Lists

Lists are one of the basic data structures in Lisp. Very often programmers need to manipulate lists. Think of the broad possibility of operations one may want to perform on lists: counting the number of elements in a list; searching for an element in a list; removing a particular element from a list; replacing an element in a list; these represent only a small number of possibilities. All of these problems are inherently recursive. Also, their solutions all follow the same structure.

 

RULE OF THUMB 1:

When recurring on a list, do three things:

1. check for the termination condition;

2. use the first element of the list;

3. recur with the ``rest'' of the list.

 

RULE OF THUMB 2:

If a function builds a list using ``cons,'' return () at the

terminating line.

 

Example 1:

Write a function, ``remove,'' which takes a list and an element, and

returns the original list with the first occurrence of the element

removed.

To solve this problem we will have to look at each of the elements of the given list one by one, checking if it is the element to be removed. We know that we can stop searching if we
(1)
have reached the end of the list without finding the element to be removed, or
(2)
have found the element to be removed (we can stop, since we are only interested in its first occurrence).

Let's try to apply Rule of Thumb 1.
(1)
From the rule we know that at each step we want to recur with the ``rest'' of the list. Thus, at each recursive call the list will get shorter by one element. We must stop when the list becomes (). We can use the predicate ``null'' to check for this condition.

(2)
The second part states that we should try to use the first element of the list. Before each recursive call we want to check if the first element of the list equals the given element. We can use the predicate ``equal'' to test for equality.

(3)
We must remember that the function ``remove'' returns the original list with the first occurrence of the given element removed. When we recur with the ``rest'' of the list, it is important to preserve the elements that do not match the given element. Thus, in the third part, we should use ``cons'' to save these elements.

Note that we are building a list using ``cons,'' specifically a list of elements excluding the element to be removed. Using Rule of Thumb 2, we know that in such a case we should return () at the terminating line. Thus, if the test for ``null'' returns true, our function will return ().

The following solution clearly shows the three parts of Rule of Thumb 1 and also illustrates the use of Rule of Thumb 2:

      (defun remove (lst elt)
         (cond ((null lst) nil)
               ((equal (first lst) elt) (rest lst))
               (t (cons (first lst) 
                        (remove (rest lst) elt)))))
The following notation gives an idea of the execution of ``remove'':
(remove '(a 1 c 2 c 7) 'c)
        = (cons 'a (remove '(1 c 2 c 7) 'c))
        = (cons 'a (cons '1 (remove '(c 2 c 7) 'c)))
        = (cons 'a (cons '1 '(2 c 7)))
        = (cons 'a '(1 2 c 7))
        = '(a 1 2 c 7)

(remove '(a (1 q) 2) 'q)
        = (cons 'a (remove '((1 q) 2) 'q))
        = (cons 'a (cons '(1 q) (remove '(2) 'q)))
        = (cons 'a (cons '(1 q) (cons 2 (remove '() 'q))))
        = (cons 'a (cons '(1 q) (cons 2 '())))
        = (cons 'a (cons '(1 q) '(2)))
        = (cons 'a '((1 q) 2))
        = '(a (1 q) 2)
Note, Rule of Thumb 1 provides a general framework within which to think about recursion. In different examples, the importance and length of the three components may differ. In the following example the second part of the rule (using the first element of the list) comes into play only implicitly.

 

Example 2:

Write a function, ``length,'' which takes a list and returns a count of

all the top level elements in the list.

NOTE: This example illustrates that you are allowed to redefine the 'length' function that is built into Lisp. Programmer beware!!
The solution is:
      (defun length (lst)
         (cond ((null lst) 0)
               (t (+ 1 (length (rest lst))))))
We can identify the three components mentioned in Rule of Thumb 1:
(1)
We still use ``null'' to test for termination, but, since now we want to return a count of top level elements, when we reach the end of the list we return 0 (the length of a null list).
(2)
We only use the first element implicitly; we account for its presence by adding a one to the value returned by the recursive call.
(3)
We do recur with the ``rest'' of the given list. Although we do not explicitly use (first lst), the first element of the list is not forgotten; by adding a one to the result of the recursive call, we keep a track of the top level elements.

The following notation gives an idea of the execution of ``length'':
(length '(a (2 q) 64))
        = (+ 1 (length '((2 q) 64)))
        = (+ 1 (+ 1 (length '(64))))
        = (+ 1 (+ 1 (+ 1 (length '()))))
        = (+ 1 (+ 1 (+ 1 0)))
        = (+ 1 (+ 1 1))
        = (+ 1 2)
        = 3


next up previous
Contents Next: Recursion on Nested Up: Programming Techniques Previous: A Word about



© Colin Allen & Maneesh Dhagat
March 2007