Info Catalog eintr: Building Robots eintr: Recursion eintr: Recursion with list

eintr: Recursive Definition Parts

 
 11.3.2 The Parts of a Recursive Definition
 ------------------------------------------
 
 A recursive function typically contains a conditional expression which
 has three parts:
 
   1. A true-or-false-test that determines whether the function is called
      again, here called the “do-again-test”.
 
   2. The name of the function.  When this name is called, a new instance
      of the function—a new robot, as it were—is created and told what to
      do.
 
   3. An expression that returns a different value each time the function
      is called, here called the “next-step-expression”.  Consequently,
      the argument (or arguments) passed to the new instance of the
      function will be different from that passed to the previous
      instance.  This causes the conditional expression, the
      “do-again-test”, to test false after the correct number of
      repetitions.
 
    Recursive functions can be much simpler than any other kind of
 function.  Indeed, when people first start to use them, they often look
 so mysteriously simple as to be incomprehensible.  Like riding a
 bicycle, reading a recursive function definition takes a certain knack
 which is hard at first but then seems simple.
 
    There are several different common recursive patterns.  A very simple
 pattern looks like this:
 
      (defun NAME-OF-RECURSIVE-FUNCTION (ARGUMENT-LIST)
        "DOCUMENTATION..."
        (if DO-AGAIN-TEST
          BODY...
          (NAME-OF-RECURSIVE-FUNCTION
               NEXT-STEP-EXPRESSION)))
 
    Each time a recursive function is evaluated, a new instance of it is
 created and told what to do.  The arguments tell the instance what to
 do.
 
    An argument is bound to the value of the next-step-expression.  Each
 instance runs with a different value of the next-step-expression.
 
    The value in the next-step-expression is used in the do-again-test.
 
    The value returned by the next-step-expression is passed to the new
 instance of the function, which evaluates it (or some transmogrification
 of it) to determine whether to continue or stop.  The
 next-step-expression is designed so that the do-again-test returns false
 when the function should no longer be repeated.
 
    The do-again-test is sometimes called the “stop condition”, since it
 stops the repetitions when it tests false.
 

Info Catalog eintr: Building Robots eintr: Recursion eintr: Recursion with list