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:
An application of recursion would give:
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:
|show 13 more comments|
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 .