What is recursion?

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

• To understand recursion, you need to first understand recursion. Oct 23, 2017 at 13:14
• You're over thinking this Wilson. All you need is the eloquence of the GNU, the ancient recursive beast. What does GNU mean, well a picture makes it look better; but, really all you need to know is GNU is Not Unix. Perfectly explains the concept without obscurantism, like all the other answers. Mar 17, 2019 at 14:40

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.

And

Nice and cute Alice.

And again

Nice and cute Alice, sweet, gentle and considerate.

• 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. Feb 23, 2013 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). Feb 23, 2013 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. Feb 23, 2013 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. Feb 23, 2013 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). Feb 24, 2013 at 20:49

I'm making this post pretty much just to link to something that seems relevant. I don't really understand the definition of recursion or its relevance to language. This may be a bit dangerous, but hopefully someone will tell me in the comments if I've mis-summarized something or if none of what I've linked to is worth anything.

The answers and comments to What's the difference between recursion and embedding? indicate that the defintion of "recursion" may vary between different theoretical frameworks.

"On recursion", by Jeffrey Watumull, Marc D. Hauser, Ian G. Roberts and Norbert Hornstein (Front. Psychol., 08 January 2014) is a review article that seems to lay out a generativist perspective on the linguistic definition of "recursion":

The core computational mechanisms of recursion, proposed to be constitutive of FLN, are: (i) computability, (ii) definition by induction, and (iii) mathematical induction.

However, there may be problems with the article (see the comments on the blog posts linked below).

Although embedding is often used as an example of recursion (which relates to the Pirahã debates), the article says that the absence of embedding is not the same thing as the absence of recursion.

Another section that seems relevant, although I can't claim to really understand it:

[...] it is false that “boundedness is principled” if for instance it is possible for the generative function only to “produc[e] a maximum phrase consisting of the verb's lexical frame plus as much as one modifier word per constituent of the phrase and up to one prepositional adjunct phrase” (Everett, 2012: 558); incidentally, the bound is claimed only for “sentential syntax,” but of course syntax—and recursion—extends “super-sententially” (as we will discuss). This function is demonstrably computable: i.e., the set of possible phrases is non-arbitrary and, even if finite, contains too many members to be listed as a lookup table; thus it must be generated by a finitary (recursive) procedure. The function is defined by induction: i.e., outputs are recursed (carried forward on tape) as inputs to strongly generate structured expressions; thus the process is not a form of iteration (equivalently tail recursion) as claimed2. And finally, the function is mathematically inductive: i.e., unboundedness would emerge with relaxation of the arbitrary lexical restrictions; furthermore, even with such restrictions, it has not been demonstrated that the number of arguments per verb and the number of modifiable constituents is bounded by principle. In short, this function is recursive.

Ultimately, any boundedness is demonstrably arbitrary as proved by the undisputed fact that recursion is unbounded in some (i.e., most or, as we submit, all) languages: i.e., it follows from mathematical law that recursion is unlearnable and thus must be part of the species endowment (UG), and thus universal [...]

Therefore even if it were true that “[t]he upper limit of a Pirahã sentence is a lexical frame with modifiers [a]nd up to two […] additional sentence-level or verb-level prepositional adjuncts” (Everett, 2012: 560), nothing would follow for the universality of recursion. And incidentally, to reiterate, it is undisputed that all languages are recursively unbounded at the super-sentential (discourse) level; and the sentential/super-sentential distinction is artificial [...]

Hornstein made a post about the article on the blog Faculty of Language ("More on recursion") that has some relevant discussion in the comments.

A follow-up post ("Jeff W comments on comments on recursion") contains the following elaborations from Watumull:

• It is no error to equate Turing computability with Gödel recursiveness.

• The important aspect of the recursive-function/lookup-table distinction is not computability per se (table look-up is trivially computable) but explanation. A recursive function derives--and thus explains--a value. A look-up table stipulates--and thus does not explain--a value.

• Jeffrey Watumull January 15, 2014 at 11:54 AM
“Assume that the process is Merge. Take a word and combine it with another word. Then combine the result of that operation with another word. This is neither using the same word over and over (it is using separate tokens) nor recursive -- it is iterative” (Everett 2012: 4). This is misleading, for this process is technically recursive: the value of Merge at step n is defined by the value at step n-1 (i.e., it is a definition by recursion/induction.) This is tail recursion (in the mathematical sense) because the value of n is a function only of n-1 (i.e., the “tail” of the derivation, c.f., “recursive”/“iterative” implementations of the factorial function).

• Jeffrey Watumull January 15, 2014 at 12:00 PM
(N.B. The Pirahã process is in fact not merely tail recursive, because the value of Merge at n is not only a function of the value of n-1, but I assumed it for the sake of argument.)

As these last comments indicate, in the generative Minimalist Program, the idea of recursion in language is connected to the idea of "Merge".

A definition which appeals to what is being defined is recursive.

For instance, a phrase structure rule for coordination of sentences which defines an S using S in the definition, S -> S "and" S (A sentence may consist of a sentence followed by "and" followed by a sentence), is recursive.

It is possible for a set of rules to be recursive, even no single one of the rules is recursive. For example the set of rules S -> NP V; NP -> "that" S is recursive, because S must be interpreted in order to give a full interpretation of S.

Similarly in programming, a procedure is recursive when among the procedures which are called to complete some computation is that very procedure itself.

In mathematics, a definition which appeals to the term being defined is recursive. For instance, "positive integer" can be defined as "1" or the successor of some positive integer.

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 .

recursion in language means a repetition of function or role. for example, i definitely completely really love you. in the sentence you can notice that definitely, completely, and really are having same function, adverb. so ya

• No. Repetition (iteration) is not the same as recursion. Though tail recursion is equivalent to iteration, computationally. Jun 3, 2018 at 16:35