Recursion: Difference between revisions

Revision as of 09:29, 14 December 2024

Latest revision as of 06:52, 23 August 2025

(10 intermediate revisions by 10 users not shown)

Line 6:

[[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]] being defined is applied within its own definition. 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]].

Line 50:

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 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 176:

{{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 journal |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 [[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 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}}