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...