Info Catalog eintr: Recursive Definition Parts eintr: Recursion eintr: Recursive triangle function

eintr: Recursion with list

 
 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
 

Info Catalog eintr: Recursive Definition Parts eintr: Recursion eintr: Recursive triangle function