

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

What is recursion? I've looked at the Wikipedia's explanation (recursion and then recursion in language) but that explanation is not really clear.

share|improve this question

Recursion is a property of language.

From a Linguistics viewpoint, recursion can also be called nesting. As I've stated in this answer to what defines a language (third-last bullet point), recursion "is a phenomenon where a linguistic rule can be applied to the result of the application of the same rule."

Let's see an example of this. Consider the sentence:

Alex has a red car.

An application of recursion would give:

Alex, whom you know very well, has a red car.

And then:

Alex, whom you know very well, has a red car which is parked there.

And so on. This can go on endlessly, even if in real situations recursion will stop at a certain point, since the idea being expressed would get too confused. Recursion can also be applied to a noun and its adjectives:

Nice Alice.


Nice and cute Alice.

And again

Nice and cute Alice, sweet, gentle and considerate.

share|improve this answer
Though, of course, recursion, like nasal consonants, is merely a very frequent (but not indispensible) property of natural languages, since Pirahã is known not to have recursive syntax. – jlawler Feb 23 '13 at 5:15
@jlawler: Pirahã is not known for its lack of recursion. This was claimed by Everett (2005), but it was seriously challenged by Pesetsky et al (2009). My point is that your comment seems to suggest that this is a fact, when this is actually a matter of debate in linguistics (although many linguists are fed up with it). – KleinePrins Feb 23 '13 at 8:30
@KleinePrins It's not settled? I personally knew that Pirahã had been considered as a language that lacks it and so it challenged the theory that it's an inherent languages tract, an idea supported by Chomsky. – Alenanno Feb 23 '13 at 9:57
@Alenanno I don't know your source for personally knowing about Pirahã, but I think this is all part of a conceptual misunderstanding and an attack to a straw man. Chomsky didn't claim that all languages must share the same properties, but the critics seem to fail to acknowledge this. The idea is not that every language must be recursive, but that any human can learn a recursive grammar because recursion is a property of the Faculty of Language (not of languages). As for Pirahã, I think the reassessment by Pesetsky et al. is very convincing, but the data are still under consideration. – KleinePrins Feb 23 '13 at 10:52
I'd like to add that not everyone thinks that "[r]ecursion is a property of languages." And, if I'm not mistaken, Chomsky and co. argued that recursion is a property of language, not languages - cf. Hauser, Fitch, and Chomsky 2002: “At a minimum, then, FLN includes the capacity of recursion” (p. 19). The authors stress out that recursion is a capacity several times in their paper. Later, they argue that “the core recursive aspect of FLN currently appears to lack any analog in animal communication and possibly other domains as well” (p. 19). – Alex B. Feb 24 '13 at 20:49

Recursion is computability,in modern theory,it is the central idea of computational theory,and due to different computational models ,that have been proved to be equivalent,like Turing Machine,Lambda calculus ,Post system,recursive function (computable function),etc,recursion may appear in different forms,formal grammar or Chomsky hierarchy is one of such forms,which is also equivalent to other computational models .

share|improve this answer

Your Answer


