next up previous
Contents Next: Recursion on Numbers Up: Programming Techniques Previous: Recursion on Simple

Recursion on Nested Lists and Expressions

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 't if it finds the atom within the nested list and returns nil

otherwise.

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 above translates into the following simple piece of code:
          (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)))))
The following notation gives an idea of the execution of ``search'':
(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
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.

 

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.

 

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

return 40.

Let us again try to identify the three elements of the previous Rule of Thumb:
(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.

The above translates into the following simple piece of code:
        (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))))))
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'':
(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


next up previous
Contents Next: Recursion on Numbers Up: Programming Techniques Previous: Recursion on Simple



© Colin Allen & Maneesh Dhagat
November 1999