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.

(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).

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

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)))))

(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)

 
Example 2:

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

  all the top level elements in the list.

      (defun length (lst)
         (cond ((null lst) 0)
               (t (+ 1 (length (rest lst))))))

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

(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