Node:The stack, Next:Controlled recursion, Previous:Recursion, Up:Recursion
The stack
What happens when we run the last example program? The
black_hole function calls itself indefinitely. Each function
call uses up a small portion of the computer's memory called the
stack. Eventually all of this memory is used up, and a kind of
error called a stack overflow occurs. The program then crashes
with a Segmentation fault error.
It is sometimes helpful to think of a function as a robot that does a job. A function definition in effect provides the blueprints for a robot. When the function is executed, it is as though a robot is built on an assembly line in a robot factory. A recursive function is like a robot that builds a copy of itself on the same assembly line. The second robot is identical to the first in every way, except that it is an assistant to the first robot, and has been passed different arguments. This second robot may in turn build a copy of itself as well, and so on. It is crucial that the process of robots building robots stop at some point; otherwise, the robot factory will run out of raw materials (that is, computer memory), and the assembly line will grind to a halt.