The recursions we have seen so far have involved linear structures, that is, lists in which only the top level was involved. A second class of recursive programs operates on both halves of a CONS cell; in general, such functions call themselves twice.

; Copy a tree structure
(DEFUN COPY-TREE (X)

  (IF (CONSP X)
      (CONS (COPY-TREE (CAR X))
            (COPY-TREE (CDR X)))
      X) )


; Test equality of structure
(DEFUN EQUAL (X Y)

  (COND ((EQL X Y) T)
        ((OR (ATOM X) (ATOM Y)) NIL)
        ((EQUAL (CAR X) (CAR Y))
          (EQUAL (CDR X) (CDR Y)) )) )

Contents    Page-10    Prev    Next    Page+10    Index