11.3.3 Recursion with a List

The example of a while loop that printed the elements of a list of numbers can be written recursively. Here is the code, including an expression to set the value of the variable animals to a list.

If you are reading this in Info in Emacs, you can evaluate this expression directly in Info. Otherwise, you must copy the example to the *scratch* buffer and evaluate each expression there. Use C-u C-x C-e to evaluate the (print-elements-recursively animals) expression so that the results are printed in the buffer; otherwise the Lisp interpreter will try to squeeze the results into the one line of the echo area.

Also, place your cursor immediately after the last closing parenthesis of the print-elements-recursively function, before the comment. Otherwise, the Lisp interpreter will try to evaluate the comment.

(setq animals '(gazelle giraffe lion tiger))

(defun print-elements-recursively (list)
  "Print each element of LIST on a line of its own.
Uses recursion."
  (when list                            ; do-again-test
        (print (car list))              ; body
        (print-elements-recursively     ; recursive call
         (cdr list))))                  ; next-step-expression

(print-elements-recursively animals)

The print-elements-recursively function first tests whether there is any content in the list; if there is, the function prints the first element of the list, the CAR of the list. Then the function invokes itself, but gives itself as its argument, not the whole list, but the second and subsequent elements of the list, the CDR of the list.

Put another way, if the list is not empty, the function invokes another instance of code that is similar to the initial code, but is a different thread of execution, with different arguments than the first instance.

Put in yet another way, if the list is not empty, the first robot assembles a second robot and tells it what to do; the second robot is a different individual from the first, but is the same model.

When the second evaluation occurs, the when expression is evaluated and if true, prints the first element of the list it receives as its argument (which is the second element of the original list). Then the function calls itself with the CDR of the list it is invoked with, which (the second time around) is the CDR of the CDR of the original list.

Note that although we say that the function “calls itself”, what we mean is that the Lisp interpreter assembles and instructs a new instance of the program. The new instance is a clone of the first, but is a separate individual.

Each time the function invokes itself, it does so on a shorter version of the original list. It creates a new instance that works on a shorter list.

Eventually, the function invokes itself on an empty list. It creates a new instance whose argument is nil. The conditional expression tests the value of list. Since the value of list is nil, the when expression tests false so the then-part is not evaluated. The function as a whole then returns nil.

When you evaluate the expression (print-elements-recursively animals) in the *scratch* buffer, you see this result:

gazelle

giraffe

lion

tiger
nil