# 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. Commented 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. Commented Mar 17, 2019 at 14:40

## 7 Answers

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.

• @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). Commented Feb 23, 2013 at 8:30
• @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. Commented 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). Commented Feb 24, 2013 at 20:49
• @GastonÜmlaut, the thing is that Everett started arguing with Chomsky and co., without having understood how generative syntax is done. Under Chomsky's proposal, it is immaterial whether there is recursion in Piraha - or in any natural language, for that matter. Chomsky and co. are interested in FLN, i.e. (human) capacity to acquire recursive structures. Now, if Everett or anyone else really wants to undermine UG, they should show that there are "normal" L1 speakers of some language who cannot acquire recursive structures. Commented Feb 28, 2013 at 2:18
• My personal opinion is that this recursive "hypothesis" is not a verifiable hypothesis but rather an axiom, which you can either accept or reject. Commented Feb 28, 2013 at 2:20

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".

• Presented humbly and self-doubtingly, I believe it speaks to someone’s cognizance when they find the ambiguity of a situation prevents them from making sure pronouncements. I agree that these questions of if “human language is recursive” may be unripe for dogmatic contest until there is a very unambiguous statement about what that is. It might be a deeper question than it first seems. I don’t know Piraha, but it’s hard to imagine a) how they could talk if they can’t embed clauses. That severely restricts the kinds of relations you can express, doesn’t it? Like, sentences of the form (roughly) Commented May 14, 2023 at 15:08
• NP + VP, and you cannot do something like AdjP -> Adj + AdjP ? Or VP -> V + NP, where the noun phrase is maybe a relative clause like “the person eating bread”, or something? I don’t know about this debate but it sounds like something you could ponder on with the Piraha just as hypothetical: even if they’re language has no embedded or coordinated clauses, or whatever “recursion” means here, why would that be interesting? I know this is because im new to this, but imagine if I found a homeless person who could only speak in monosyllabic words. So what? It’s not clear to me why the Piraha Commented May 14, 2023 at 15:12
• would be such a rare anomaly, why somewhere out there deep in the Amazon is the lone rare counter example to the theory of language. It sounds quizzical, at least from a distance. journals.plos.org/plosone/article?id=10.1371/… daneverettbooks.com/the-logical-issue-of-claims-of-recursion Commented May 14, 2023 at 15:13
• @JohnSmith Allegedly, you just use separate, sequential sentences/clauses in Piraha rather than embedded clauses to express the same ideas that you might use a relative clause for in other languages. Commented May 14, 2023 at 16:47
• I had a thought on this which maybe could be posted as a separate question. In an article I posted as an answer here, my unconfirmed impression is that Geoffrey Pullum claimed that all syntax rules producing their own type as output can be split into sentences where an argument refers to its head using anaphora. But I suggest that anaphora is different than syntax. I wonder if an example can show how a language with terminating rules is not the same as a language with one. I will explain in my post. Commented Jun 6, 2023 at 11:23

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 .

From what I've read, a recursive rule is one that can operate on its own output.

For example, consider the noun phrase "the dolphin." It can be modified by a relative clause that contains a noun phrase like so: "the dolphin that ate the fish."

The noun phrase "the fish" can also be modified by its own relative clause that contains a noun phrase: "the dolphin that ate the fish that swallowed the crab"

The noun phrase "the crab" can also be modified by its own relative clause that contains a noun phrase: "the dolphin that ate the fish that swallowed the crab that had been marked with radioactive dye"

The noun phrase "radioactive dye" can also be modified by its own relative clause that contains a noun phrase like so: "the dolphin that ate the fish that swallowed the crab that had been marked with radioactive dye that my mother had bought as a street fair"

You get the idea. A relative clause can modify a noun phrase within a previous relative clause. The resulting chains of relative clauses can be theoretically (though not actually) infinite because the rules for forming relative clauses can be applied to a noun phrase in a matrix relative clause.

You can always turn to Pullum for illumination.*

(to be further edited)

