Editing Recursion (section)

==In language==
Linguist [[Noam Chomsky]], among many others, has argued that the lack of an upper bound on the number of grammatical sentences in a language, and the lack of an upper bound on grammatical sentence length (beyond practical constraints such as the time available to utter one), can be explained as the consequence of recursion in natural language.<ref>{{cite book|last=Pinker|first=Steven|title=The Language Instinct|year=1994|publisher=William Morrow}}</ref><ref>{{cite journal | doi = 10.1016/j.cognition.2004.08.004 | title = The faculty of language: What's so special about it? | year = 2005 | last1 = Pinker | first1=Steven | last2 = Jackendoff | first2=Ray | journal = Cognition | volume = 95 | issue = 2 | pages = 201–236 | pmid=15694646| citeseerx = 10.1.1.116.7784 | s2cid = 1599505 }}</ref>

This can be understood in terms of a recursive definition of a syntactic category, such as a sentence. A sentence can have a structure in which what follows the verb is another sentence: ''Dorothy thinks witches are dangerous'', in which the sentence ''witches are dangerous'' occurs in the larger one. So a sentence can be defined recursively (very roughly) as something with a structure that includes a noun phrase, a verb, and optionally another sentence. This is really just a special case of the mathematical definition of recursion.

This provides a way of understanding the creativity of language—the unbounded number of grammatical sentences—because it immediately predicts that sentences can be of arbitrary length: ''Dorothy thinks that Toto suspects that Tin Man said that...''. There are many structures apart from sentences that can be defined recursively, and therefore many ways in which a sentence can embed instances of one category inside another.<ref>{{Cite web|url=https://www.thoughtco.com/recursion-grammar-1691901|title=What Is Recursion in English Grammar?|last=Nordquist|first=Richard|website=ThoughtCo|language=en|access-date=2019-10-24}}</ref> Over the years, languages in general have proved amenable to this kind of analysis.

The generally accepted idea that recursion is an essential property of human language has been challenged by [[Daniel Everett]] on the basis of his claims about the [[Pirahã language]]. Andrew Nevins, David Pesetsky and Cilene Rodrigues are among many who have argued against this.<ref>{{cite journal |doi=10.1353/lan.0.0140 |title=Evidence and argumentation: A reply to Everett (2009) |url=http://web.mit.edu/linguistics/people/faculty/pesetsky/Nevins_Pesetsky_Rodrigues_2_Evidence_and_Argumentation_Reply_to_Everett.pdf |year=2009 |last1=Nevins |first1=Andrew |last2=Pesetsky |first2=David |last3=Rodrigues |first3=Cilene |journal=Language |volume=85 |issue=3 |pages=671–681 |s2cid=16915455 |archive-url=https://web.archive.org/web/20120106154616/http://web.mit.edu/linguistics/people/faculty/pesetsky/Nevins_Pesetsky_Rodrigues_2_Evidence_and_Argumentation_Reply_to_Everett.pdf |archive-date=2012-01-06}}</ref> Literary [[self-reference]] can in any case be argued to be different in kind from mathematical or logical recursion.<ref name="Drucker2008">{{cite book |last=Drucker|first=Thomas |title=Perspectives on the History of Mathematical Logic |url=https://books.google.com/books?id=R70M4zsVgREC&pg=PA110 |date=4 January 2008 |publisher=Springer Science & Business Media |isbn=978-0-8176-4768-1 |page=110}}</ref>

Recursion plays a crucial role not only in syntax, but also in [[natural language semantics]]. The word ''and'', for example, can be construed as a function that can apply to sentence meanings to create new sentences, and likewise for noun phrase meanings, verb phrase meanings, and others. It can also apply to intransitive verbs, transitive verbs, or ditransitive verbs. In order to provide a single denotation for it that is suitably flexible, ''and'' is typically defined so that it can take any of these different types of meanings as arguments. This can be done by defining it for a simple case in which it combines sentences, and then defining the other cases recursively in terms of the simple one.<ref>Barbara Partee and Mats Rooth. 1983. In Rainer Bäuerle et al., ''Meaning, Use, and Interpretation of Language''. Reprinted in Paul Portner and Barbara Partee, eds. 2002. ''Formal Semantics: The Essential Readings''. Blackwell.</ref>

A [[recursive grammar]] is a [[formal grammar]] that contains recursive [[production (computer science)|production rules]].<ref name="ns02">{{citation
 | last1 = Nederhof | first1 = Mark-Jan
 | last2 = Satta | first2 = Giorgio
 | contribution = Parsing Non-recursive Context-free Grammars
 | doi = 10.3115/1073083.1073104
 | location = Stroudsburg, PA, USA
 | pages = 112–119
 | publisher = Association for Computational Linguistics
 | title = Proceedings of the 40th Annual Meeting on Association for Computational Linguistics (ACL '02)
 | year = 2002| doi-access = free
 }}.</ref>

===Recursive humor===
Recursion is sometimes used humorously in computer science, programming, philosophy, or mathematics textbooks, generally by giving a [[circular definition]] or [[self-reference]], in which the putative recursive step does not get closer to a base case, but instead leads to an [[infinite regress]]. It is not unusual for such books to include a joke entry in their glossary along the lines of:
:Recursion, ''see Recursion''.<ref name=Hunter>{{cite book|last=Hunter|first=David|title=Essentials of Discrete Mathematics|year=2011|publisher=Jones and Bartlett|pages=494|url=https://books.google.com/books?id=kuwhTxCVovQC&q=recursion+joke|isbn=9781449604424}}</ref>

A variation is found on page 269 in the [[Back-of-the-book index|index]]  of some editions of [[Brian Kernighan]] and [[Dennis Ritchie]]'s book ''[[The C Programming Language]]''; the index entry recursively references itself ("recursion 86, 139, 141, 182, 202, 269"). Early versions of this joke can be found in ''Let's talk Lisp'' by Laurent Siklóssy (published by Prentice Hall PTR on December 1, 1975, with a copyright date of 1976) and in ''Software Tools'' by Kernighan and Plauger (published by Addison-Wesley Professional on January 11, 1976). The joke also appears in ''The UNIX Programming Environment'' by Kernighan and Pike. It did not appear in the first edition of ''The C Programming Language''. The joke is part of the [[functional programming]] folklore and was already widespread in the functional programming community before the publication of the aforementioned books. <ref name="Grainger College">{{cite web |last1=Shaffer |first1=Eric |title=CS 173:Discrete Structures |url=https://courses.engr.illinois.edu/cs173/sp2009/Lectures/lect_19.pdf |publisher=University of Illinois at Urbana-Champaign |access-date=7 July 2023}}</ref><ref name="Columbia University">{{cite web |title=Introduction to Computer Science and Programming in C; Session 8: September 25, 2008 |url=http://www.cs.columbia.edu/~bert/courses/1003/lecture8.pdf |publisher=Columbia University |access-date=7 July 2023}}</ref>

[[File:Toronto recursive history plaque.jpg|thumb|A plaque commemorates the Toronto Recursive History Project of Toronto's Recursive History.]]

Another joke is that "To understand recursion, you must understand recursion."<ref name=Hunter/> In the English-language version of the Google web search engine, when a search for "recursion" is made, the site suggests "Did you mean: ''recursion''."<ref>{{Cite web|url=https://www.google.com/search?q=recursion|title=recursion - Google Search|website=www.google.com|access-date=2019-10-24}}</ref> An alternative form is the following, from [[Andrew Plotkin]]: ''"If you already know what recursion is, just remember the answer. Otherwise, find someone who is standing closer to [[Douglas Hofstadter]] than you are; then ask him or her what recursion is."''

[[Recursive acronym]]s are other examples of recursive humor. [[PHP]], for example, stands for "PHP Hypertext Preprocessor", [[Wine (software)|WINE]] stands for "WINE Is Not an Emulator", [[GNU]] stands for "GNU's not Unix", and [[SPARQL]] denotes the "SPARQL Protocol and RDF Query Language".