GNU Info

(emacs-lisp-intro.info)Recursion with list

---

Next: Recursive triangle function Prev: Recursive Definition Parts Up: Recursion

---

Enter node , (file) or (file)node

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 using Emacs 20 or before, this example must be copied to
the `*scratch*' buffer and each expression must be evaluated 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.

   If you are using Emacs 21 or later, you can evaluate this expression
directly in Info.

     (setq animals '(gazelle giraffe lion tiger))
     
     (defun print-elements-recursively (list)
       "Print each element of LIST on a line of its own.
     Uses recursion."
       (if list                              ; do-again-test
           (progn
             (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
assemblies 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 `if' 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 invokes itself 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
`if' expression tests false so the then-part is not evaluated.  The
function as a whole then returns `nil'.

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

     giraffe
     
     gazelle
     
     lion
     
     tiger
     nil