Recursion in plain English
Recursion is the process a procedure goes through when one of the steps of the procedure involves rerunning the procedure. A procedure that goes through recursion is said to be recursive. Something is also said to be recursive when it is the result of a recursive procedure.
To understand recursion, one must recognize the distinction between a procedure and the running of a procedure. A procedure is a set of steps that are to be taken based on a set of rules. The running of a procedure involves actually following the rules and performing the steps. An analogy might be that a procedure is like a menu in that it is the possible steps, while running a procedure is actually choosing the courses for the meal from the menu.
A procedure is recursive if one of the steps that makes up the procedure calls for a new running of the procedure. Therefore, a recursive four-course meal would be a meal in which one of the choices of appetizer, salad, entrée, or dessert was an entire meal unto itself. So a recursive meal might be potato skins, baby greens salad, chicken Parmesan, and for dessert, a four-course meal, consisting of crab cakes, Caesar salad, for an entrée, a four-course meal, and chocolate cake for dessert, so on until each of the meals within the meals is completed.
A recursive procedure must complete every one of its steps. Even if a new running is called in one of its steps, each running must run through the remaining steps. What this means is that even if the salad is an entire four-course meal unto itself, you still have to eat your entrée and dessert.
Recursive humor
A common joke is the following "definition" of recursion.[1]
- Recursion
- See "Recursion".
This is a parody on references in dictionaries, which in some cases may lead to circular definitions among related words. Jokes often have an element of wisdom, and also an element of misunderstanding. This one is also the shortest possible example of an erroneous recursive definition of an object, the error being the absence of the termination condition (or lack of the initial state, if looked at from an opposite point of view). Newcomers to recursion are often bewildered by its apparent circularity, until they learn to appreciate that a termination condition is key.
An example of this can be found by searching Google for the term.[2] Google puts the searcher in an endless cycle, of suggesting "Recursion" as the word they were trying to spell, even though this is the input they just used.
A variation on this joke is:
- Recursion
- If you still don't get it, see: "Recursion".
which actually does terminate, as soon as the reader "gets it."
