Recursion: Difference between revisions

Revision as of 19:20, 30 November 2023

Latest revision as of 06:52, 23 August 2025

(39 intermediate revisions by 26 users not shown)

Line 4:

<!-- Making the Recursion article link to itself will not display correctly, and is considered to break [[WP:ASTONISH]]. The joke itself is already featured in the "Recursive humor" section. See discussion on the talk page. -->

[[File:Droste Cacao Alcalinise blikje, foto4.JPG|thumb|A visual form of recursion known as the [[Droste effect]]. The woman in this image holds an object that contains a smaller image of her holding an identical object, which in turn contains a smaller image of herself holding an identical object, and so forth. 1904 Droste [[hot chocolate|cocoa]] tin, designed by Jan Misset.]]

'''Recursion''' occurs when the definition of a concept or process depends on a simpler or previous version of itself.<ref>{{Cite book |last=Causey |first=Robert L. |url=https://www.worldcat.org/oclc/62093042 |title=Logic, sets, and recursion |date=2006 |publisher=Jones and Bartlett Publishers |isbn=0-7637-3784-4 |edition=2nd|___location=Sudbury, Mass. |oclc=62093042}}</ref> Recursion is used in a variety of disciplines ranging from [[linguistics]] to [[logic]]. The most common application of recursion is in [[mathematics]] and [[computer science]], where a [[function (mathematics)|function]] callsbeing defined is applied within its own itselfdefinition. While this apparently defines an infinite number of instances (function values), it is often done in such a way that no infinite loop or infinite chain of references can occur.

A process that exhibits recursion is ''recursive''. [[Video feedback]] displays recursive images, as does an [[infinity mirror]].

==Formal definitions==

Line 35:

==Informal definition==

[[File:Mixing Sourdough starter into the flour.jpg|thumb|Recently refreshed [[sourdoughSourdough starter]], bubblingbeing throughstirred [[fermentation]]into flour to produce sourdough: the recipe calls for some sourdough left over from the last time the same recipe was made.]]

Recursion is the process a procedure goes through when one of the steps of the procedure involves invoking the procedure itself. A procedure that goes through recursion is said to be 'recursive'.<ref>{{Cite web|url=https://www.merriam-webster.com/dictionary/recursive|title=Definition of RECURSIVE|website=www.merriam-webster.com|language=en|access-date=2019-10-24}}</ref>

Line 45:

When a procedure is thus defined, this immediately creates the possibility of an endless loop; recursion can only be properly used in a definition if the step in question is skipped in certain cases so that the procedure can complete.

But evenEven if it is properly defined, a recursive procedure is not easy for humans to perform, as it requires distinguishing the new from the old, partially executed invocation of the procedure; this requires some administration as to how far various simultaneous instances of the procedures have progressed. For this reason, recursive definitions are very rare in everyday situations.

==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.{{Clarification needed|date=August 2025}}

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.

Line 58:

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

Line 74:

: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.]]

Line 83:

==In mathematics==

[[File:Sierpinski triangle.svg|thumb|250px|The [[SierpinskiSierpiński triangle]]—a confined recursion of triangles that form a fractal]]

===Recursively defined sets===

Line 111:

===Functional recursion===

A [[function (mathematics)|function]] may be recursively defined in terms of itself. A familiar example is the [[Fibonacci number]] sequence: ''F''(''n'') = ''F''(''n'' − 1) + ''F''(''n'' − 2). For such a definition to be useful, it must be reducible to non-recursively defined values: in this case ''F''(0) = 0 and ''F''(1) = 1.

A famous recursive function is the [[Ackermann function]], which, unlike the Fibonacci sequence, cannot be expressed without recursion.{{Citation needed|date=October 2019}}

===Proofs involving recursive definitions===

Line 173 ⟶ 171:

== In the social sciences ==

Authors use the concept of ''recursivity'' to foreground the situation in which specifically ''social'' scientists find themselves when producing knowledge about the world they are always already part of.<ref>{{Cite journal |last=Bourdieu |first=Pierre |year=1992 |title=Double Bind et Conversion |journal=Pour Une Anthropologie Réflexive |publisher=Le Seuil |publication-place=Paris}}</ref><ref>{{Cite book |last=Giddens |first=Anthony |title=Social Theory and Modern Sociology |publisher=Polity Press |year=1987}}</ref> According to Audrey Alejandro, “as social scientists, the recursivity of our condition deals with the fact that we are both subjects (as discourses are the medium through which we analyse) and objects of the academic discourses we produce (as we are social agents belonging to the world we analyse).”<ref name="Alejandro2021">{{Cite journal |last=Alejandro |first=Audrey |date=2021 |title=Reflexive discourse analysis: A methodology for the practice of reflexivity |url=http://journals.sagepub.com/doi/10.1177/1354066120969789 |journal=[[European Journal of International Relations]] |language=en |volume=27 |issue=1 |page=171 |doi=10.1177/1354066120969789 |s2cid=229461433 |issn=1354-0661|doi-access=free }}</ref> From this basis, she identifies in recursivity a fundamental challenge in the production of emancipatory knowledge which calls for the exercise of [[Reflexivity (social theory)|reflexive]] efforts:{{quote|we are socialised into discourses and dispositions produced by the socio-political order we aim to challenge, a socio-political order that we may, therefore, reproduce unconsciously while aiming to do the contrary. The recursivity of our situation as scholars – and, more precisely, the fact that the dispositional tools we use to produce knowledge about the world are themselves produced by this world – both evinces the vital necessity of implementing reflexivity in practice and poses the main challenge in doing so.|Audrey Alejandro| {{Harvp|Alejandro|2021}}}}

==In business==

{{Further information|Management cybernetics}}

Recursion is sometimes referred to in [[management science]] as the process of iterating through levels of abstraction in large business entities.<ref>{{cite webjournal |title=The Canadian Small Business–Bank Interface: A Recursive Model |date=1994 |url=https://journals.sagepub.com/doi/pdf/10.1177/104225879401800401 |publisher=SAGE Journals|doi=10.1177/104225879401800401 |last1=Riding |first1=Allan |last2=Haines |first2=George H. |last3=Thomas |first3=Roland |journal=Entrepreneurship Theory and Practice |volume=18 |issue=4 |pages=5–24 |url-access=subscription }}</ref> A common example is the recursive nature of management [[hierarchy|hierarchies]], ranging from [[line management]] to [[senior management]] via [[middle management]]. It also encompasses the larger issue of [[capital structure]] in [[corporate governance]].<ref>{{cite book |last1=Beer |first1=Stafford |title=Brain Of The Firm |date=1972 |publisher=John Wiley & Sons |isbn=978-0471948391}}</ref>

==In art==

[[File:First matryoshka museum doll open.jpg|thumb|Recursive dolls: the original set of [[Matryoshka doll]]s by [[Vasily Zvyozdochkin|Zvyozdochkin]] and [[Sergey Malyutin|Malyutin]], 1892]]

[[File:PolitticoGiotto. stefaneschi,The Stefaneschi Triptych (verso) c.1330 220x245cm. Pinacoteca, Vatican..jpg|thumb|left|Front face of [[Giotto]]'s ''[[Stefaneschi Triptych]]'', 1320, recursively contains an image of itself (held up by the kneeling figure in the central panel).]]

{{See also|Mathematics and art|Infinity mirror}}

The Russian Doll or [[Matryoshka doll]] is a physical artistic example of the recursive concept.<ref>{{cite web |last1=Tang |first1=Daisy |title=CS240 -- Lecture Notes: Recursion|date=March 2013|publisher=California State Polytechnic University, Pomona |url=http://www.cpp.edu/~ftang/courses/CS240/lectures/recursion.htm|archive-url=https://web.archive.org/web/20180317100946/https://www.cpp.edu/~ftang/courses/CS240/lectures/recursion.htm|archive-date=2018-03-17 |access-date=24 September 2015 |quote=More examples of recursion: Russian Matryoshka dolls. Each doll is made of solid wood or is hollow and contains another Matryoshka doll inside it. }}</ref>

Recursion has been used in paintings since [[Giotto]]'s ''[[Stefaneschi Triptych]]'', made in 1320. Its central panel contains the kneeling figure of Cardinal Stefaneschi, holding up the triptych itself as an offering.<ref>{{cite web |title=Giotto di Bondone and assistants: Stefaneschi triptych |url=http://mv.vatican.va/3_EN/pages/PIN/PIN_Sala02_03.html |publisher=The Vatican |access-date=16 September 2015}}</ref><ref>{{Cite book |title=Physical (A)Causality: Determinism, Randomness and Uncaused Events |url=https://books.google.com/books?id=gxBMDwAAQBAJ&pg=PA12 |first=Karl |last=Svozil |year=2018 |publisher=Springer |pages=12| isbn=9783319708157 }}</ref> This practice is more generally known as the [[Droste effect]], an example of the [[Mise en abyme]] technique.

Line 195 ⟶ 193:

The film ''[[Inception]]'' has colloquialized the appending of the suffix ''[[wiktionary:-ception|-ception]]'' to a noun to jokingly indicate the recursion of something.<ref>{{cite web |title=-ception – The Rice University Neologisms Database |url=http://neologisms.rice.edu/index.php?a=term&d=1&t=17573 |url-status=live |archive-url=https://web.archive.org/web/20170705153941/http://neologisms.rice.edu/index.php?a=term&d=1&t=17573 |archive-date=July 5, 2017 |access-date=December 23, 2016 |publisher=Rice University}}</ref>

== See also ==<!-- Making the Recursion article link to itself will not display correctly, and is considered to break [[WP:ASTONISH]]. The joke itself is already featured in the "Recursive humor" section. See discussion on the talk page. -->

==See also==

* {{Annotated link|Corecursion}}

* {{Annotated link|Course-of-values recursion}}