When a computed function (or procedure) calls itself, it is called "recursive." If the call is via one or more other functions then this group of functions are collectively called "mutually recursive." If a function were to always call itself whenever it is called, then it would never terminate. Since each call of the function requires an activation frame in the computer's memory, it would soon use up all of the computer's resources and bring it to a complete halt as well. Therefore, a recursive function first performs some test on its arguments to check for a "base case"--a condition under which it can return a value without calling itself. When it is called with higher values, then it calls itself with a lower value, and so on, until a base case is reached and values can be returned to the higher-level calling routines.

The canonical example...