Node:Recursion with list, Next:Recursive triangle function, Previous:Recursive Definition Parts, Up:Recursion
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