16.4.7 Recursion

A function can call any function, including itself. A function that calls itself is recursive. The Common Lisp function member tests whether something is an element of a list. Here is a simplified version defined as a recursive function:

(defun our-member (obj lst)
  (if (null lst)
      nil
      (if (eql (car lst) obj)
          (our-member obj (cdr lst)))))

The predicate eql tests whether its two arguments are identical: aside from that, everything in this definition is something we have seen before.

The definition of our-member corresponds to the following English description. To test whether an object obj is a member of a list lst, we:

1. First check whether lst is empty. If it is, then obj is clearly not a member of it, and we’re done.
2. Otherwise, if obj is the first element of lst, it is a member.
3. Otherwise, obj is only a member of lst if it is a member of the rest of lst.

When you want to understand how a recursive function works, it can help to translate it into a description of this kind.