GNU Info

(emacs-lisp-intro.info)Recursive Definition Parts

---

Next: Recursion with list Prev: Building Robots Up: Recursion

---

Enter node , (file) or (file)node

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.