A process that executes a series of operations containing that process itself as one of its own subsets. An analogy might be drawn with the Russian Matryoshka doll, in which one doll contains another doll inside of it, which contains yet another doll inside of that doll, which contains yet another doll, and so on, and so on, until there is no more space left for the next doll. Following from this analogy, the strict definition of recursion defines an operation that, in order to be completed, must call itself and use the results of that operation to complete its own task. In the looser definition, an operation calls a sub-operation — either itself or another operation — and uses the results of that operation to complete its task. The sub-operation can then again call itself or another operation, and again and again for ninstances, until a final condition or result has been met. For a better definition, see recursion.
Recursion is not limited to computer science. It is in fact often used in literature, suggesting perhaps a closer link than one might expect between computer programming and the open structure of literature. For example, Borges uses the ruse of citation in his Garden of Forking Paths in order to allude to the recursive structure of another narrative, namely his own Garden of Forking Paths :
I remembered that night which is at the middle of the Thousand and One Nights when Scheherazade (through a magical oversight of the copyist) begins to relate word for word the story of the Thousand and One Nights, establishing the risk of coming once again to the night when she must repeat it, and thus on to infinity.
– Jorge Luis Borges; The Garden of Forking Paths; 1962; pp. 25
Cinema is equally prone to recursive filmic and narrative structures. For example, in Wojiech Has’s film adaption of Jan Potocki’s The Manuscript Found in Saragossa — itself an amazing collection of recursive narrative structures — the hero of the story, one Alphonse van Worden, stumbles across a curious book of engravings:
These engravings describe scenes of hangings, of voluptuous women, and a giant lobster and a squid. As soon as the hero sees them, he knows exactly what they represent, as does the audience. For the book is in fact the story of The Manuscript Found in Saragossa itself as seen thus far, i.e. the precise story van Worden is enacting, i.e the story currently being recounted by the film Rekopis znaleziony w Saragosse.
In the story, we quickly learn that the book had accidentally been left open by Donna Rebecca Uzeda, the sister of the mysterious cabbalist, Don Pedro Uzeda, who immediately hides the volume from van Worden so as to, according to Don Pedro, avoid making the rest of his story impossible to understand.
For van Worden has accidentally stumbled onto the book of his own adventures, where he risks stumbling within that story onto the page where, as in the The Book of One Thousand and One Nights, Alphonse van Worden discovers during his journies a curious book of engravings which recount the tale of Alphone van Worden, and so on and so on.
While Rekopis znaleziony w Saragosse duplicates the literary recursive structure from the Jan Potocki novel, it also adds its own cinematographic signature via a specific form of cut: i.e. a fairly subtle combination of jump-cut followed in most instances by an identical travelling shot or some other strangely familiar framing device. This cut + camera frame/movement creates a sort of bookends-effect, which is important concept for recursion.
The principle of recursion is equally at home in mathematics, where it is most commonly associated with the concept of Set Theory. Sets are mathematical entities that contain items, and can even contain other sets, including themselves. One of the most famous and absurd recursive Set Theory examples is that of Russell’s Paradox, in which a set is defined as containing all sets that do not contain themselves. This generates an oscillation between two states (the set contains itself, the set does not contain itself) giving rise to the concept of itération (cf. Russell’s Paradox).
It can also be found in popular culture, for example in the french children’s song “mon pantalon” (Anonyme) :
mon pantalon / est décousu / si ça continue on verra le trou de / mon pantalon / est décousu / si ça continue on verra le trou de / mon pantalon / … /
my pants / have got a rip / and if it goes on like this you’ll soon be looking at the the crack of / my pants / have got a rip / and if it goes on like this you’ll soon see the crack of / my pants / … /
– Anonyme
Another famous use of recursion, and inspired by its mathematical incantation, comes from Noam Chomsky’s theory of generative grammar.
A system of propositions expressing the meaning of a sentence is produced in the mind as the sentence is realized as a physical signal, the two being related by certain formal operations that, in current terminology, we may call grammatical transformations. Continuing with current terminology, we may thus distinguish the surface structure of the sentence, the organization into categories and phrases that is directly associated with the physical signal, from the underlying deep structure, also a system of categories and phrases, but with a more abstract caracter. Thus, the surface structure of the sentence “A wise man is honest” might analyze it into the subject “a wise man” and the predicate “is honest.” The deep structure, however, will be rather different. It will, in particular, extract from the complex idea that constitutes the subject of the surface structure an underlying proposition with the subject “man” and the predicate “be wise”. In fact, the deep structure, in the traditional view, is a system of two propositions, neither of which is asserted, but which interrelate in such a way as to express the meaning of the sentence “A wise man is honest.” We might represent the deep structure in this sample case by formula 1, and the surface structure by formula 2, where paired brackets are labeled to show the category of phrase that they bound. (Many details are omitted.)
An alternative and equivalent notation, widely used, expressed the labeled bracketing of 1 and 2 in tree form, as 1’ and 2’ respectively:
If we understand the relation “subject-of” to hold between a phrase of the category noun phrase (NP) and the sentence (S) that directly dominates it, and the relation of “predicate-of” to hold between a phrase of the category verb phrase (VP) and the sentence that directly dominates it, then structures 1 and 2 (equivalently, 1’ and 2’) specify the grammatical functions of subject and predicate in the intended way. The grammatical function of the deep structure (1) play a central role in determining the meaning of the sentence. The phrase structure indicated in 2, on the other hand, is closely related to its phonetic shape — specifically, it determines the intonation contour of the utterance represented.
– Noam Chomsky; Language and Mind; 1968; pp. 25
In the Chomsky model of linguistics, grammar (an innate quality, built into the genetic heritage of the human being) generates deep meaning through recursive structures where each item within the grammatical tree can recursively, and at any moment, represent a more specific subset of meanings. In the above sentence “wise” is in reality an umbrella for the idea “man is wise” which can further be broken down into the ideas “man” and “is wise”. The complexity of the entire sentence can be treated with a fairly limited set of rules and yet generate an infinite variety of meanings (cf. generative). Humans do not have to learn all of the possible permutations of a given language, they simply need to understand these recursive patterns. Once you’ve understood that an item can be better understood by investigating its sub-items, and that those sub-items can in turn be further specialized, you basically have the grasp of any possible utterance.
The validity of Chomsky’s theory is of course of no importance here; what interests us instead is the structure he proposes itself, and most importantly the manner in which it allows for extremely complex operations with a minimum of basic operations. Additionally, it creates an interesting model in which one can access the tree at the lowest, specific level, at the highest, abstract level, or at some intermediate level in-between. For it is this latter aspect, the way in which the concept of recursion allows us to access complex structures at various levels, which leads us into one of the fundamental aspects of computer operation. And finally, recursion becomes not only a form of looping the program onto itself, a kind of cosmic joke as in The Book of One Thousand and One Nights, but instead as a process of investigating deeper and deeper into an object in order to continue the process by using only a limited set of basic rules. This is the point at which we move from a strict looping definition of recursion, to a generative and pragmatic definition of smaller pieces generating results for the whole.
Recursion is at work in almost all aspects of modern computer operation. At the lowest levels of the tree are the base zeroes and ones flowing through the circuitry. But those zeroes and ones are in fact organized at a “higher” level (in following the Chomsky model), passing through various algorithms in which certain zeroes and ones will lead to one series of subsequent operations, whereas other zeroes and ones will lead to an entirely different series. These algorithms can then lead to families of algorithms, that can in turn be placed in a “higher” series of algorithms (algorithm A -> algorithm B -> algorithm C). These groups can then be placed into larger groups, for example an entire family of sub-algorithms dealing with printing a pixel onto a monitor, or another family of algorithms dealing with printing a pixel onto a piece of paper. Rather than requiring the user to determine the details of how each sub-operation is done, instead she or he simply types or clicks on “print” and the computer distributes all of the sub-operations to each individual program or even circuit or peripheral which in turn redistributes to other circuits or internal sub-operators, and so on. Starting from a virtual button inside of a Graphical User Interface (GUI) an entire army of operations and sub-operations are invoked, with a gigantic tree of delegations taking place, all the way down to the final leaves of each branch where a simple zero flickers into a one, or a bit of electricity turns a motor on or sprays a bit of ink. All of these different levels of recursion define degrees of abstraction and specificity, different points-of-view at which the user or the program can access and manipulate the machine.
One of the most elegeant operating systems — the system formerly known as NEXTStep and now rebaptized Apple Mac OS X — is an excellent example of this process of delegation of complexity to lower and lower eschelons of specificity, as can be seen in the following diagram of just a portion of the NEXTStep inspired family of operations, otherwise known as Cocoa.
Each of the above items (cf. object) in this diagram represent a class, which in common language represents a series of I-know-how-to-do-somethings, a certain know-how, for example displaying an alert to a user: “Are you really sure you want to delete your entire hard drive?”. These classes are used to build objects, which is just a fancy name for things that know how to do stuff. In Mac OS X, windows, buttons, text fields, scrollbars, menus, and so on are all objects, and can be described in the above diagram. They represent the official Macintosh graphical user interface (cf. GUI).
While this diagram describes wholly different entities of know-how, each entity — each class — builds up from the previous class hierarchically, using a process of recursion similar to the Chomsky model of generative grammar, albeit in reverse. When an object doesn’t know how to do something, it just looks back up the recursion tree to see if it’s containing class knows how to do what is asked of it. The details of this process are not important here, and can be learned through any book on Cocoa Programming. What is important is how the structure of recursion can be used to simplify complex processes.
Although the above Cocoa diagram prides itself on having very few levels of what are named sub-classes, in reality what we see here are only the “public” algorithms with their “public” nominations. In reality, each sub-section has literally hundreds, even thousands of delegated operations, all the way down to each instruction sent to specific pins on some specific chip situated on the computer’s motherboard. The “sophisticated” aspect of this design comes from the ability of the computer programmer to invoke one or several of these “classes” of instructions (open a window, create a text document, save a file, draw a line, make a noise, etc) without having to know exactly how NEXT/Apple programmed each of the classes, nor how the hardware does what it does with these instructions in order to make them operational.
Even the material configuration of the computer shows massive levels of hierarchization, whereby instructions are sent to individual chips soldered onto the motherboard: “hey you, the graphics card, can you print me up this visual display image?”, “hey, memory bank number 1, can you retrieve for me whatever is sitting at address x05ae2001f?”
In the purely strict, computer science definition of recursion, such as the one we began with at the opening of this entry, we ought only speak of recursion if and only if each class or each operation calls itself, leading us back to The Book of One Thousand and One Nights (cf. Claygrid, arborescence). A famous example of this is illustrated in the algorithm entitled the Tower of Hanoi. And yet from a certain point of view, even from a technical standpoint, the computer is always operating on a basic set of standard operations: read memory value, compare or calculate that value with another value at another memory location, store the result of that operation in a third memory location, jump to a new section of the program based on the value at the latter location, and so on. As the program jumps further and further to new points, it keeps adding operations onto the stack. As such, recursion becomes more of a functionalrecursion rather than a strict circular, looping one, as the results of each sub-operation must be calculated before the results of the encompassing operation can be complete — taking us back to the figure of the Russian Matryoshka doll.
