What Is Recursion?

In 1637, the French philosopher R né Descartes wrote the immortal line "Je pense, donc je suis." Curiously, this is usually rendered in Latin, as Cogito, ergo sum, and is translated in English as "I think, therefore I am." In making this statement, Descartes was not merely thinking, he was thinking about thinking, which led him to the conclusion that he existed. The recursive nature of Descartes's insight is perhaps better rendered in the version offered by Ambrose Bierce in The Devil's Dictionary: Cogito cogito ergo cogito sum—"I think I think, therefore I think I am." Descartes himself, though, was more prone to doubt, and expanded his dictum as "Je doute, donc je pense, donc je suis"—"I doubt, therefore I think, therefore I am." He thus concluded that even if he doubted, someone or something must be doing the doubting, so the very fact that he doubted proved his existence. This probably came as a relief to his friends.

In this book, I examine the more general role of recursion in our mental lives, and argue that it is the primary characteristic that distinguishes the human mind from that of other animals. It underlies our ability not only to reflect upon our own minds, but also to simulate the minds of others. It allows us to travel mentally in time, inserting consciousness of the past or future into present consciousness. Recursion is also the main ingredient distinguishing human language from all other forms of animal communication.

Recursion, though, is a fairly elusive concept, often used in slightly different ways. Before I delve into some of the complexities, let's consider some further examples to give the general idea. First, then, a not-too-serious dictionary definition:

