So far we have worked only with simple lists. These are lists for which the top-level elements are our only concern. For example, given the list '(1 a (5 g) up), the top-level elements are: 1, a, (5 g), and up. But often we are interested in looking deeper than just the top-level. A nested list consists of atoms and lists; the latter may themselves be nested. Searching, deleting, inserting, replacing atoms in a multi-level list, or evaluating arbitrarily complex mathematical expressions are all naturally recursive problems on nested lists. Such recursion is slightly more complicated than recursion on simple lists, but it again follows a common, general structure.

RULE OF THUMB 3:When recurring on a nested list, do three things:

1. check for the termination condition;

2. check if the first element of the list is an atom or a list;

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

Example 3:Write a function, ``search,'' which takes a nested list and an atom, and

it returns

'tif it finds the atom within the nested list and returnsnilotherwise.

To write this function, let's take the steps recommended by Rule of Thumb 3:

- (1)
- We will move through the list one element at a time and if we reach the end without finding the given atom, we will return (). To check for termination we can use the predicate ``null.''
- (2)
- At each step we will look at the first element of the list; if it
is an atom we will check if it equals the given atom. If they
match, we can return
`'t`

immediately, else we go on with the search in the rest of the list. We can use the predicate ``atom'' to check if the first element is an atom. We can use ``equal'' to test for equality. - (3)
- Lastly, if we discover that the first element is a list, we may
need to perform two searches: the first within the nested list
represented by the first element; the second within the ``rest'' of
the original list. If the result of either of these searches is
't, the overall result is also true. We can use the logical
function ``or'' to get this effect.

The following notation gives an idea of the execution of ``search'':(defun search (lst elt) (cond ((null lst) nil) ((atom (first lst)) (if (equal (first lst) elt) 't (search (rest lst) elt))) (t (or (search (first lst) elt) (search (rest lst) elt)))))

Note that ``or'' only needs to evaluate upto the first non-nil argument to return true. Similarly, ``and'' only needs to evaluate upto the first nil argument to return nil. Another interesting application of recursion is the evaluation of mathematical or logical expressions.(search '(a (1 c) 2 7) 'c) = (search '((1 c) 2 7) 'c) = (or (search '(1 c) 'c) (search '(2 7) 'c)) = (or (search '(c) 'c) (search '(2 7) 'c)) = (or 't (search '(2 7) 'c)) = 't

RULE OF THUMB 4:When evaluating an expression, do three things:

1. check for the termination condition;

2. identify operator;

3. apply operator to recursive calls on the operands.

**
**

Let us again try to identify the three elements of the previous Rule of Thumb:

Example 4:Write a function, ``evaluate,'' which takes a prefix expression represented

as a nested list and returns the numerical value represented by the

expression. Only +, -, and * may be used as operators and each operator

can have only two operands. Thus,

(evaluate '(* (+ 4 6) 4)shouldreturn 40.

- (1)
- Note that we are no longer working with a list of elements. The argument of ``evaluate'' represents an expression. If this argument is a list we know that it will have three parts: an operator, the first operand sub-expression, the second operand sub-expression. In this case, we will need to further evaluate the operands. If the argument is a number, we can stop. We can use the predicate ``numberp'' to test for a numerical value.
- (2)
- We can identify the first element of the argument list as the operator. For each operator we will need to apply a different function.
- (3)
- For each possible operator we will recursively call evaluate on
the first and second operands.

Since there are only three possible operators, we can use the default case for *. The following notation gives an idea of the execution of ``evaluate'':(defun evaluate (expr) (cond ((numberp expr) expr) ((equal (first expr) '+) (+ (evaluate (second expr)) (evaluate (third expr)))) ((equal (first expr) '-) (- (evaluate (second expr)) (evaluate (third expr)))) (t (* (evaluate (second expr)) (evaluate (third expr))))))

(evaluate '(* (+ 6 3) (- (+ -1 2) 3)) = (* (evaluate '(+ 6 3)) (evaluate '(- (+ -1 2) 3))) = (* (+ (evaluate 6) (evaluate 3)) (evaluate '(- (+ -1 2) 3))) = (* (+ 6 (evaluate 3)) (evaluate '(- (+ -1 2) 3))) = (* (+ 6 3) (evaluate '(- (+ -1 2) 3))) = (* 9 (evaluate '(- (+ -1 2) 3))) = (* 9 (- (evaluate '(+ -1 2)) (evaluate 3))) = (* 9 (- (+ (evaluate -1) (evaluate 2)) (evaluate 3))) = (* 9 (- (+ -1 (evaluate 2)) (evaluate 3))) = (* 9 (- (+ -1 2) (evaluate 3))) = (* 9 (- 1 (evaluate 3))) = (* 9 (- 1 3)) = (* 9 -2) = -18

November 1999