What is recursion? I've looked at the Wikipedia's explanation (recursion and then recursion in language) but that explanation is not really clear.
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.
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 and cute Alice.
Nice and cute Alice, sweet, gentle and considerate.
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 .