Recursion (from Latin recurrere, "to run back"): Self-reference; recursion occurs whenever an object either directly or indirectly ►refers to itself.
An example of recursion is the sentence "This sentence is true." Recursion can lead to strange contradictions, as you will see when you start pondering about whether the sentence "This sentence is not true" is true or not. Indirect recursion consists in a reciprocal reference of several objects, such as in the following pair: "The following sentence is true," "The previous sentence is not true." Recursive sentences sometimes have a ring of infinity about them: "'Becomes longer with each repetition' becomes longer with each repetition." And sometimes they can simply overwhelm the reader, as in "Do not read this sentence!"
But sentences are not the only objects that can be recursive. One type of infinite graphical recursion is also known as the Droste effect in honor of Droste, the Dutch brand of chocolates. Their cocoa packages display the image of a nurse who carries a cocoa package with the image of a nurse who carries a cocoa package with the image of a nurse.
The Droste Effect*
This package design has not been changed for 100 years. Its very existence, in the fast-moving world of advertising, thus has something almost ►eternal about it. However, due to the necessary miniaturizations involved, the Droste effect quickly reaches the limits of what is pictographically workable. Is it possible to achieve the same effect in a picture without miniaturization and with genuine infinity? We would tend to think that this is impossible. But ►M.C. Escher did indeed achieve this effect by distorting space into an endless spiral:
Escher, Print Gallery, 1956**
Some internet projects play with infinite self-reference. The ►Infinite Cat Project began with the image of a cat watching a computer monitor. Subsequently a visitor posted the image of her cat who watches a computer monitor showing a cat watching a computer monitor. The idea was further continued. Each visitor is asked to contribute an element to this potential infinitude by means of a monitor and a cat; meanwhile (in 2008) the project has arrived at the 1075th cat.
In programming, recursion means a ►function that repeatedly calls up itself in the computation of an intermediate or end result. Such a computer function must delimit its own repetitions by means of a truncation condition. Otherwise the result is an infinite recursion, a special case of the ►infinite loop so dreaded by programmers; when such a loop occurs, the self-repetitions of the function continue infinitely, often leading to a crashed computer.
It is not at all easy to determine whether a given truncation condition does indeed reliably break off a recursive function for any and all possible input data. As the British mathematician Alan Turing proved as early as in 1936, the accuracy of truncation conditions cannot generally be demonstrated (the halt problem). You'll find his proof under ►Infinite Loop.
* By arrangement with Droste B.V.
** All rights for all Escher graphics are owned by M.C. Escher Company B.V., http://www.mcescher.com