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.