ANSI Common Lisp

On the forty-second page of “ANSI Common Lisp” Lisp rockstar Paul Graham wrote (emphasis added):

This call has no effect because the list has three elements, and none of them are x. What we need here is subst, which replaces elements in a tree:

>(subst 'y 'x '(and (integerp x) (zerop (mod x 2))))
(AND (INTEGERP Y) (ZEROP (MOD Y 2)))

If we define a version of subst, it comes out looking a lot like copy-tree:

(defun our-subst (new old tree)
  (if (eql tree old)
    new
    (if (atom tree)
      tree
      (cons (our-subst new old (car tree))
        (our-subst new old (cdr tree))))))

Functions that operate on trees usually have this form, recursing down both the car and the cdr. Such functions are said to be doubly recrusive.

3.9 Understanding Recursion

Students learning about recursion are sometimes encouraged to trace all the invocations of a recursive function on a piece of paper. (A trace of a recursive function can be seen on page 288.) This exercise could be misleading: a programmer defining a recursive function usually does not think explicitly about the sequence of invocations that results from calling it.

If one always had to think of a program in such terms, recursion would be burdensome, not helpful. The advantage of recursion is precisely that it lets us view algorithms in a more abstract way. You can judge whether or not a recursive function is correct without considering all the invocations that result when the function is actually called.

To see if a recursive function does what it's supposed to, all you have to ask is, does it cover all the cases? For example, here is a recursive function for finding the length of a list:

(defun len (lst)
  (if (null lst)
    0
    (+ (len (cdr lst)) 1)))

We can assure ourselves that this function is correct by verifying two things:

1. That it works for lists of length 0.

This book is available for purchase from:

• Barnes & Noble
• Amazon.com
• Powell's Books