Node:Building Robots, Next:Recursive Definition Parts, Previous:Recursion, Up:Recursion
It is sometimes helpful to think of a running program as a robot that does a job. In doing its job, a recursive function calls on a second robot to help it. The second robot is identical to the first in every way, except that the second robot helps the first and has been passed different arguments than the first.
In a recursive function, the second robot may call a third; and the third may call a fourth, and so on. Each of these is a different entity; but all are clones.
Since each robot has slightly different instructions--the arguments will differ from one robot to the next--the last robot should know when to stop.
Let's expand on the metaphor in which a computer program is a robot.
A function definition provides the blueprints for a robot. When you
install a function definition, that is, when you evaluate a
defun special form, you install the necessary equipment to
build robots. It is as if you were in a factory, setting up an
assembly line. Robots with the same name are built according to the
same blueprints. So they have, as it were, the same `model number',
but a different `serial number'.
We often say that a recursive function `calls itself'. What we mean is that the instructions in a recursive function cause the Lisp interpreter to run a different function that has the same name and does the same job as the first, but with different arguments.
It is important that the arguments differ from one instance to the next; otherwise, the process will never stop.