Do you think I believe you hope…? The limits of recursion


In Slavic villages, when a young girl wanted to know what her future husband would look like, she would go to a dark, dark barn in the middle of the night, put two mirrors facing each other and light two candles. Next, she would stare at the endless “tunnel” formed by the reflections until she could see a face. This divination method is based on recursion.

Recursion, or self-same replication, occurs when a rule or procedure is applied to its own successive results. In other words, something -an object, image, rule or procedure- is replicated and copied within itself into infinity. The best definition of recursion is as follows: “Recursion, see Recursion”. In fact, recursion is all around us: you can see it in tree branches, blood vessels and ice crystals, in Romanesco cabbage and nautilus shells.

Top: Romanseco cabbage, middle: nautilus shell, bottom: fractal geometry
Recursion has inspired artists like M.C. Escher, designers (a famous example is the Droste cocoa powder tin), film-makers (check Doctor Strange) and, of course, mathematicians. You might have heard of fractal geometry, where the same patterns are replicated at different scales, as in the picture on the right.

Recursion in grammar
Some linguists believe that human language is based on recursion, too. For example, Hauser, Chomky and Fitch in their widely cited article argue that recursion forms the core of human language. But what exactly is recursion in language? It may sound strange, but there is a lot of confusion about the definition of recursion, in fact (as shown here, for example). There are at least two widespread interpretations, which I’ll call “Matryoshka dolls” and “Prolific hierarchy”.

Matryoshka dolls in grammar
For some linguists, one can speak about recursion when a language allows the user to embed one structure within the same structure. For example, one clause (a basic sentence unit) can be embedded within another clause, as in the following examples:

[Mary knew [that John said [that Jane did it]]]
[[[Tom’s daughter’s] friend’s] birthday]

These structures are like matryoshka dolls. They contain one unit inside another, and so on.

Most languages allow these structures. There are doubts, however, that this is universal. In particular, Daniel Everett has argued that the Pirahã, an indigenous folk living in the Amazon Rainforest, do not have convincing examples of recursion neither in their grammar nor in their culture. In a language like Pirahã, the sentence Mary knew that John said that Jane did it could be expressed by a concatenation of simple sentences, something like Jane did it. John said. Mary knew it. The intended meaning would be inferred from context. Linguists are still fighting with each other about Pirahã – whether it has any recursive structures worth speaking about or not, and whether it has serious consequences for linguistic theory (see here and here, for example).

Prolific hierarchy
The other understanding of recursion is more abstract. Noam Chomsky, who popularized recursion, was inspired by an observation made by Wilhelm von Humboldt, a German linguist and philosopher, that language makes ‘infinite use of finite means’. That is, language users are able to create an endless number of sentences applying a limited set of grammatical rules to the words in a language. In other words, thanks to a language’s grammar rules, there is no limit to the number of sentences we can create.

For this purpose, as Chomsky and his followers argue, there is a special computational procedure in our brain, called Merge. It constructs grammatical objects from words and their combinations, until all words in a sentence are integrated in one structure. So, if a sentence has more than two words , it is recursive because there should be at some point a merge between a word and an already merged phrase. For example, take a sentence, My professor cried bitterly. To understand the structure of the sentence (S), as shown in the tree below, our brain applies the computational procedure Merge to the nominal phrase [[my][professor]] and the verb phrase [[cried] [bitterly]], and then merges these merged phrases using Merge.

Example sentence structure

But is this type of recursion really as unique to human language as it is claimed? Generally speaking, the structure produced by Merge is a hierarchy. Smaller units are organized in larger ones, and those in even larger ones, and so on.We can find hierarchical structures everywhere in nature and culture. Take the human body. We can start with atoms of chemical elements, which form molecules, such as DNA, RNA, proteins and many others, which form different parts of biological cells. The latter organize in tissues, which constitute organs, which form our body. All complex systems are in fact hierarchical!

So is human behaviour… For example, in the morning, I get up, go to the shower, brush my teeth, dress and have my breakfast. All these activities can be split into subroutines. For instance, having breakfast means preparing it and eating it. Preparing it includes making a cup of coffee and a bowl of porridge, and so on.

A more sophisticated example is a musical symphony, which consists of motions. Each of those motions has its own structure, all the way down to the individual bars, notes and pauses. Every symphony is unique, and there are no indications that all options will be ever exhausted. Our species is thus able to generate an infinite number of hierarchical activities and cultural products. Why should grammar be any different?

Does this mean that recursion is something trivial to talk about then and we should move on to something more exciting? Not yet! In fact, there are claims that recursion plays an intriguing and important role in human communication. But this is the topic of another post. Stay tuned!


Read more
– Chomsky, N. (1957). Syntactic structures. The Hague: Mouton.
– Chomsky, N. (1995). The Minimalist Program. Cambridge, Massachusetts: The MIT Press.
– Everett, D. (2005). Cultural constraints on grammar and cognition in Pirahã: Another look at the design features of human language. Current Anthropology 46(4): 621–646. Link
– Hauser, M. D., Chomsky, N., & Tecumseh Fitch, W. (2002). The faculty of language: What it is, who has it, and how did it evolve? Science 298: 1569. Link
– Humboldt, von W. (1836 [1988]). On Language: The Diversity of Human Language-Structure and its Influence on the Mental Development of Mankind. Cambridge: Cambridge University Press.
– Simon, H. A. (1962). The architecture of complexity. Proceedings of the American Philosophical Society 106(6): 467–482. Link
– Tomalin, M. (2011). Syntactic structures and the legacy of imprecision. Journal of Logic, Language, and Information 20(3): 297–315. Link


– Romanesco cabbage via link
– Nautilus mollusc shell via link
– Fractal geometric shape created in R using the mandelbrot package


Writer: Natalia Levshina
Editor: Merel Wolf
Dutch translation: Inge Pasman
German translation: Bianca Thomsen
Final editing: Merel Wolf