27 May 2009

Linguistic Factoid No. 9: Recursion

So what is recursion? Recursion, as defined by the Oxford English Dictionary, is the property of a certain rule in which the output of the rule can serve as input to the same rule. I suppose this is best illustrated by a formula. So, let's build a sentence. These are the following rules for building a sentence.

Sentence = NP + VP
Noun Phrase = (Det) + N
Verb Phrase = V + (NP)

Using the above rules, we can build the following sentences.

1. John slept.
2. John saw Mary.
3. The man slept.
4. The man saw the woman.

However, there are plenty of other sentences that are possible, at least in English. Let us add another rule or two.

Verb Phrase = V + (CP)
Complement Phrase = C + S

Using these rules, we can now build the following sentences.

5. John knew that Mary saw the woman.
6. The man thought that John knew the answer.
7. My sister knows that I know that she knows that I am a jerk.

Now, notice the application of the rules in a recursive fashion. The rule that generates a complement phrase gives a sentence as an output, which then allows one to generate a new sentence again, and again, and again. Here are other examples of recursion. For ease of exposition, I added brackets as necessary.

8. I saw [the dog that chased [the cat that killed [the mouse that ate the cheese]]].

I could go on and on and on with this, describing each noun with a modifier. However, not all recursions can be infinite. There are times in which having multiple embedded stuff can make processing difficult, and one such example is center-embedding, where the recursive material is inside the sentence, not at the edge. I will illustrate this one by one, for ease of interpretation.

9. The mouse ate the cheese.
10. The [mouse that the cat killed] ate the cheese.
11. The [mouse that [the cat that the dog chased] killed] ate the cheese.
12. The [mouse that [the cat that [the dog that the city impounded] chased] killed] ate the cheese.

Who here still understands what the last sentence means?

Anyway, some linguists, notably Noam Chomsky, argues that recursion is one of the most fundamental aspects of language, and by having recursion possible, one can generate an infinite number of sentences using just simple finite rules. Other linguists, however, such as Daniel Everett, challenges this view, using data from other languages such as Piraha, in which there apparently is no use of recursion. If this is the case, then recursion cannot be universal. Obviously, the debate is more complicated than how I outlined it here, and it is keeping linguists busy. In fact, linguists who find this aspect of language fascinating are having a conference right this moment, in UMass Amherst. We'll see how this plays out.

(Weird Contraption, from my National Gallery of Art Series)


  1. Fascinating! I didn't understand the last sentence, too many loops. Also I think when you brought cheese into the picture, you closed the recursion since an inanimate noun (cheese) can't have a transitive verb associated with it, and without an object, the sentence can't move ahead (or will it?). The most you can say is 'the cheese smelled'...

    btw Jeruen, do you know Sanskrit? I've heard linguists speak highly about it. Its barely a spoken language now.

  2. Priyank,

    The last sentence wasn't talking about the cheese. It was talking about the mouse! But still, a dead mouse due to being killed by a cat couldn't eat cheese!

    And no, I do not know Sanskrit at all. I am not an Indo-Europeanist. I have friends who do however, and they could show me how Sanskrit and Irish relate to each other. My line of interest however, deals with how language is processed in the brain, so I am more of a lab-and-experiments person than a old-texts-in-archives person.

  3. I find it rather interesting that a Christian missionary turned Piraha convert had such slander and malice thrown his way because he dared to challenge an apparent universal law in linguistics. Perhaps in his defiance and courage to do so, language as we know it may grow andare evolve. Oh, and Priyank, the recursive sentences above were just as much about the cheese as they were the mouse. ;) To really understand language, we need to grasp an understanding of motivation and how this effects tonality of the subject(s) and yes, how the brain processes it.