Recursion

A recursive function contains code that tells itself to evaluate itself. When the function evaluates itself, it again finds the code that tells itself to evaluate itself, so the function evaluates itself again ... and again ... A recursive function will keep telling itself to evaluate itself again forever unless it is also provided with a stop condition.

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.
3. An expression that causes the conditional expression to test false after the correct number of repetitions, here called the next-step-expression.

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.

A template for a recursive function looks like this:

(defun name-of-recursive-function (argument-list)
  "documentation..."
  body...
  (if do-again-test
    (name-of-recursive-function 
         next-step-expression)))

Each time the recursive function is evaluated, an argument is bound to the value of the next-step-expression; and that value is used in the do-again-test. 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.

Go to the first, previous, next, last section, table of contents.