I think he is saying that there is a widespread claim which different people are reiterating, but it isn’t even clear what they’re claiming. If you try to refine it a bit, it can be either trivially true but pretty obvious, or if made more specific, then false, or pending on further conditions.

Pullum is a really good example of questioning rhetoric one is exposed to in an intellectual field and trying to develop it with rigor, whereupon it may not have substance, unlike repeating claims that others with a degree of social status, visibility, reputation or authority are saying, possibly because other people are, too. (For example: https://web.mit.edu/norvin/www/24.902/PullumScholz.pdf)

The Standard Argument:

The argument that linguists have most relied upon for support of the infinitude claim is actually a loose family of very similar arguments that we will group together and call the Standard Argument…

The Standard Argument starts with certain uncontested facts about the syntactic structure of certain classes of expressions. It draws from these the intermediate conclusion that there can be no longest expression. The infinitude claim then follows.

(I) Syntactic facts

I exist is a declarative clause, and so is I know that I exist, and so is I know that I know that I exist; came in and went out is a verb phrase coordination, and so is came in, turned round, and went out, and so is came in, saw us, turned round, and went out; very nice is an adjective phrase, and so is very very nice, and so is very very very nice; and so on for many other examples and types of example.

It is not controversial that a huge collection of facts of this sort, showing grammaticality-preserving extensibility of various types of expression, could be presented for many different languages.

The intermediate conclusion that purportedly follows from facts like those in (I) is presented in (II):

(II) The No Maximal Length claim (NML)

For any English expression there is another expression that is longer. (Equivalently: No English expression has maximal length.)

Some linguists give a stronger claim we can call NML+, which entails (II): They claim not just that for any expression a longer expression always exists, but that starting from any arbitrary grammatical expression you can always construct a longer one that will still be grammatical, simply by adding words. NML+ is never actually crucial to the argument, but we note various appearances of it below.

The ultimate conclusion from the argument is then (III):

(III) The Infinitude Claim

The collection of all grammatical English expressions is an infinite set.

Presentations of the Standard Argument utilizing (I) – (III) in various forms can be found in large numbers of introductory texts on linguistics. Langacker (1973), for example, asserts (II) as applied to English, in both its weaker and its stronger form (he seems to offer NML+ as an explication of why NML must be true), and concludes (III), with an additional claim appended:

(4) There is no sentence to which we can point and say, ‘Aha! This is the longest sentence of the language.’ Given any sentence of English (or any other language), it is easy to find a longer sentence, no matter how long the original is . . . The set of well-formed sentences of English is infinite, and the same is true of every other language. (Langacker 1973: 30)

The parenthetical remark “or any other language”, claiming a universalization of (III) to all human languages, does not, of course, follow from the premises that he states (compare the similar remark by Epstein and Hornstein in (2)).

Bach (1974: 24) states that if we assent to (II) – which he gives as NML+ – then we must accept (III):

(5) If we admit that, given any English sentence, we can concoct some way to add at least one word to the sentence and come up with a longer English sentence, then we are driven to the conclusion that the set of English sentences is (countably) infinite. (1974: 24)

(The parenthesized addition “countably” does not follow from the premises supplied, but we ignore that.)

Huddleston (1976) (making reference to unbounded multiple coordination rather than subordination facts) also asserts that if we accept (II) we must accept (III):

to accept that there are no linguistic limits on the number of clauses that can be coordinated within a sentence is to accept that there are no linguistic limits on the number of different sentences in the language, ie that there is a (literally) infinite set of well-formed sentences. (Huddleston 1976: 7)

Stabler (1999: 321) poses the question “Is the set of linguistic structures finite?” as one of the issues that arises in connection with applying formal grammars to human languages, and answers it by stating that (II) seems to be true, so we can conclude (III):

(7) there seems to be no longest sentence, and consequently no maximally complex linguistic structure, and we can conclude that hu- man languages are infinite.

A more recent discussion in Hauser, Chomsky and Fitch (2002: 1571) affirms that human languages have “a potentially infinite array of discrete expressions” because of a “capacity” that “yields discrete infinity (a property that also characterizes the natural numbers).” They proceed to the rather surprising claim that “The core property of discrete infinity is intuitively fa miliar to every language user” (we doubt this), and then state a coordination redundantly consisting of three different ways of expressing (III):

(8) There is no longest sentence (any candidate sentence can be trumped by, for example, embedding it in ‘Mary thinks that . . . ’), and there is no non-arbitrary upper bound to sentence length.

Other passages of a broadly similar character could be cited. We now proceed to critique the argument that they all hint at.

# 3 How the Standard Argument fails

All the linguists quoted in (4) – (8) seem to be concentrating on the step from (II) to (III), which is trivial mathematics. Under the traditional informal definition of ‘infinite’, where it simply means ‘not finite’ (a collection being finite if and only if it we can count its elements and then stop.)

As Dretske (1965: 100) remarks, to say that if a person continues counting forever he will count to infinity is coherent, but to say that at some point he will have counted to infinity is not.

So (II) and (III) are just paraphrases. The claim is that counting the expressions of a language like English could go on forever, which is all that ‘infinite’ means.

It is the inference from (I) to (II) that should be critically examined. Linguists never seem to discuss that step. What licenses inferring NML from certain syntactic properties of individual English expressions?

3.1 Not inductive generalization, nor mathematical induction

To begin with, we can dismiss any suggestion that the inference from (I) to (II) is an inductive generalization – an ampliative inference from a statement about certain individuals to a statement about all the members of some col- lection.

An example of inductive generalization on English expressions – and a justifiable one – would be to reason from English adjective phrases like very nice, very very nice, very very very nice, and so on, to the generalization that repeatable adverb modifiers in adjective phrases always precede the head.

But inferring that the collection of all possible English adjective phrases has no longest member is an entirely different matter. The conclusion is not about the properties of adjective phrases at all. It concerns a property of a different kind of object: It attributes a size to the set of all adjective phrases of a certain form, which is very different from making a generalization about their form.

A different possibility would be that (II) can be concluded from (I) by means of some kind of mathematical argument, rather than an inductive gen- eralization from linguistic data. Pinker (1994: 86) explicitly suggests as much: By the same logic that shows that there are an infinite number of integers–if you ever think you have the largest integer, just add 1 to it and you will have another–there must be an infinite number of sentences.

This reference to a “logic that shows that there are an infinite number of integers” is apparently an allusion to reasoning by mathematical induction.

Arguments by mathematical induction use recursion to show that some property holds of all of the infinitely many positive integers.

There are two components: A base case, in which some initial integer such as 0 or 1 is established as having a certain property P , and an inductive step in which it is established that if any number n has P then n + 1 must also have P . The conclusion that every positive integer has P then follows.

However, it follows only given certain substantive arithmetical assump- tions.

Specifically, we need two of Peano’s axioms: The one that says every integer has a successor (so there is an integer n + 1 for every n), and the one that says the successor function is injective (so distinct numbers cannot share a successor).

Pinker’s suggestion seems to be that a mathematical induction on the set of lengths of English expressions will show that English is an infinite set. This is true, provided we assume that the analogs of the necessary Peano axioms hold on the set of English expressions. That is, we must assume both that every English expression length has a successor, and that no two English expression lengths share a successor. But to assume this is to assume the NML claim (II). (There cannot be a longest expression, because the length of any such expression would have to have a successor that was not the successor of any other expression length, which is impossible.) Thus we get from (I) to (II) only by assuming (II). The argument makes no use of any facts about the structure of English expressions, and simply assumes what it was supposed to show.

## 3.2 Arguing from generative grammars

A third alternative for arguing from (I) to (II) probably comes closest to re- constructing what some linguists may have had in mind. If facts like those in (I) inevitably demand representation in terms of generative rule systems with recursion, infinitude might be taken to follow from that. The enormous influence of generative grammatical frameworks over the past fifty years may have led some linguists to think that a generative grammar must be posited to describe data sets like the ones illustrated in (I). If in the face of such sets of facts there was simply no alternative to assuming a generative grammar description with recursion in the rule system, then a linguistically competent human being would have to mentally represent “a recursive procedure that generates an infinity of expressions” (2002: 86–87), and thus (II) would have to be, in a sense, true.

There are two flaws in this argument. The less important one is perhaps worth noting in passing nonetheless. It is that assuming a generative frame- work, even with non-trivially recursive rules, does not entail NML, and thus does not guarantee infinitude. A generative grammar can make recursive use of non-useless symbols and yet not generate an infinite stringset. Consider the following simple context-sensitive grammar (adapted from one suggested by Andra ́s Kornai):

(9) Nonterminals: Start symbol:

Terminals: Rules: S, NP, VP S They, came, running S→NPVP VP→VP VP NP → They VP → came / They VP → running / They came

The rule “VP → VP VP” is non-trivially recursive – it generates the infinite set of all binary VP-labelled trees. No non-terminals are unproductive (inca- pable of deriving terminal strings) or unreachable (incapable of figuring in a completed derivation from S). And no rules are useless – in fact all rules par- ticipate in all derivations that terminate. Yet only two strings are generated: They came, and They came running. The structures are shown in (10).

(10)S S 3 & 3 & 3 NPVP NPVP 4

VP No derivation that uses the crucial VP rule more than once can terminate. Thus recursion does not guarantee infinitude.

8

They came They VP

came running

4

One might dismiss this as an unimportant anomaly, and say that a proper theory of syntactic structure should simply rule out such failures of infinitude by stipulation.

But interestingly, for a wide range of generative grammars, including context-sensitive grammars and most varieties of transformational grammar, questions of the type ‘Does grammar G generate an infinite set of strings?’ are undecidable, in the sense that no general algorithm can deter- mine whether the goal of “a recursive procedure that generates an infinity of expressions” has been achieved.

One could stipulate in linguistic theory that the permissible grammars are (say) all and only those context-sensitive grammars that generate infinite sets, but the theory would have the strange property that whether a given grammar conformed to it would be a computa- tionally undecidable question.3

One important point brought out by example grammars like (9) is that you can have a syntax that generates an infinitude of structures without thereby having an infinitude of generated expressions. Everything depends on the lexicon. In (9) only the lexical items They, came, and running are allowed, and they are in effect subcategorized to ensure that came has to follow They and running has to follow came. Because of this, almost none of the rich variety of subtrees rooted in VP can contribute to the generation of strings. Similarly, the syntax of a human language could allow clausal complementa- tion, but if the lexicon happened to contain no relevant lexical items (verbs of propositional attitude and the like), this permissiveness would be to no avail.

However, there is a much more important flaw in the argument via gener- ative grammars. It stems from the fact that generative grammars are not the only way of representing data such as that given in (I). There are at least three alternatives – non-generative ways of formulating grammars that are mathe- matically explicit, in the sense that they distinguish unequivocally between grammatical and ungrammatical expressions, and model all of the structural properties required for well-formedness.

First, we could model grammars as transducers, i.e., formal systems that map between one representation and another. It is very common to find theo- retical linguists speaking of grammars as mapping between sounds and mean- ings. They rarely seem to mean it, because they generally endorse some va- riety of what Seuren (2004) calls random generation grammars, and Seuren is quite right that these cannot be regarded as mapping meaning to sound. For example, as Manaster Ramer (1993) has pointed out, Chomsky’s remark that a human being’s internalized grammar “assigns a status to every relevant 9

physical event, say, every sound wave” (Chomsky 1986: 26) is false of the generative grammars he recognizes in the rest of that work: Grammars of the sort he discusses assign a status only to strings that they generate. They do not take inputs; they merely generate a certain set of abstract objects, and they cannot assign linguistic properties to any object not in that set. However, if grammars were modeled as transducers, grammars could be mappings be- tween representations (e.g., sounds and meanings), without regard to how many expressions there might be. Such grammars would make no commit- ment regarding either infinitude or finitude. A second possibility is suggested by an idea for formalizing the trans- formational theory of Zellig Harris. Given what Harris says in his various papers, he might be thought of as tacitly suggesting that grammars could be modeled in terms of category theory. There is a collection of objects (the utterances of the language, idealized in Harris 1968 as strings paired with acceptability scores), whose exact boundaries are not clear and do not re- ally matter (see Harris 1968: 10–12 for a suggestion that the collection of all utterances is “not well-defined and is not even a proper part of the set of word sequences”); and there is a set of morphisms defined on it, the trans- formations, which appear to meet the defining category-theoretic conditions of being associative and composable, and including an identity morphism for each object. In category theory the morphisms defined on a class can be stud- ied without any commitment to the cardinality of the class. A category is characterized by the morphisms in its inventory, not by the objects in the un- derlying collection. This seems very much in the spirit of Harris’s view of language, at least in Harris (1968), where a transformation is “a pairing of sets . . . preserving sentencehood” (p. 60). Perhaps the best-developed kind of grammar that is neutral with respect to infinitude, however, is a third type: The purely constraint-based or model- theoretic approach that has flourished as a growing minority viewpoint in formal syntax over the past thirty years, initially given explicit formulation by Johnson and Postal (1980) but later taken up in various other frameworks — for example, LFG as presented in Kaplan (1995) and as reformalized by Blackburn and Gardent (1995); GPSG as reformalized by Rogers (1997); and HPSG as discussed in Pollard (1999) and Ginzburg and Sag (2000). The idea of constraints is familiar enough within generative linguistics. The statements of the binding theory in GB (Chomsky, 1981), for exam- ple, entail nothing about expression length or set size. (To say that every 10

anaphor is bound in its governing category is to say something that could be true regardless of how many expressions containing anaphors might exist.) Chomsky (1981) used such constraints only as filters on the output of an un- derlying generative grammar with an X-bar phrase structure base component and a movement transformation. But in a fully model-theoretic framework, a grammar consists of constraints on syntactic structures and nothing more – there is no generative component at all. Grammars of this sort are entirely independent of the numerosity of ex- pressions (though conditions on the class of intended models can be stipu- lated at a meta-level). For example, suppose the grammar of English includes statements requiring (i) that adverb modifiers in adjective phrases precede the head adjective; (ii) that an internal complement of know must be a finite clause or NP or PP headed by of or about; (iii) that all content-clause comple- ments follow the lexical heads of their immediately containing phrases; and (iv) that the subject of a clause precedes the predicate. Such conditions can adequately represent facts like those in (I). But they are compatible with any answer to the question of how many repetitions of a modifier an adjective can have, or how deep embedding of content clauses can go, or how many sen- tences there are. The constraints are satisfied by expressions with the relevant structure whether there are infinitely many of them, or a huge finite number, or only a few.

Derbyshire (1979) describes the Amazonian language Hixkarya ́na (in the Cariban family, unrelated to Piraha ̃), and similar syntactic characteristics emerge. Hixkarya ́na has no finite complement clauses, hence no indirect speech constructions or verbs of propositional attitude. According to Der- byshire, “Subordination is restricted to nonfinite verbal forms, specifically de- rived nominals” or “pseudo-nominals that function as adverbials”, and “There is no special form for indirect statements such as ‘he said that he is going’. . . ” (p. 21). (There is a verb meaning ‘say’ that allows for directly quoted speech, but that does not involve subordination.) Hixkarya ́na has nominalization (of an apparently non-recursive kind), but no clausal subordination. Derbyshire 18 also notes (1979: 45) the absence of any “formal means . . . for expressing co- ordination at either the sentence or the phrase level, i.e. no simple equivalents of ‘and’, ‘but’ and ‘or’.” Givon (1979: 298) discusses the topic in general terms and relates it to language evolution, both diachronic and phylogenetic. He claims that “di- achronically, in extant human language, subordination always develops out of earlier loose coordination”, the evidence suggesting that it “must have also been a phylogenetic process, correlated with the increase in both cognitive capacity and sociocultural complexity”, and he observes: there are some languages extant to this day – all in preindus- trial, illiterate societies with relatively small, homogeneous so- cial units – where one could demonstrate that subordination does not really exist, and that the complexity of discourse–narrative is still achieved via “chaining” or coordination, albeit with an evolved discourse-function morphology. . . Other works, more recent but still antedating Everett, could be cited. For example, Deutscher (2000, summarized in Sampson 2009) claims that when Akkadian was first written it did not have finite complement clauses, though later in its history it developed them. We are not attempting an exhaustive survey of such references in the liter- ature. We merely note that various works have noted the absence of iterable embedding in various human languages, and for some of those it has also been claimed that they lack syndetic sentence coordination (that is, they do not have sentence coordination that is explicitly marked with a coordinator word, as opposed to mere juxtaposition of sentences in discourse). Languages with neither iterable embedding nor unbounded coordination would in principle have just a finite (though very large) number of distinct expressions, for any given finite fixing of the lexicon – (though saying that there are only finitely many sentence presupposes that we have some way of distinguishing sentences from sentence sequences; this is by no means a trivial codicil, but let us assume it). The suggestion that there might be finite human languages, then, did not suddenly emerge with Everett’s work in 2005. It is implicit in plenty of earlier linguistic literature.

A language that can express multiple thoughts in a single sentence is not thereby required to do so. Complex sentences involving can be re-expressed in sequences of syntactically simpler sentences. For example, I think you re- alize that we’re lost and we should ask the way contains a coordination of finite clauses serving as a complement within a clausal complement, but it could be re-expressed paratactically (Here are my thoughts. You realize our situation. We’re lost. We should ask the way). Such re-expression trans- fers the (semantic) complexity of the content of the different clauses from the sentence level to the paragraph level. Absence of syntactic embedding and coordination resources in a language that calls for certain content to be expressed multisententially rather than unisententially is not the same as ren- dering a thought inexpressible or untranslatable. Just as absence of syntactic support for infinitude claims about some lan- guage does not imply anything demeaning about its speakers, neither does it threaten the research program of transformational-generative grammar. Gen- erative linguistics does not stand or fall with the infinitude claim. Overstate- ments like those in (1) or (2) can be dismissed without impugning any re- search progam. We argued at the end of § 3.2 above that generative rule systems with recursion do not have to be used to represent the syntax of lan- guages with iterable subordination; but that does not mean it is an error to use generative rule systems for describing human languages or stating universal principles of linguistic structure. Whether it is an error or not depends on such things as the goals of a linguistic framework, and the data to which its theorizing aims to be responsive (Pullum and Scholz 2001, 2005).

6 Concluding remarks

Infinitude of human languages has not been independently established — and could not be. It does not represent a factual claim that can be used to support the idea that the properties of human language must be explicated via gener- ative grammars involving recursion. Positing a generative grammar does not entail infinitude for the generated language anyway, even if there is recursion present in the rule system. The remark of Lasnik (2000: 3), that “We need to find a way of repre- senting structure that allows for infinity”, therefore has it backwards. It is not that languages have been found to be infinite so our theories have to represent them as such. Language infinitude is not a reason for adopting a generative grammatical framework, but merely a theoretical consequence that will (un- der some conditions) emerge from adopting such a framework. What remains true, by contrast, is Harris’s claim (1957: 208) “If we were to insist on a finite language, we would have to include in our grammar sev- eral highly arbitrary and numerical conditions.” No such arbitrary conditions should be added to grammars, of course. Ideally grammars should be stated in a way that insists neither on finitude nor on infinitude. It is a virtue of model-theoretic syntactic frameworks that they allow for this.

Read the entire thing:

http://www.lel.ed.ac.uk/~gpullum/bcscholz/Infinitude.pdf

*hyperbole

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. Commented Jun 3, 2018 at 16:35