Recursion (ri-kûr'-zhen) noun. See recursion.

One problem here, of course, is that this implies an infinite loop, from which you may never escape in order to read the other stuff in this book. The following variant suggests a way out:

Recursion (ri-kûr'-zhen) noun. If you still don't get it, see recursion.

This banks on the possibility that if you do get it after a round or two, you can escape and move on. If you don't, well I'm sorry.

The postmodern novelist John Barth concocted what is probably both the shortest and the longest story ever written, called Frame-Tale. It can be reproduced as follows: Write the sentence ONCE UPON A TIME THERE on one side of a strip of paper, and WAS A STORY THAT BEGAN on the other side. Then twist one end once and attach it to the other end, to form a Mobius strip. As you work your way round the strip, the story goes on forever.

A similar example comes from an anonymous parody of the first line of Bulwer-Lytton's infamous novel, Paul Clifford:

It was a dark and stormy night, and we said to the captain, "Tell us a story!" And this is the story the captain told: "It was a dark and stormy night, and we said to the captain, 'Tell us a story!' And this is the story the captain told: 'It was a dark ...'"

Another amusing example is provided by a competition, run by The Spectator magazine, which asked readers to state what they would most like to read on opening the morning paper. The winning entry read as follows:

Our Second Competition

The First Prize in the second of this year's competitions goes to Mr Arthur Robinson, whose witty entry was easily the best of those we received. His choice of what he would like to read when opening the paper was headed, "Our Second Competition," and was as follows: "The First prize in the second of this year's competitions goes to Mr Arthur Robinson, whose witty entry was easily the best of those we received. His choice of what he would like to read when opening the paper was headed 'Our Second Competition,' but owing to paper restrictions we cannot print all of it."

Taking a different tack, John Barth's story Autobiography: A Self-recorded Fiction is a recursive tale in which the narrator is ostensibly the story itself, writing about itself. It ends, recursively, in its own end:

Nonsense, I'll mutter to the end, one word after another, string the rascals out, mad or not, heard or not, my last words will be my last words.

To my knowledge, no story has yet attempted to write a story of a story that writes about itself.

And then there is the recurring problem of fleas, as penned by the Victorian mathematician Augustus de Morgan:

Great fleas have little fleas upon their backs to bite 'em, And little fleas have smaller fleas, and so ad infinitum. And the great fleas themselves, in turn, have greater fleas to go on, While these again have greater still, and greater still, and so on.

This notion of inserting progressively smaller entities into larger ones ad infinitum can also give rise to interesting visual effects, as in the examples shown in figure 2.

The use of recursion to create infinite sequences is also exploited by mathematics. One such sequence is the set of natural (i.e. whole) numbers, which I'll write as N. Thus we can generate all of the positive natural numbers by the definitions

1 is in N

If n is in N then (n + 1) is in N.

This second definition is recursive, because N appears in the condition that needs to be satisfied for N.

You may remember, possibly from schooldays, what factorials are. As a schoolboy I found them amusing in a childish kind of way, because they were signaled with exclamation marks; thus factorial 3, usually written 3!, is 3 * 2 * 1, and equals 6.5 Similarly, we can compute the following:

5! = 5 * 4 * 3 * 2 * 1 = 120

8! = 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 40,320

Clearly, this can go on forever, but we can capture the entire set by using just two defining equations:

0! = 1

n! = n * (n - 1)! [where n > 0].

This second equation is recursive in that a factorial is defined in terms of a factorial. We need the first equation to kick the thing off.

The next example is for rabbits, and is called the Fibonacci series, defined by the following three equations:

fibonacci(0) = 1
fibonacci(1) = 1
fibonacci(n) = fibonacci(n - 1) + fibonacci (n - 2)
[where n > 1].

If you are following me, you should be able to compute the series, which goes 1, 1, 2, 3, 5, 8, 13, ... What the definition says, then, is that each number in the series is the sum of the two previous ones. Why rabbits? Fibonacci (c. 1170–1250) was an Italian mathematician who used the series to predict the growth of a hypothetical population of rabbits.

For a final informal example, I take you to Kyoto, Japan, where I once happened upon a sign on a gate that was written in Kanji script. I asked what it meant, and my guide told me, I hope correctly, that it meant Post no bills. There is a paradox here in that the sign was itself a bill, thereby contravening its own presence. Perhaps there needed to be another sign that said Post no "Post no bills" bills. But of course this is itself in violation of its own message, so we might envisage another sign that reads Post no 'Post "Post no bills" bills' bills. There is no end to this process, so it might have been more sensible to have allowed bills on the gate in the first place. In practice, though, limitations of time, space, or memory will prevent a recursive sequence of structure continuing forever.

Toward a Working Definition

One of the characteristics of recursion, then, is that it can takes its own output as the next input, a loop that can be extended indefinitely to create sequences or structures of unbounded length or complexity. In practice, of course, we do not get caught up in infinite loops—life is simply too short for that. For the purposes of this book, then, we shall not be interested so much in the generation of infinite sequences as in a definition that might apply usefully to human thought. A definition that meets this requirement is suggested by Steven Pinker and Ray Jackendoff, who define recursion as "a procedure that calls itself, or ... a constituent that contains a constituent of the same kind."

The second part of this definition is important, especially in language, because it allows that recursive constructions need not involve the embedding of the same constituents, as in the example of the gate in Kyoto, but may contain constituents of the same kind—a process sometimes known as "self-similar embedding." For example, noun phrases can be built from noun phrases in recursive fashion. Tecumseh Fitch gives the example of simple noun phrases such as the dog, the cat, the tree, the lake, and one can then create new noun phrases by placing the word beside between any pair: the dog beside the tree, the cat beside the lake. Or one might have two sentences: Jane loves John and Jane flies airplanes, and embed one in the other (with appropriate modification) as Jane, who flies airplanes, loves John. These can be extended recursively to whatever level of complexity is desired. For example we could extend the noun phrase to the dog beside the tree beside the lake, or the sentence about Jane and John to Jane who flies airplanes that exceed the sound barrier loves John, who is prone to self-doubt. Most languages make use of recursive operations of this sort—although we shall see in the next chapter that there may be a few languages that don't operate in this way.

Although it is common to provide illustrations from language, the main theme of this book is that it is in thought rather than in language that recursion originates. As Pinker and Jackendoff put it, "The only reason language needs to be recursive is because its function is to express recursive thoughts. If there were not any recursive thoughts, the means of expression would not need recursion either." In remembering episodes from the past, for instance, we essentially insert sequences of past consciousness into present consciousness, or in our interactions with other people we may insert what they are thinking into our own thinking. These themes are explored in later chapters.

Process and Structure

As suggested by Pinker and Jackendoff's dual definition, recursion can be understood either as a process or as a structure. The distinction can be important. A recursive process may lead to a structure that need not be seen as itself recursive. For example, suppose we construct a sequence of musical notes with an embedding routine by pairing pairs of notes, each consisting of a randomly chosen note played on a piano with a randomly chosen note played on a violin. The first pair is embedded in another pair, and the four-note output then embedded in another pair. This process can be continued indefinitely to create a sequence of notes. As illustrated in figure 3, though, the sequence can be interpreted, not as a recursively embedded structure, but as a sequence of piano notes followed by an equally long sequence of violin notes. This failure to distinguish recursive embedding from recursive structure has led to some confusion, especially in claims about recursion in nonhuman species.

Again, in his most recent theory on the nature of language, known as the Minimalist Program, Noam Chomsky has argued that human thought is generated by a Merge operation, applied recursively. That is, units are merged to form larger entities, and the merged entities can be themselves merged to form still larger entities, and so on. This operation underlies the embedded structure of human language, although in Chomsky's theory it applies strictly to what he calls I-language, which is the thought process preceding E-language, the external language that is actually spoken or signed. Merge can produce strings of elements, be they words or elements of thought, and although it may be applied recursively to produce hierarchical structure, that structure may not be evident in the final output. For instance, even sentences might be regarded simply as words all merged in unstructured sequence, as in ritualized songs or prayers. Everyday language, too, may include mentally undifferentiated clichés and slogans, or sequences that are highly automated. Politicians may be especially prone to this kind of talk.

As noted above, recursive processes and structures can in principle extend without limit, but are limited in practice. Nevertheless recursion does give rise to the concept of infinity, itself perhaps limited to the human imagination. After all, only humans have acquired the ability to count indefinitely, and to understand the nature of infinite series, whereas other species can at best merely estimate quantity, and are accurate only up to some small finite number. Even in language, we understand that a sentence can in principle be extended indefinitely, even though in practice it cannot be—although the novelist Henry James had a damn good try. Such understandings are indeed part of human mental achievement, and depend on a human capacity for recursive thought. Nevertheless they are not the primary concerns of this book.

The appealing aspect of recursion is precisely that it can in principle extend indefinitely to create thoughts (and sentences) of whatever complexity is required. The idea has an elegant simplicity, giving rise to what Chomsky called "discrete infinity," or Wilhelm Humboldt (1767–1835) famously called "the infinite use of finite means." And although recursion is limited in practice, we can nevertheless achieve considerable depths of recursive thought, arguably unsurpassed in any other species. In chess, for example, a player may be able to think recursively three or four steps ahead, examining possible moves and countermoves, but the number of possibilities soon multiplies beyond the capacity of the mind to hold them.

Deeper levels of recursion may be possible with the aid of writing, or simply with extended time for rehearsal and contemplation, or extended memory capacity through artificial means. The slow development of a complex mathematical proof, for example, may require subtheorems within subtheorems. Plays or novels may involve recursive loops that build slowly—in Shakespeare's Twelfth Night, for example, Maria foresees that Sir Toby will eagerly anticipate that Olivia will judge Malvolio absurdly impertinent to suppose that she wishes him to regard himself as her preferred suitor. As in fiction, so in life; we all live in a web of complex recursive relationships, and planning a dinner party may need careful attention to who thinks what of whom.

The structures resulting from recursive processes need not reveal the nature of those processes, just as a loaf of bread may not reveal the processes of kneading that went into the making of the bread, or the taste of wine the picking and trampling of the grapes. Often, though, the structure of a sentence or stream of thought may reveal recursive embedding—interpretation of a sentence may require the understanding of phrases embedded in phrases, regardless of how the embedding was actually accomplished, and an internal understanding of a stream of thought may require the segmentation of episodes within episodes.

What Recursion Is Not

Recursion is not the only device for creating sequences or structures of potentially infinite length or size. I now consider some examples that do not meet the criteria for recursion.

Repetition

Simple repetition can lead to sequences of potentially infinite length, but does not classify as true recursion. For example, the sentence that opens chapter 9 of A. A. Milne's Winnie the Pooh goes It rained and it rained and it rained. This could go on forever—or at least until Piglet is drowned—but the repetition simply conveys the information that it rained rather a lot, causing Piglet some ennui. It is not recursive because each addition of and it rained is not driven by the previous one; it is simply added at the discretion of the writer.

In any event, repetition does not distinguish human activity from that of nonhuman animals. Birdsong, for example, is relentlessly repetitive, but each repeated theme does not embellish or qualify the previous one. At most, the repetition might signal urgency, or simply signal continuing presence, as one might repeatedly knock on a door in the hope of arousing someone inside. Repetition is ubiquitous in human and animal life, in activities ranging from the repeated jaw movements in eating, to the curiously repetitive nature of sexual activity. The spider, no less, is capable of repetition, as in Walt Whitman's Leaves of Grass:

A NOISELESS, patient spider I mark'd, where, on a little promontory, it stood, isolated; Mark'd how, to explore the vacant, vast surrounding, It launch'd forth filament, filament, filament, out of itself; Ever unreeling them—ever tirelessly speeding them