The Design Recipe

(defun fact (n)
  (if (zerop n)
      1
      (* n (fact (- n 1)))))

(defun fact-tr (n &optional (a 1))
  (if (zerop n)
      a
      (fact-tr (- n 1) (* n a))))

(deftype traffic-light () '(member red yellow green))

(deftype boolight-type () '(or boolean traffic-light))

(defstruct boolight-struct boolean traffic-light)

(defstruct node value left right)

(defstruct node
  (value  nil :type fixnum)
  (left   nil :type bt)
  (right  nil :type bt))

(defun max2 (m n)
  (if (> m n)
      m
      n))

(defun listmax (lon)
  "Returns the largest number in the list."
  (cond ((null lon) (error "no elements in list"))
        ((consp lon)
         (listmax-aux (rest lon) (first lon)))))

(defun listmax-aux (lon c)
  (cond ((null lon) c)
        ((consp lon)
         (listmax-aux (rest lon) (max2 c (first lon))))))

(defun listmax2 (lon)
  "Returns the largest number in the list."
  (labels ((listmax-aux (lon c)
             (cond ((null lon) c)
                   ((consp lon)
                    (listmax-aux (rest lon) (max2 c (first lon)))))))
    (cond ((null lon) (error "no elements in list"))
          ((consp lon)
           (listmax-aux (rest lon) (first lon))))))

(defun listmax3 (lon &optional c)
  "Returns the largest number in the list."
  (cond ((null lon) (or c (error "no elements in list")))
        ((consp lon)
         (listmax3 (rest lon)
                   (if c
                       (max2 c (first lon))
                       (first lon))))))

(defun listsum (lon)
  "Adds up the elements of LON."
  (cond ((null lon) 0)
        ((consp lon)
         (+ (first lon)
            (listsum (rest lon))))))

;; Binary (search) trees

(deftype bt () '(or node null))

(defstruct node
  (value nil :type fixnum)
  (left  nil :type bt)
  (right nil :type bt))

(defun bt-sum (bt)
  "Returns the sum of all the values in a BT."
  (cond ((null bt) 0)
        ((node-p bt)
         (+ (node-value bt)
            (bt-sum (node-left bt))
            (bt-sum (node-right bt))))))

(defun bt-height (bt)
  "Returns the height of the BT, i.e. the length of the longest path from the root
to a leaf."
  (cond ((null bt) 0)
        ((node-p bt)
         (+ 1 (max2 (bt-height (node-left bt))
                    (bt-height (node-right bt)))))))