A recursive function typically contains a conditional expression which has three parts:
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.