CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Recursion - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy","wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"2c6d25c5-bbd4-4808-8b32-51b8d3c27ad7","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Recursion","wgTitle":"Recursion","wgCurRevisionId":1279552408,"wgRevisionId":1279552408,"wgArticleId":25407,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description matches Wikidata","Wikipedia pages semi-protected against vandalism","Pages displaying short descriptions of redirect targets via Module:Annotated link","Commons category link from Wikidata","Articles with example C code","Recursion","Theory of computation","Self-reference","Feedback"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Recursion","wgRelevantArticleId":25407,"wgIsProbablyEditable":false,"wgRelevantPageIsProbablyEditable":false,"wgRestrictionEdit":["autoconfirmed"],"wgRestrictionMove":["autoconfirmed"],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":30000,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q179976","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGELevelingUpEnabledForUser":false}; RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","ext.pygments":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","ext.pygments.view","mediawiki.page.media","ext.scribunto.logs","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.quicksurveys.init","ext.growthExperiments.SuggestedEditSession"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.pygments%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.22"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/d/d9/Droste_Cacao_Alcalinise_blikje%2C_foto4.JPG/1200px-Droste_Cacao_Alcalinise_blikje%2C_foto4.JPG"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="1597"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/d/d9/Droste_Cacao_Alcalinise_blikje%2C_foto4.JPG/800px-Droste_Cacao_Alcalinise_blikje%2C_foto4.JPG"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="1065"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/d/d9/Droste_Cacao_Alcalinise_blikje%2C_foto4.JPG/640px-Droste_Cacao_Alcalinise_blikje%2C_foto4.JPG"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="852"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Recursion - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Recursion"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Recursion"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Recursion rootpage-Recursion skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" title="Main menu" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li><li id="n-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages"><span>Special pages</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Recursion" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Recursion" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Recursion" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Recursion" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Formal_definitions" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Formal_definitions"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Formal definitions</span> </div> </a> <ul id="toc-Formal_definitions-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Informal_definition" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Informal_definition"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Informal definition</span> </div> </a> <ul id="toc-Informal_definition-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-In_language" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#In_language"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>In language</span> </div> </a> <button aria-controls="toc-In_language-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle In language subsection</span> </button> <ul id="toc-In_language-sublist" class="vector-toc-list"> <li id="toc-Recursive_humor" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Recursive_humor"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>Recursive humor</span> </div> </a> <ul id="toc-Recursive_humor-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-In_mathematics" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#In_mathematics"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>In mathematics</span> </div> </a> <button aria-controls="toc-In_mathematics-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle In mathematics subsection</span> </button> <ul id="toc-In_mathematics-sublist" class="vector-toc-list"> <li id="toc-Recursively_defined_sets" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Recursively_defined_sets"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1</span> <span>Recursively defined sets</span> </div> </a> <ul id="toc-Recursively_defined_sets-sublist" class="vector-toc-list"> <li id="toc-Example:_the_natural_numbers" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Example:_the_natural_numbers"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1.1</span> <span>Example: the natural numbers</span> </div> </a> <ul id="toc-Example:_the_natural_numbers-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Example:_Proof_procedure" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Example:_Proof_procedure"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1.2</span> <span>Example: Proof procedure</span> </div> </a> <ul id="toc-Example:_Proof_procedure-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Finite_subdivision_rules" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Finite_subdivision_rules"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.2</span> <span>Finite subdivision rules</span> </div> </a> <ul id="toc-Finite_subdivision_rules-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Functional_recursion" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Functional_recursion"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.3</span> <span>Functional recursion</span> </div> </a> <ul id="toc-Functional_recursion-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Proofs_involving_recursive_definitions" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Proofs_involving_recursive_definitions"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.4</span> <span>Proofs involving recursive definitions</span> </div> </a> <ul id="toc-Proofs_involving_recursive_definitions-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Recursive_optimization" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Recursive_optimization"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.5</span> <span>Recursive optimization</span> </div> </a> <ul id="toc-Recursive_optimization-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-The_recursion_theorem" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#The_recursion_theorem"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.6</span> <span>The recursion theorem</span> </div> </a> <ul id="toc-The_recursion_theorem-sublist" class="vector-toc-list"> <li id="toc-Proof_of_uniqueness" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Proof_of_uniqueness"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.6.1</span> <span>Proof of uniqueness</span> </div> </a> <ul id="toc-Proof_of_uniqueness-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> </ul> </li> <li id="toc-In_computer_science" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#In_computer_science"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>In computer science</span> </div> </a> <ul id="toc-In_computer_science-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-In_biology" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#In_biology"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>In biology</span> </div> </a> <ul id="toc-In_biology-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-In_the_social_sciences" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#In_the_social_sciences"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>In the social sciences</span> </div> </a> <ul id="toc-In_the_social_sciences-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-In_business" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#In_business"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>In business</span> </div> </a> <ul id="toc-In_business-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-In_art" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#In_art"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>In art</span> </div> </a> <ul id="toc-In_art-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-In_culture" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#In_culture"> <div class="vector-toc-text"> <span class="vector-toc-numb">10</span> <span>In culture</span> </div> </a> <ul id="toc-In_culture-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">11</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">12</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Bibliography" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Bibliography"> <div class="vector-toc-text"> <span class="vector-toc-numb">13</span> <span>Bibliography</span> </div> </a> <ul id="toc-Bibliography-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">14</span> <span>External links</span> </div> </a> <ul id="toc-External_links-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" title="Table of Contents" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Recursion</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 61 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-61" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">61 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D8%B9%D9%88%D8%AF%D9%8A%D8%A9" title="عودية – Arabic" lang="ar" hreflang="ar" data-title="عودية" data-language-autonym="العربية" data-language-local-name="Arabic" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-az mw-list-item"><a href="https://az.wikipedia.org/wiki/Rekursiya" title="Rekursiya – Azerbaijani" lang="az" hreflang="az" data-title="Rekursiya" data-language-autonym="Azərbaycanca" data-language-local-name="Azerbaijani" class="interlanguage-link-target"><span>Azərbaycanca</span></a></li><li class="interlanguage-link interwiki-bn mw-list-item"><a href="https://bn.wikipedia.org/wiki/%E0%A6%AA%E0%A7%81%E0%A6%A8%E0%A6%B0%E0%A6%BE%E0%A6%AC%E0%A7%83%E0%A6%A4%E0%A7%8D%E0%A6%A4%E0%A6%BF_(%E0%A6%B0%E0%A6%BF%E0%A6%95%E0%A6%BE%E0%A6%B0%E0%A7%8D%E0%A6%B6%E0%A6%A8)" title="পুনরাবৃত্তি (রিকার্শন) – Bangla" lang="bn" hreflang="bn" data-title="পুনরাবৃত্তি (রিকার্শন)" data-language-autonym="বাংলা" data-language-local-name="Bangla" class="interlanguage-link-target"><span>বাংলা</span></a></li><li class="interlanguage-link interwiki-zh-min-nan mw-list-item"><a href="https://zh-min-nan.wikipedia.org/wiki/Ch%C3%A0i-kui" title="Chài-kui – Minnan" lang="nan" hreflang="nan" data-title="Chài-kui" data-language-autonym="閩南語 / Bân-lâm-gú" data-language-local-name="Minnan" class="interlanguage-link-target"><span>閩南語 / Bân-lâm-gú</span></a></li><li class="interlanguage-link interwiki-bg mw-list-item"><a href="https://bg.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F" title="Рекурсия – Bulgarian" lang="bg" hreflang="bg" data-title="Рекурсия" data-language-autonym="Български" data-language-local-name="Bulgarian" class="interlanguage-link-target"><span>Български</span></a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Recursivitat" title="Recursivitat – Catalan" lang="ca" hreflang="ca" data-title="Recursivitat" data-language-autonym="Català" data-language-local-name="Catalan" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/Rekurze" title="Rekurze – Czech" lang="cs" hreflang="cs" data-title="Rekurze" data-language-autonym="Čeština" data-language-local-name="Czech" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-da mw-list-item"><a href="https://da.wikipedia.org/wiki/Rekursion" title="Rekursion – Danish" lang="da" hreflang="da" data-title="Rekursion" data-language-autonym="Dansk" data-language-local-name="Danish" class="interlanguage-link-target"><span>Dansk</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Rekursion" title="Rekursion – German" lang="de" hreflang="de" data-title="Rekursion" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-et mw-list-item"><a href="https://et.wikipedia.org/wiki/Rekursioon" title="Rekursioon – Estonian" lang="et" hreflang="et" data-title="Rekursioon" data-language-autonym="Eesti" data-language-local-name="Estonian" class="interlanguage-link-target"><span>Eesti</span></a></li><li class="interlanguage-link interwiki-el mw-list-item"><a href="https://el.wikipedia.org/wiki/%CE%91%CE%BD%CE%B1%CE%B4%CF%81%CE%BF%CE%BC%CE%AE" title="Αναδρομή – Greek" lang="el" hreflang="el" data-title="Αναδρομή" data-language-autonym="Ελληνικά" data-language-local-name="Greek" class="interlanguage-link-target"><span>Ελληνικά</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Recursi%C3%B3n" title="Recursión – Spanish" lang="es" hreflang="es" data-title="Recursión" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-eo mw-list-item"><a href="https://eo.wikipedia.org/wiki/Rikuro" title="Rikuro – Esperanto" lang="eo" hreflang="eo" data-title="Rikuro" data-language-autonym="Esperanto" data-language-local-name="Esperanto" class="interlanguage-link-target"><span>Esperanto</span></a></li><li class="interlanguage-link interwiki-eu mw-list-item"><a href="https://eu.wikipedia.org/wiki/Errekurtsio" title="Errekurtsio – Basque" lang="eu" hreflang="eu" data-title="Errekurtsio" data-language-autonym="Euskara" data-language-local-name="Basque" class="interlanguage-link-target"><span>Euskara</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%A8%D8%A7%D8%B2%DA%AF%D8%B4%D8%AA" title="بازگشت – Persian" lang="fa" hreflang="fa" data-title="بازگشت" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/R%C3%A9cursivit%C3%A9" title="Récursivité – French" lang="fr" hreflang="fr" data-title="Récursivité" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-gl mw-list-item"><a href="https://gl.wikipedia.org/wiki/Recursividade" title="Recursividade – Galician" lang="gl" hreflang="gl" data-title="Recursividade" data-language-autonym="Galego" data-language-local-name="Galician" class="interlanguage-link-target"><span>Galego</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EC%9E%AC%EA%B7%80" title="재귀 – Korean" lang="ko" hreflang="ko" data-title="재귀" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-hy mw-list-item"><a href="https://hy.wikipedia.org/wiki/%D5%8C%D5%A5%D5%AF%D5%B8%D6%82%D6%80%D5%BD%D5%AB%D5%A1" title="Ռեկուրսիա – Armenian" lang="hy" hreflang="hy" data-title="Ռեկուրսիա" data-language-autonym="Հայերեն" data-language-local-name="Armenian" class="interlanguage-link-target"><span>Հայերեն</span></a></li><li class="interlanguage-link interwiki-hi mw-list-item"><a href="https://hi.wikipedia.org/wiki/%E0%A4%AA%E0%A5%8D%E0%A4%B0%E0%A4%A4%E0%A4%BF%E0%A4%B5%E0%A4%B0%E0%A5%8D%E0%A4%A4%E0%A4%A8" title="प्रतिवर्तन – Hindi" lang="hi" hreflang="hi" data-title="प्रतिवर्तन" data-language-autonym="हिन्दी" data-language-local-name="Hindi" class="interlanguage-link-target"><span>हिन्दी</span></a></li><li class="interlanguage-link interwiki-hr mw-list-item"><a href="https://hr.wikipedia.org/wiki/Rekurzija" title="Rekurzija – Croatian" lang="hr" hreflang="hr" data-title="Rekurzija" data-language-autonym="Hrvatski" data-language-local-name="Croatian" class="interlanguage-link-target"><span>Hrvatski</span></a></li><li class="interlanguage-link interwiki-io mw-list-item"><a href="https://io.wikipedia.org/wiki/Rekurso" title="Rekurso – Ido" lang="io" hreflang="io" data-title="Rekurso" data-language-autonym="Ido" data-language-local-name="Ido" class="interlanguage-link-target"><span>Ido</span></a></li><li class="interlanguage-link interwiki-id mw-list-item"><a href="https://id.wikipedia.org/wiki/Rekursi" title="Rekursi – Indonesian" lang="id" hreflang="id" data-title="Rekursi" data-language-autonym="Bahasa Indonesia" data-language-local-name="Indonesian" class="interlanguage-link-target"><span>Bahasa Indonesia</span></a></li><li class="interlanguage-link interwiki-ia mw-list-item"><a href="https://ia.wikipedia.org/wiki/Recursion" title="Recursion – Interlingua" lang="ia" hreflang="ia" data-title="Recursion" data-language-autonym="Interlingua" data-language-local-name="Interlingua" class="interlanguage-link-target"><span>Interlingua</span></a></li><li class="interlanguage-link interwiki-is mw-list-item"><a href="https://is.wikipedia.org/wiki/Endurkv%C3%A6mt_fall" title="Endurkvæmt fall – Icelandic" lang="is" hreflang="is" data-title="Endurkvæmt fall" data-language-autonym="Íslenska" data-language-local-name="Icelandic" class="interlanguage-link-target"><span>Íslenska</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%A8%D7%A7%D7%95%D7%A8%D7%A1%D7%99%D7%94" title="רקורסיה – Hebrew" lang="he" hreflang="he" data-title="רקורסיה" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-kk mw-list-item"><a href="https://kk.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F" title="Рекурсия – Kazakh" lang="kk" hreflang="kk" data-title="Рекурсия" data-language-autonym="Қазақша" data-language-local-name="Kazakh" class="interlanguage-link-target"><span>Қазақша</span></a></li><li class="interlanguage-link interwiki-lv mw-list-item"><a href="https://lv.wikipedia.org/wiki/Rekursija" title="Rekursija – Latvian" lang="lv" hreflang="lv" data-title="Rekursija" data-language-autonym="Latviešu" data-language-local-name="Latvian" class="interlanguage-link-target"><span>Latviešu</span></a></li><li class="interlanguage-link interwiki-lt mw-list-item"><a href="https://lt.wikipedia.org/wiki/Rekursija" title="Rekursija – Lithuanian" lang="lt" hreflang="lt" data-title="Rekursija" data-language-autonym="Lietuvių" data-language-local-name="Lithuanian" class="interlanguage-link-target"><span>Lietuvių</span></a></li><li class="interlanguage-link interwiki-lmo mw-list-item"><a href="https://lmo.wikipedia.org/wiki/Recorsion" title="Recorsion – Lombard" lang="lmo" hreflang="lmo" data-title="Recorsion" data-language-autonym="Lombard" data-language-local-name="Lombard" class="interlanguage-link-target"><span>Lombard</span></a></li><li class="interlanguage-link interwiki-hu mw-list-item"><a href="https://hu.wikipedia.org/wiki/Rekurzi%C3%B3" title="Rekurzió – Hungarian" lang="hu" hreflang="hu" data-title="Rekurzió" data-language-autonym="Magyar" data-language-local-name="Hungarian" class="interlanguage-link-target"><span>Magyar</span></a></li><li class="interlanguage-link interwiki-ml mw-list-item"><a href="https://ml.wikipedia.org/wiki/%E0%B4%B8%E0%B5%8D%E0%B4%B5%E0%B4%BE%E0%B4%B5%E0%B5%BC%E0%B4%A4%E0%B5%8D%E0%B4%A4%E0%B4%A8%E0%B4%82" title="സ്വാവർത്തനം – Malayalam" lang="ml" hreflang="ml" data-title="സ്വാവർത്തനം" data-language-autonym="മലയാളം" data-language-local-name="Malayalam" class="interlanguage-link-target"><span>മലയാളം</span></a></li><li class="interlanguage-link interwiki-mr mw-list-item"><a href="https://mr.wikipedia.org/wiki/%E0%A4%B8%E0%A5%8D%E0%A4%B5%E0%A4%BE%E0%A4%B5%E0%A4%B0%E0%A5%8D%E0%A4%A4%E0%A4%A8" title="स्वावर्तन – Marathi" lang="mr" hreflang="mr" data-title="स्वावर्तन" data-language-autonym="मराठी" data-language-local-name="Marathi" class="interlanguage-link-target"><span>मराठी</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Recursie" title="Recursie – Dutch" lang="nl" hreflang="nl" data-title="Recursie" data-language-autonym="Nederlands" data-language-local-name="Dutch" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-nds-nl mw-list-item"><a href="https://nds-nl.wikipedia.org/wiki/Rekursie" title="Rekursie – Low Saxon" lang="nds-NL" hreflang="nds-NL" data-title="Rekursie" data-language-autonym="Nedersaksies" data-language-local-name="Low Saxon" class="interlanguage-link-target"><span>Nedersaksies</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E5%86%8D%E5%B8%B0" title="再帰 – Japanese" lang="ja" hreflang="ja" data-title="再帰" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-no mw-list-item"><a href="https://no.wikipedia.org/wiki/Rekursjon" title="Rekursjon – Norwegian Bokmål" lang="nb" hreflang="nb" data-title="Rekursjon" data-language-autonym="Norsk bokmål" data-language-local-name="Norwegian Bokmål" class="interlanguage-link-target"><span>Norsk bokmål</span></a></li><li class="interlanguage-link interwiki-nn mw-list-item"><a href="https://nn.wikipedia.org/wiki/Rekursjon" title="Rekursjon – Norwegian Nynorsk" lang="nn" hreflang="nn" data-title="Rekursjon" data-language-autonym="Norsk nynorsk" data-language-local-name="Norwegian Nynorsk" class="interlanguage-link-target"><span>Norsk nynorsk</span></a></li><li class="interlanguage-link interwiki-uz mw-list-item"><a href="https://uz.wikipedia.org/wiki/Rekursiya" title="Rekursiya – Uzbek" lang="uz" hreflang="uz" data-title="Rekursiya" data-language-autonym="Oʻzbekcha / ўзбекча" data-language-local-name="Uzbek" class="interlanguage-link-target"><span>Oʻzbekcha / ўзбекча</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Rekurencja" title="Rekurencja – Polish" lang="pl" hreflang="pl" data-title="Rekurencja" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Recursividade" title="Recursividade – Portuguese" lang="pt" hreflang="pt" data-title="Recursividade" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ro mw-list-item"><a href="https://ro.wikipedia.org/wiki/Recursivitate" title="Recursivitate – Romanian" lang="ro" hreflang="ro" data-title="Recursivitate" data-language-autonym="Română" data-language-local-name="Romanian" class="interlanguage-link-target"><span>Română</span></a></li><li class="interlanguage-link interwiki-rue mw-list-item"><a href="https://rue.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D0%B7%D1%96%D1%8F" title="Рекурзія – Rusyn" lang="rue" hreflang="rue" data-title="Рекурзія" data-language-autonym="Русиньскый" data-language-local-name="Rusyn" class="interlanguage-link-target"><span>Русиньскый</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F" title="Рекурсия – Russian" lang="ru" hreflang="ru" data-title="Рекурсия" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sa mw-list-item"><a href="https://sa.wikipedia.org/wiki/%E0%A4%AA%E0%A5%81%E0%A4%A8%E0%A4%B0%E0%A5%8D%E0%A4%97%E0%A4%AE%E0%A4%A8%E0%A4%B5%E0%A4%BE%E0%A4%A6" title="पुनर्गमनवाद – Sanskrit" lang="sa" hreflang="sa" data-title="पुनर्गमनवाद" data-language-autonym="संस्कृतम्" data-language-local-name="Sanskrit" class="interlanguage-link-target"><span>संस्कृतम्</span></a></li><li class="interlanguage-link interwiki-simple mw-list-item"><a href="https://simple.wikipedia.org/wiki/Recursion" title="Recursion – Simple English" lang="en-simple" hreflang="en-simple" data-title="Recursion" data-language-autonym="Simple English" data-language-local-name="Simple English" class="interlanguage-link-target"><span>Simple English</span></a></li><li class="interlanguage-link interwiki-sk mw-list-item"><a href="https://sk.wikipedia.org/wiki/Rekurzia_(matematika)" title="Rekurzia (matematika) – Slovak" lang="sk" hreflang="sk" data-title="Rekurzia (matematika)" data-language-autonym="Slovenčina" data-language-local-name="Slovak" class="interlanguage-link-target"><span>Slovenčina</span></a></li><li class="interlanguage-link interwiki-sl mw-list-item"><a href="https://sl.wikipedia.org/wiki/Rekurzija" title="Rekurzija – Slovenian" lang="sl" hreflang="sl" data-title="Rekurzija" data-language-autonym="Slovenščina" data-language-local-name="Slovenian" class="interlanguage-link-target"><span>Slovenščina</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D0%B7%D0%B8%D1%98%D0%B0" title="Рекурзија – Serbian" lang="sr" hreflang="sr" data-title="Рекурзија" data-language-autonym="Српски / srpski" data-language-local-name="Serbian" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-sh mw-list-item"><a href="https://sh.wikipedia.org/wiki/Rekurzija" title="Rekurzija – Serbo-Croatian" lang="sh" hreflang="sh" data-title="Rekurzija" data-language-autonym="Srpskohrvatski / српскохрватски" data-language-local-name="Serbo-Croatian" class="interlanguage-link-target"><span>Srpskohrvatski / српскохрватски</span></a></li><li class="interlanguage-link interwiki-fi mw-list-item"><a href="https://fi.wikipedia.org/wiki/Rekursio" title="Rekursio – Finnish" lang="fi" hreflang="fi" data-title="Rekursio" data-language-autonym="Suomi" data-language-local-name="Finnish" class="interlanguage-link-target"><span>Suomi</span></a></li><li class="interlanguage-link interwiki-sv mw-list-item"><a href="https://sv.wikipedia.org/wiki/Rekursion" title="Rekursion – Swedish" lang="sv" hreflang="sv" data-title="Rekursion" data-language-autonym="Svenska" data-language-local-name="Swedish" class="interlanguage-link-target"><span>Svenska</span></a></li><li class="interlanguage-link interwiki-tl mw-list-item"><a href="https://tl.wikipedia.org/wiki/Rekursiyon" title="Rekursiyon – Tagalog" lang="tl" hreflang="tl" data-title="Rekursiyon" data-language-autonym="Tagalog" data-language-local-name="Tagalog" class="interlanguage-link-target"><span>Tagalog</span></a></li><li class="interlanguage-link interwiki-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B8%81%E0%B8%B2%E0%B8%A3%E0%B9%80%E0%B8%A7%E0%B8%B5%E0%B8%A2%E0%B8%99%E0%B9%80%E0%B8%81%E0%B8%B4%E0%B8%94" title="การเวียนเกิด – Thai" lang="th" hreflang="th" data-title="การเวียนเกิด" data-language-autonym="ไทย" data-language-local-name="Thai" class="interlanguage-link-target"><span>ไทย</span></a></li><li class="interlanguage-link interwiki-tg mw-list-item"><a href="https://tg.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F" title="Рекурсия – Tajik" lang="tg" hreflang="tg" data-title="Рекурсия" data-language-autonym="Тоҷикӣ" data-language-local-name="Tajik" class="interlanguage-link-target"><span>Тоҷикӣ</span></a></li><li class="interlanguage-link interwiki-tr mw-list-item"><a href="https://tr.wikipedia.org/wiki/%C3%96zyineleme" title="Özyineleme – Turkish" lang="tr" hreflang="tr" data-title="Özyineleme" data-language-autonym="Türkçe" data-language-local-name="Turkish" class="interlanguage-link-target"><span>Türkçe</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D1%96%D1%8F" title="Рекурсія – Ukrainian" lang="uk" hreflang="uk" data-title="Рекурсія" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-vi mw-list-item"><a href="https://vi.wikipedia.org/wiki/%C4%90%E1%BB%87_quy" title="Đệ quy – Vietnamese" lang="vi" hreflang="vi" data-title="Đệ quy" data-language-autonym="Tiếng Việt" data-language-local-name="Vietnamese" class="interlanguage-link-target"><span>Tiếng Việt</span></a></li><li class="interlanguage-link interwiki-wuu mw-list-item"><a href="https://wuu.wikipedia.org/wiki/%E9%80%92%E5%BD%92" title="递归 – Wu" lang="wuu" hreflang="wuu" data-title="递归" data-language-autonym="吴语" data-language-local-name="Wu" class="interlanguage-link-target"><span>吴语</span></a></li><li class="interlanguage-link interwiki-zh-yue mw-list-item"><a href="https://zh-yue.wikipedia.org/wiki/%E9%81%9E%E6%AD%B8" title="遞歸 – Cantonese" lang="yue" hreflang="yue" data-title="遞歸" data-language-autonym="粵語" data-language-local-name="Cantonese" class="interlanguage-link-target"><span>粵語</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E9%80%92%E5%BD%92" title="递归 – Chinese" lang="zh" hreflang="zh" data-title="递归" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q179976#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Recursion" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Recursion" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Recursion"><span>Read</span></a></li><li id="ca-viewsource" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Recursion&action=edit" title="This page is protected.
You can view its source [e]" accesskey="e"><span>View source</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Recursion&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Recursion"><span>Read</span></a></li><li id="ca-more-viewsource" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Recursion&action=edit"><span>View source</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Recursion&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Recursion" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Recursion" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Recursion&oldid=1279552408" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Recursion&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Recursion&id=1279552408&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FRecursion"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FRecursion"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Recursion&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Recursion&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:Recursion" hreflang="en"><span>Wikimedia Commons</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q179976" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> <div id="mw-indicator-pp-default" class="mw-indicator"><div class="mw-parser-output"><span typeof="mw:File"><a href="/wiki/Wikipedia:Protection_policy#semi" title="This article is semi-protected due to vandalism"><img alt="Page semi-protected" src="//upload.wikimedia.org/wikipedia/en/thumb/1/1b/Semi-protection-shackle.svg/20px-Semi-protection-shackle.svg.png" decoding="async" width="20" height="20" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/1/1b/Semi-protection-shackle.svg/40px-Semi-protection-shackle.svg.png 1.5x" data-file-width="512" data-file-height="512" /></a></span></div></div> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Process of repeating items in a self-similar way</div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">For other uses, see <a href="/wiki/Recursion_(disambiguation)" class="mw-disambig" title="Recursion (disambiguation)">Recursion (disambiguation)</a>.</div> <p class="mw-empty-elt"> </p> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Droste_Cacao_Alcalinise_blikje,_foto4.JPG" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/d/d9/Droste_Cacao_Alcalinise_blikje%2C_foto4.JPG/220px-Droste_Cacao_Alcalinise_blikje%2C_foto4.JPG" decoding="async" width="220" height="293" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/d/d9/Droste_Cacao_Alcalinise_blikje%2C_foto4.JPG/330px-Droste_Cacao_Alcalinise_blikje%2C_foto4.JPG 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/d/d9/Droste_Cacao_Alcalinise_blikje%2C_foto4.JPG/440px-Droste_Cacao_Alcalinise_blikje%2C_foto4.JPG 2x" data-file-width="2265" data-file-height="3015" /></a><figcaption>A visual form of recursion known as the <a href="/wiki/Droste_effect" title="Droste effect">Droste effect</a>. 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 <a href="/wiki/Hot_chocolate" title="Hot chocolate">cocoa</a> tin, designed by Jan Misset.</figcaption></figure> <p><b>Recursion</b> occurs when the definition of a concept or process depends on a simpler or previous version of itself.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Recursion is used in a variety of disciplines ranging from <a href="/wiki/Linguistics" title="Linguistics">linguistics</a> to <a href="/wiki/Logic" title="Logic">logic</a>. The most common application of recursion is in <a href="/wiki/Mathematics" title="Mathematics">mathematics</a> and <a href="/wiki/Computer_science" title="Computer science">computer science</a>, where a <a href="/wiki/Function_(mathematics)" title="Function (mathematics)">function</a> 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. </p><p>A process that exhibits recursion is <i>recursive</i>. <a href="/wiki/Video_feedback" title="Video feedback">Video feedback</a> displays recursive images, as does an <a href="/wiki/Infinity_mirror" title="Infinity mirror">infinity mirror</a>. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Formal_definitions">Formal definitions</h2></div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Serpiente_alquimica.jpg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/7/71/Serpiente_alquimica.jpg/250px-Serpiente_alquimica.jpg" decoding="async" width="220" height="219" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/71/Serpiente_alquimica.jpg/330px-Serpiente_alquimica.jpg 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/71/Serpiente_alquimica.jpg/500px-Serpiente_alquimica.jpg 2x" data-file-width="625" data-file-height="621" /></a><figcaption><a href="/wiki/Ouroboros" title="Ouroboros">Ouroboros</a>, an ancient symbol depicting a serpent or dragon eating its own tail</figcaption></figure> <p>In mathematics and computer science, a class of objects or methods exhibits recursive behavior when it can be defined by two properties: </p> <ul><li><span class="anchor" id="base_case"></span>A simple <i>base case</i> (or cases) — a terminating scenario that does not use recursion to produce an answer</li> <li><span class="anchor" id="recursive_step"></span>A <i>recursive step</i> — a set of rules that reduces all successive cases toward the base case.</li></ul> <p>For example, the following is a recursive definition of a person's <i>ancestor</i>. One's ancestor is either: </p> <ul><li>One's parent (<i>base case</i>), <i>or</i></li> <li>One's parent's ancestor (<i>recursive step</i>).</li></ul> <p>The <a href="/wiki/Fibonacci_sequence" title="Fibonacci sequence">Fibonacci sequence</a> is another classic example of recursion: </p> <dl><dd><span class="texhtml">Fib(0) = 0</span> as base case 1,</dd></dl> <dl><dd><span class="texhtml">Fib(1) = 1</span> as base case 2,</dd></dl> <dl><dd>For all <a href="/wiki/Integer" title="Integer">integers</a> <span class="texhtml"><i>n</i> > 1</span>, <span class="texhtml">Fib(<i>n</i>) = Fib(<i>n</i> − 1) + Fib(<i>n</i> − 2)</span>.</dd></dl> <p>Many mathematical axioms are based upon recursive rules. For example, the formal definition of the <a href="/wiki/Natural_number" title="Natural number">natural numbers</a> by the <a href="/wiki/Peano_axioms" title="Peano axioms">Peano axioms</a> can be described as: "Zero is a natural number, and each natural number has a successor, which is also a natural number."<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> By this base case and recursive rule, one can generate the set of all natural numbers. </p><p>Other recursively defined mathematical objects include <a href="/wiki/Factorial" title="Factorial">factorials</a>, <a href="/wiki/Function_(mathematics)" title="Function (mathematics)">functions</a> (e.g., <a href="/wiki/Recurrence_relation" title="Recurrence relation">recurrence relations</a>), <a href="/wiki/Set_(mathematics)" title="Set (mathematics)">sets</a> (e.g., <a href="/wiki/Cantor_ternary_set" class="mw-redirect" title="Cantor ternary set">Cantor ternary set</a>), and <a href="/wiki/Fractal" title="Fractal">fractals</a>. </p><p>There are various more tongue-in-cheek definitions of recursion; see <a href="#Recursive_humor">recursive humor</a>. </p> <div class="mw-heading mw-heading2"><h2 id="Informal_definition">Informal definition</h2></div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Mixing_Sourdough_starter_into_the_flour.jpg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/e/e0/Mixing_Sourdough_starter_into_the_flour.jpg/250px-Mixing_Sourdough_starter_into_the_flour.jpg" decoding="async" width="220" height="275" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/e/e0/Mixing_Sourdough_starter_into_the_flour.jpg/330px-Mixing_Sourdough_starter_into_the_flour.jpg 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/e/e0/Mixing_Sourdough_starter_into_the_flour.jpg/500px-Mixing_Sourdough_starter_into_the_flour.jpg 2x" data-file-width="1200" data-file-height="1500" /></a><figcaption><a href="/wiki/Sourdough_starter" class="mw-redirect" title="Sourdough starter">Sourdough starter</a> being stirred into flour to produce sourdough: the recipe calls for some sourdough left over from the last time the same recipe was made.</figcaption></figure> <p>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'.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p><p>To understand recursion, one must recognize the distinction between a procedure and the running of a procedure. A procedure is a set of steps based on a set of rules, while the running of a procedure involves actually following the rules and performing the steps. </p><p>Recursion is related to, but not the same as, a reference within the specification of a procedure to the execution of some other procedure. </p><p>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. </p><p>Even 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. </p> <div class="mw-heading mw-heading2"><h2 id="In_language">In language</h2></div> <p>Linguist <a href="/wiki/Noam_Chomsky" title="Noam Chomsky">Noam Chomsky</a>, 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.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> </p><p>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: <i>Dorothy thinks witches are dangerous</i>, in which the sentence <i>witches are dangerous</i> 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. </p><p>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: <i>Dorothy thinks that Toto suspects that Tin Man said that...</i>. 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.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> Over the years, languages in general have proved amenable to this kind of analysis. </p><p>The generally accepted idea that recursion is an essential property of human language has been challenged by <a href="/wiki/Daniel_Everett" title="Daniel Everett">Daniel Everett</a> on the basis of his claims about the <a href="/wiki/Pirah%C3%A3_language" title="Pirahã language">Pirahã language</a>. Andrew Nevins, David Pesetsky and Cilene Rodrigues are among many who have argued against this.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> Literary <a href="/wiki/Self-reference" title="Self-reference">self-reference</a> can in any case be argued to be different in kind from mathematical or logical recursion.<sup id="cite_ref-Drucker2008_8-0" class="reference"><a href="#cite_note-Drucker2008-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> </p><p>Recursion plays a crucial role not only in syntax, but also in <a href="/wiki/Natural_language_semantics" class="mw-redirect" title="Natural language semantics">natural language semantics</a>. The word <i>and</i>, 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, <i>and</i> 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.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> </p><p>A <a href="/wiki/Recursive_grammar" title="Recursive grammar">recursive grammar</a> is a <a href="/wiki/Formal_grammar" title="Formal grammar">formal grammar</a> that contains recursive <a href="/wiki/Production_(computer_science)" title="Production (computer science)">production rules</a>.<sup id="cite_ref-ns02_10-0" class="reference"><a href="#cite_note-ns02-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Recursive_humor">Recursive humor</h3></div> <p>Recursion is sometimes used humorously in computer science, programming, philosophy, or mathematics textbooks, generally by giving a <a href="/wiki/Circular_definition" title="Circular definition">circular definition</a> or <a href="/wiki/Self-reference" title="Self-reference">self-reference</a>, in which the putative recursive step does not get closer to a base case, but instead leads to an <a href="/wiki/Infinite_regress" title="Infinite regress">infinite regress</a>. It is not unusual for such books to include a joke entry in their glossary along the lines of: </p> <dl><dd>Recursion, <i>see Recursion</i>.<sup id="cite_ref-Hunter_11-0" class="reference"><a href="#cite_note-Hunter-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup></dd></dl> <p>A variation is found on page 269 in the <a href="/wiki/Back-of-the-book_index" class="mw-redirect" title="Back-of-the-book index">index</a> of some editions of <a href="/wiki/Brian_Kernighan" title="Brian Kernighan">Brian Kernighan</a> and <a href="/wiki/Dennis_Ritchie" title="Dennis Ritchie">Dennis Ritchie</a>'s book <i><a href="/wiki/The_C_Programming_Language" title="The C Programming Language">The C Programming Language</a></i>; the index entry recursively references itself ("recursion 86, 139, 141, 182, 202, 269"). Early versions of this joke can be found in <i>Let's talk Lisp</i> by Laurent Siklóssy (published by Prentice Hall PTR on December 1, 1975, with a copyright date of 1976) and in <i>Software Tools</i> by Kernighan and Plauger (published by Addison-Wesley Professional on January 11, 1976). The joke also appears in <i>The UNIX Programming Environment</i> by Kernighan and Pike. It did not appear in the first edition of <i>The C Programming Language</i>. The joke is part of the <a href="/wiki/Functional_programming" title="Functional programming">functional programming</a> folklore and was already widespread in the functional programming community before the publication of the aforementioned books. <sup id="cite_ref-Grainger_College_12-0" class="reference"><a href="#cite_note-Grainger_College-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Columbia_University_13-0" class="reference"><a href="#cite_note-Columbia_University-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> </p> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Toronto_recursive_history_plaque.jpg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/b/b4/Toronto_recursive_history_plaque.jpg/220px-Toronto_recursive_history_plaque.jpg" decoding="async" width="220" height="252" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/b/b4/Toronto_recursive_history_plaque.jpg/330px-Toronto_recursive_history_plaque.jpg 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/b/b4/Toronto_recursive_history_plaque.jpg/440px-Toronto_recursive_history_plaque.jpg 2x" data-file-width="1788" data-file-height="2048" /></a><figcaption>A plaque commemorates the Toronto Recursive History Project of Toronto's Recursive History.</figcaption></figure> <p>Another joke is that "To understand recursion, you must understand recursion."<sup id="cite_ref-Hunter_11-1" class="reference"><a href="#cite_note-Hunter-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> In the English-language version of the Google web search engine, when a search for "recursion" is made, the site suggests "Did you mean: <i>recursion</i>."<sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> An alternative form is the following, from <a href="/wiki/Andrew_Plotkin" title="Andrew Plotkin">Andrew Plotkin</a>: <i>"If you already know what recursion is, just remember the answer. Otherwise, find someone who is standing closer to <a href="/wiki/Douglas_Hofstadter" title="Douglas Hofstadter">Douglas Hofstadter</a> than you are; then ask him or her what recursion is."</i> </p><p><a href="/wiki/Recursive_acronym" title="Recursive acronym">Recursive acronyms</a> are other examples of recursive humor. <a href="/wiki/PHP" title="PHP">PHP</a>, for example, stands for "PHP Hypertext Preprocessor", <a href="/wiki/Wine_(software)" title="Wine (software)">WINE</a> stands for "WINE Is Not an Emulator", <a href="/wiki/GNU" title="GNU">GNU</a> stands for "GNU's not Unix", and <a href="/wiki/SPARQL" title="SPARQL">SPARQL</a> denotes the "SPARQL Protocol and RDF Query Language". </p> <div class="mw-heading mw-heading2"><h2 id="In_mathematics">In mathematics</h2></div> <figure typeof="mw:File/Thumb"><a href="/wiki/File:Sierpinski_triangle.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/4/45/Sierpinski_triangle.svg/250px-Sierpinski_triangle.svg.png" decoding="async" width="250" height="217" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/4/45/Sierpinski_triangle.svg/375px-Sierpinski_triangle.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/4/45/Sierpinski_triangle.svg/500px-Sierpinski_triangle.svg.png 2x" data-file-width="1024" data-file-height="887" /></a><figcaption>The <a href="/wiki/Sierpi%C5%84ski_triangle" title="Sierpiński triangle">Sierpiński triangle</a>—a confined recursion of triangles that form a fractal</figcaption></figure> <div class="mw-heading mw-heading3"><h3 id="Recursively_defined_sets">Recursively defined sets</h3></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951" /><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Recursive_definition" title="Recursive definition">Recursive definition</a></div> <div class="mw-heading mw-heading4"><h4 id="Example:_the_natural_numbers">Example: the natural numbers</h4></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951" /><div role="note" class="hatnote navigation-not-searchable">See also: <a href="/wiki/Closure_(mathematics)" title="Closure (mathematics)">Closure (mathematics)</a></div> <p>The canonical example of a recursively defined set is given by the <a href="/wiki/Natural_numbers" class="mw-redirect" title="Natural numbers">natural numbers</a>: </p> <dl><dd>0 is in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {N} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">N</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {N} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fdf9a96b565ea202d0f4322e9195613fb26a9bed" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \mathbb {N} }" /></span></dd> <dd>if <i>n</i> is in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {N} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">N</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {N} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fdf9a96b565ea202d0f4322e9195613fb26a9bed" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \mathbb {N} }" /></span>, then <i>n</i> + 1 is in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {N} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">N</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {N} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fdf9a96b565ea202d0f4322e9195613fb26a9bed" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \mathbb {N} }" /></span></dd> <dd>The set of natural numbers is the smallest set satisfying the previous two properties.</dd></dl> <p>In mathematical logic, the <a href="/wiki/Peano_axioms" title="Peano axioms">Peano axioms</a> (or Peano postulates or Dedekind–Peano axioms), are axioms for the natural numbers presented in the 19th century by the German mathematician <a href="/wiki/Richard_Dedekind" title="Richard Dedekind">Richard Dedekind</a> and by the Italian mathematician <a href="/wiki/Giuseppe_Peano" title="Giuseppe Peano">Giuseppe Peano</a>. The Peano Axioms define the natural numbers referring to a recursive successor function and addition and multiplication as recursive functions. </p> <div class="mw-heading mw-heading4"><h4 id="Example:_Proof_procedure">Example: Proof procedure</h4></div> <p>Another interesting example is the set of all "provable" propositions in an <a href="/wiki/Axiomatic_system" title="Axiomatic system">axiomatic system</a> that are defined in terms of a <a href="/wiki/Proof_procedure" title="Proof procedure">proof procedure</a> which is inductively (or recursively) defined as follows: </p> <ul><li>If a proposition is an axiom, it is a provable proposition.</li> <li>If a proposition can be derived from true reachable propositions by means of inference rules, it is a provable proposition.</li> <li>The set of provable propositions is the smallest set of propositions satisfying these conditions.</li></ul> <div class="mw-heading mw-heading3"><h3 id="Finite_subdivision_rules">Finite subdivision rules</h3></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951" /><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Finite_subdivision_rule" title="Finite subdivision rule">Finite subdivision rule</a></div> <p>Finite subdivision rules are a geometric form of recursion, which can be used to create fractal-like images. A subdivision rule starts with a collection of polygons labelled by finitely many labels, and then each polygon is subdivided into smaller labelled polygons in a way that depends only on the labels of the original polygon. This process can be iterated. The standard `middle thirds' technique for creating the <a href="/wiki/Cantor_set" title="Cantor set">Cantor set</a> is a subdivision rule, as is <a href="/wiki/Barycentric_subdivision" title="Barycentric subdivision">barycentric subdivision</a>. </p> <div class="mw-heading mw-heading3"><h3 id="Functional_recursion">Functional recursion</h3></div> <p>A <a href="/wiki/Function_(mathematics)" title="Function (mathematics)">function</a> may be recursively defined in terms of itself. A familiar example is the <a href="/wiki/Fibonacci_number" class="mw-redirect" title="Fibonacci number">Fibonacci number</a> sequence: <i>F</i>(<i>n</i>) = <i>F</i>(<i>n</i> − 1) + <i>F</i>(<i>n</i> − 2). For such a definition to be useful, it must be reducible to non-recursively defined values: in this case <i>F</i>(0) = 0 and <i>F</i>(1) = 1. </p> <div class="mw-heading mw-heading3"><h3 id="Proofs_involving_recursive_definitions">Proofs involving recursive definitions</h3></div> <p>Applying the standard technique of <a href="/wiki/Proof_by_cases" class="mw-redirect" title="Proof by cases">proof by cases</a> to recursively defined sets or functions, as in the preceding sections, yields <a href="/wiki/Structural_induction" title="Structural induction">structural induction</a> — a powerful generalization of <a href="/wiki/Mathematical_induction" title="Mathematical induction">mathematical induction</a> widely used to derive proofs in <a href="/wiki/Mathematical_logic" title="Mathematical logic">mathematical logic</a> and computer science. </p> <div class="mw-heading mw-heading3"><h3 id="Recursive_optimization">Recursive optimization</h3></div> <p><a href="/wiki/Dynamic_programming" title="Dynamic programming">Dynamic programming</a> is an approach to <a href="/wiki/Optimization_(mathematics)" class="mw-redirect" title="Optimization (mathematics)">optimization</a> that restates a multiperiod or multistep optimization problem in recursive form. The key result in dynamic programming is the <a href="/wiki/Bellman_equation" title="Bellman equation">Bellman equation</a>, which writes the value of the optimization problem at an earlier time (or earlier step) in terms of its value at a later time (or later step). </p> <div class="mw-heading mw-heading3"><h3 id="The_recursion_theorem">The recursion theorem</h3></div> <p>In <a href="/wiki/Set_theory" title="Set theory">set theory</a>, this is a theorem guaranteeing that recursively defined functions exist. Given a set <span class="texhtml mvar" style="font-style:italic;">X</span>, an element <span class="texhtml mvar" style="font-style:italic;">a</span> of <span class="texhtml mvar" style="font-style:italic;">X</span> and a function <span class="texhtml"><i>f</i>: <i>X</i> → <i>X</i></span>, the theorem states that there is a unique function <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F:\mathbb {N} \to X}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> <mo>:</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">N</mi> </mrow> <mo stretchy="false">→</mo> <mi>X</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F:\mathbb {N} \to X}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/12e26c5d663cc5a24ab3ceef0bf75ad2c7c626e4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.95ex; height:2.176ex;" alt="{\displaystyle F:\mathbb {N} \to X}" /></span> (where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {N} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">N</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {N} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fdf9a96b565ea202d0f4322e9195613fb26a9bed" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \mathbb {N} }" /></span> denotes the set of natural numbers including zero) such that </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(0)=a}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> <mo stretchy="false">(</mo> <mn>0</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mi>a</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F(0)=a}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e13d054d8df6f9f2770997b66344c4f390bae2d4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.041ex; height:2.843ex;" alt="{\displaystyle F(0)=a}" /></span></dd> <dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(n+1)=f(F(n))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mi>F</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F(n+1)=f(F(n))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/872fa88af5e4b3ca934ba4abee41be187e3d3f94" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.079ex; height:2.843ex;" alt="{\displaystyle F(n+1)=f(F(n))}" /></span></dd></dl> <p>for any natural number <span class="texhtml mvar" style="font-style:italic;">n</span>. </p><p>Dedekind was the first to pose the problem of unique definition of set-theoretical functions on <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {N} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">N</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {N} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fdf9a96b565ea202d0f4322e9195613fb26a9bed" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \mathbb {N} }" /></span> by recursion, and gave a sketch of an argument in the 1888 essay "Was sind und was sollen die Zahlen?" <sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading4"><h4 id="Proof_of_uniqueness">Proof of uniqueness</h4></div> <p>Take two functions <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F:\mathbb {N} \to X}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> <mo>:</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">N</mi> </mrow> <mo stretchy="false">→</mo> <mi>X</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F:\mathbb {N} \to X}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/12e26c5d663cc5a24ab3ceef0bf75ad2c7c626e4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.95ex; height:2.176ex;" alt="{\displaystyle F:\mathbb {N} \to X}" /></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G:\mathbb {N} \to X}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>G</mi> <mo>:</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">N</mi> </mrow> <mo stretchy="false">→</mo> <mi>X</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle G:\mathbb {N} \to X}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/23a0594749da30b07c384d71c20068c54f02af5a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:11.036ex; height:2.176ex;" alt="{\displaystyle G:\mathbb {N} \to X}" /></span> such that: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(0)=a}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> <mo stretchy="false">(</mo> <mn>0</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mi>a</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F(0)=a}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e13d054d8df6f9f2770997b66344c4f390bae2d4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.041ex; height:2.843ex;" alt="{\displaystyle F(0)=a}" /></span></dd> <dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G(0)=a}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>G</mi> <mo stretchy="false">(</mo> <mn>0</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mi>a</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle G(0)=a}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1e4144e1a9d47560e0b5930da11b91807bde69f5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.127ex; height:2.843ex;" alt="{\displaystyle G(0)=a}" /></span></dd> <dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(n+1)=f(F(n))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mi>F</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F(n+1)=f(F(n))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/872fa88af5e4b3ca934ba4abee41be187e3d3f94" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.079ex; height:2.843ex;" alt="{\displaystyle F(n+1)=f(F(n))}" /></span></dd> <dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G(n+1)=f(G(n))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>G</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle G(n+1)=f(G(n))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e0c178891ef17320110f41eaeb21ab5307f996a2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.251ex; height:2.843ex;" alt="{\displaystyle G(n+1)=f(G(n))}" /></span></dd></dl> <p>where <span class="texhtml mvar" style="font-style:italic;">a</span> is an element of <span class="texhtml mvar" style="font-style:italic;">X</span>. </p><p>It can be proved by <a href="/wiki/Mathematical_induction" title="Mathematical induction">mathematical induction</a> that <span class="texhtml"><i>F</i>(<i>n</i>) = <i>G</i>(<i>n</i>)</span> for all natural numbers <span class="texhtml mvar" style="font-style:italic;">n</span>: </p> <dl><dd><b>Base Case</b>: <span class="texhtml"><i>F</i>(0) = <i>a</i> = <i>G</i>(0)</span> so the equality holds for <span class="texhtml"><i>n</i> = 0</span>.</dd></dl> <dl><dd><b>Inductive Step</b>: Suppose <span class="texhtml"><i>F</i>(<i>k</i>) = <i>G</i>(<i>k</i>)</span> for some <span class="nowrap"><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\in \mathbb {N} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> <mo>∈</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">N</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k\in \mathbb {N} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2a5bc4b7383031ba693b7433198ead7170954c1d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.73ex; height:2.176ex;" alt="{\displaystyle k\in \mathbb {N} }" /></span>.</span> Then <span class="texhtml"><i>F</i>(<i>k</i> + 1) = <i>f</i>(<i>F</i>(<i>k</i>)) = <i>f</i>(<i>G</i>(<i>k</i>)) = <i>G</i>(<i>k</i> + 1)</span>. <dl><dd>Hence <span class="texhtml"><i>F</i>(<i>k</i>) = <i>G</i>(<i>k</i>)</span> implies <span class="texhtml"><i>F</i>(<i>k</i> + 1) = <i>G</i>(<i>k</i> + 1)</span>.</dd></dl></dd></dl> <p>By induction, <span class="texhtml"><i>F</i>(<i>n</i>) = <i>G</i>(<i>n</i>)</span> for all <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in \mathbb {N} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>∈</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">N</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n\in \mathbb {N} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d059936e77a2d707e9ee0a1d9575a1d693ce5d0b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.913ex; height:2.176ex;" alt="{\displaystyle n\in \mathbb {N} }" /></span>. </p> <div class="mw-heading mw-heading2"><h2 id="In_computer_science">In computer science</h2></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951" /><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Recursion_(computer_science)" title="Recursion (computer science)">Recursion (computer science)</a></div> <p>A common method of simplification is to divide a problem into subproblems of the same type. As a <a href="/wiki/Computer_programming" title="Computer programming">computer programming</a> technique, this is called <a href="/wiki/Divide_and_conquer_algorithm" class="mw-redirect" title="Divide and conquer algorithm">divide and conquer</a> and is key to the design of many important algorithms. Divide and conquer serves as a top-down approach to problem solving, where problems are solved by solving smaller and smaller instances. A contrary approach is <a href="/wiki/Dynamic_programming" title="Dynamic programming">dynamic programming</a>. This approach serves as a bottom-up approach, where problems are solved by solving larger and larger instances, until the desired size is reached. </p><p>A classic example of recursion is the definition of the <a href="/wiki/Factorial" title="Factorial">factorial</a> function, given here in <a href="/wiki/Python_(programming_language)" title="Python (programming language)">Python</a> code: </p> <div class="mw-highlight mw-highlight-lang-python3 mw-content-ltr" dir="ltr"><pre><span></span><span class="k">def</span> <span class="nf">factorial</span><span class="p">(</span><span class="n">n</span><span class="p">):</span> <span class="k">if</span> <span class="n">n</span> <span class="o">></span> <span class="mi">0</span><span class="p">:</span> <span class="k">return</span> <span class="n">n</span> <span class="o">*</span> <span class="n">factorial</span><span class="p">(</span><span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="k">else</span><span class="p">:</span> <span class="k">return</span> <span class="mi">1</span> </pre></div> <p>The function calls itself recursively on a smaller version of the input <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">(n - 1)</code> and multiplies the result of the recursive call by <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">n</code>, until reaching the <a href="/wiki/Base_case_(recursion)" class="mw-redirect" title="Base case (recursion)">base case</a>, analogously to the mathematical definition of factorial. </p><p>Recursion in computer programming is exemplified when a function is defined in terms of simpler, often smaller versions of itself. The solution to the problem is then devised by combining the solutions obtained from the simpler versions of the problem. One example application of recursion is in <a href="/wiki/Parser" class="mw-redirect" title="Parser">parsers</a> for programming languages. The great advantage of recursion is that an infinite set of possible sentences, designs or other data can be defined, parsed or produced by a finite computer program. </p><p><a href="/wiki/Recurrence_relation" title="Recurrence relation">Recurrence relations</a> are equations which define one or more sequences recursively. Some specific kinds of recurrence relation can be "solved" to obtain a non-recursive definition (e.g., a <a href="/wiki/Closed-form_expression" title="Closed-form expression">closed-form expression</a>). </p><p>Use of recursion in an algorithm has both advantages and disadvantages. The main advantage is usually the simplicity of instructions. The main disadvantage is that the memory usage of recursive algorithms may grow very quickly, rendering them impractical for larger instances. </p> <div class="mw-heading mw-heading2"><h2 id="In_biology">In biology</h2></div> <p>Shapes that seem to have been created by recursive processes sometimes appear in plants and animals, such as in branching structures in which one large part branches out into two or more similar smaller parts. One example is <a href="/wiki/Romanesco_broccoli" title="Romanesco broccoli">Romanesco broccoli</a>.<sup id="cite_ref-16" class="reference"><a href="#cite_note-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="In_the_social_sciences">In the social sciences</h2></div><p> Authors use the concept of <i>recursivity</i> to foreground the situation in which specifically <i>social</i> scientists find themselves when producing knowledge about the world they are always already part of.<sup id="cite_ref-17" class="reference"><a href="#cite_note-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-18" class="reference"><a href="#cite_note-18"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup> 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).”<sup id="cite_ref-Alejandro2021_19-0" class="reference"><a href="#cite_note-Alejandro2021-19"><span class="cite-bracket">[</span>19<span class="cite-bracket">]</span></a></sup> From this basis, she identifies in recursivity a fundamental challenge in the production of emancipatory knowledge which calls for the exercise of <a href="/wiki/Reflexivity_(social_theory)" title="Reflexivity (social theory)">reflexive</a> efforts:<style data-mw-deduplicate="TemplateStyles:r1244412712">.mw-parser-output .templatequote{overflow:hidden;margin:1em 0;padding:0 32px}.mw-parser-output .templatequotecite{line-height:1.5em;text-align:left;margin-top:0}@media(min-width:500px){.mw-parser-output .templatequotecite{padding-left:1.6em}}</style></p><blockquote class="templatequote"><p>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.</p><div class="templatequotecite">— <cite>Audrey Alejandro, <a href="#CITEREFAlejandro2021">Alejandro (2021)</a></cite></div></blockquote> <div class="mw-heading mw-heading2"><h2 id="In_business">In business</h2></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951" /><div role="note" class="hatnote navigation-not-searchable">Further information: <a href="/wiki/Management_cybernetics" title="Management cybernetics">Management cybernetics</a></div> <p>Recursion is sometimes referred to in <a href="/wiki/Management_science" title="Management science">management science</a> as the process of iterating through levels of abstraction in large business entities.<sup id="cite_ref-20" class="reference"><a href="#cite_note-20"><span class="cite-bracket">[</span>20<span class="cite-bracket">]</span></a></sup> A common example is the recursive nature of management <a href="/wiki/Hierarchy" title="Hierarchy">hierarchies</a>, ranging from <a href="/wiki/Line_management" title="Line management">line management</a> to <a href="/wiki/Senior_management" title="Senior management">senior management</a> via <a href="/wiki/Middle_management" title="Middle management">middle management</a>. It also encompasses the larger issue of <a href="/wiki/Capital_structure" title="Capital structure">capital structure</a> in <a href="/wiki/Corporate_governance" title="Corporate governance">corporate governance</a>.<sup id="cite_ref-21" class="reference"><a href="#cite_note-21"><span class="cite-bracket">[</span>21<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="In_art">In art</h2></div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:First_matryoshka_museum_doll_open.jpg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/3/3d/First_matryoshka_museum_doll_open.jpg/250px-First_matryoshka_museum_doll_open.jpg" decoding="async" width="220" height="155" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/3/3d/First_matryoshka_museum_doll_open.jpg/330px-First_matryoshka_museum_doll_open.jpg 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/3/3d/First_matryoshka_museum_doll_open.jpg/500px-First_matryoshka_museum_doll_open.jpg 2x" data-file-width="500" data-file-height="352" /></a><figcaption>Recursive dolls: the original set of <a href="/wiki/Matryoshka_doll" title="Matryoshka doll">Matryoshka dolls</a> by <a href="/wiki/Vasily_Zvyozdochkin" title="Vasily Zvyozdochkin">Zvyozdochkin</a> and <a href="/wiki/Sergey_Malyutin" title="Sergey Malyutin">Malyutin</a>, 1892</figcaption></figure> <figure class="mw-default-size mw-halign-left" typeof="mw:File/Thumb"><a href="/wiki/File:Giotto._The_Stefaneschi_Triptych_(verso)_c.1330_220x245cm._Pinacoteca,_Vatican..jpg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/9/93/Giotto._The_Stefaneschi_Triptych_%28verso%29_c.1330_220x245cm._Pinacoteca%2C_Vatican..jpg/250px-Giotto._The_Stefaneschi_Triptych_%28verso%29_c.1330_220x245cm._Pinacoteca%2C_Vatican..jpg" decoding="async" width="220" height="193" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/9/93/Giotto._The_Stefaneschi_Triptych_%28verso%29_c.1330_220x245cm._Pinacoteca%2C_Vatican..jpg/330px-Giotto._The_Stefaneschi_Triptych_%28verso%29_c.1330_220x245cm._Pinacoteca%2C_Vatican..jpg 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/9/93/Giotto._The_Stefaneschi_Triptych_%28verso%29_c.1330_220x245cm._Pinacoteca%2C_Vatican..jpg/500px-Giotto._The_Stefaneschi_Triptych_%28verso%29_c.1330_220x245cm._Pinacoteca%2C_Vatican..jpg 2x" data-file-width="3543" data-file-height="3106" /></a><figcaption>Front face of <a href="/wiki/Giotto" title="Giotto">Giotto</a>'s <i><a href="/wiki/Stefaneschi_Triptych" title="Stefaneschi Triptych">Stefaneschi Triptych</a></i>, 1320, recursively contains an image of itself (held up by the kneeling figure in the central panel).</figcaption></figure> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951" /><div role="note" class="hatnote navigation-not-searchable">See also: <a href="/wiki/Mathematics_and_art" title="Mathematics and art">Mathematics and art</a> and <a href="/wiki/Infinity_mirror" title="Infinity mirror">Infinity mirror</a></div> <p>The <a href="/wiki/Matryoshka_doll" title="Matryoshka doll">Matryoshka doll</a> is a physical artistic example of the recursive concept.<sup id="cite_ref-22" class="reference"><a href="#cite_note-22"><span class="cite-bracket">[</span>22<span class="cite-bracket">]</span></a></sup> </p><p>Recursion has been used in paintings since <a href="/wiki/Giotto" title="Giotto">Giotto</a>'s <i><a href="/wiki/Stefaneschi_Triptych" title="Stefaneschi Triptych">Stefaneschi Triptych</a></i>, made in 1320. Its central panel contains the kneeling figure of Cardinal Stefaneschi, holding up the triptych itself as an offering.<sup id="cite_ref-23" class="reference"><a href="#cite_note-23"><span class="cite-bracket">[</span>23<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-24" class="reference"><a href="#cite_note-24"><span class="cite-bracket">[</span>24<span class="cite-bracket">]</span></a></sup> This practice is more generally known as the <a href="/wiki/Droste_effect" title="Droste effect">Droste effect</a>, an example of the <a href="/wiki/Mise_en_abyme" title="Mise en abyme">Mise en abyme</a> technique. </p><p><a href="/wiki/M._C._Escher" title="M. C. Escher">M. C. Escher</a>'s <i><a href="/wiki/Print_Gallery_(M._C._Escher)" title="Print Gallery (M. C. Escher)">Print Gallery</a></i> (1956) is a print which depicts a distorted city containing a gallery which <a href="/wiki/Recursive" class="mw-redirect" title="Recursive">recursively</a> contains the picture, and so <i><a href="/wiki/Ad_infinitum" title="Ad infinitum">ad infinitum</a></i>.<sup id="cite_ref-25" class="reference"><a href="#cite_note-25"><span class="cite-bracket">[</span>25<span class="cite-bracket">]</span></a></sup> </p> <div style="clear:both;" class=""></div> <div class="mw-heading mw-heading2"><h2 id="In_culture">In culture</h2></div> <p>The film <i><a href="/wiki/Inception" title="Inception">Inception</a></i> has colloquialized the appending of the suffix <i><a href="https://en.wiktionary.org/wiki/-ception" class="extiw" title="wiktionary:-ception">-ception</a></i> to a noun to jokingly indicate the recursion of something.<sup id="cite_ref-26" class="reference"><a href="#cite_note-26"><span class="cite-bracket">[</span>26<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2></div> <ul><li><a href="/wiki/Corecursion" title="Corecursion">Corecursion</a> – Type of algorithm in computer science</li> <li><a href="/wiki/Course-of-values_recursion" title="Course-of-values recursion">Course-of-values recursion</a> – Technique for defining number-theoretic functions by recursion</li> <li><a href="/wiki/Digital_infinity" title="Digital infinity">Digital infinity</a> – Term in theoretical linguistics</li> <li><a href="/wiki/A_Dream_Within_a_Dream_(poem)" class="mw-redirect" title="A Dream Within a Dream (poem)">A Dream Within a Dream (poem)</a> – Poem by Edgar Allan Poe<span style="display:none" class="category-annotation-with-redirected-description">Pages displaying short descriptions of redirect targets</span></li> <li><a href="/wiki/Droste_effect" title="Droste effect">Droste effect</a> – Recursive visual effect</li> <li><a href="/wiki/False_awakening" title="False awakening">False awakening</a> – Vivid and convincing dream about awakening from sleep</li> <li><a href="/wiki/Fixed_point_combinator" class="mw-redirect" title="Fixed point combinator">Fixed point combinator</a> – Higher-order function Y for which Y f = f (Y f)<span style="display:none" class="category-annotation-with-redirected-description">Pages displaying short descriptions of redirect targets</span></li> <li><a href="/wiki/Infinite_compositions_of_analytic_functions" title="Infinite compositions of analytic functions">Infinite compositions of analytic functions</a> – Mathematical theory about infinitely iterated function composition</li> <li><a href="/wiki/Infinite_loop" title="Infinite loop">Infinite loop</a> – Programming idiom</li> <li><a href="/wiki/Infinite_regress" title="Infinite regress">Infinite regress</a> – Philosophical problem</li> <li><a href="/wiki/Infinitism" title="Infinitism">Infinitism</a> – Philosophical view that knowledge may be justified by an infinite chain of reasons</li> <li><a href="/wiki/Infinity_mirror" title="Infinity mirror">Infinity mirror</a> – Parallel or angled mirrors, creating smaller reflections that appear to recede to infinity</li> <li><a href="/wiki/Iterated_function" title="Iterated function">Iterated function</a> – Result of repeatedly applying a mathematical function</li> <li><a href="/wiki/Mathematical_induction" title="Mathematical induction">Mathematical induction</a> – Form of mathematical proof</li> <li><a href="/wiki/Mise_en_abyme" title="Mise en abyme">Mise en abyme</a> – Technique of placing a copy of an image within itself, or a story within a story</li> <li><a href="/wiki/Reentrant_(subroutine)" class="mw-redirect" title="Reentrant (subroutine)">Reentrant (subroutine)</a> – Concept in computer programming<span style="display:none" class="category-annotation-with-redirected-description">Pages displaying short descriptions of redirect targets</span></li> <li><a href="/wiki/Self-reference" title="Self-reference">Self-reference</a> – Sentence, idea or formula that refers to itself</li> <li><a href="/wiki/Spiegel_im_Spiegel" title="Spiegel im Spiegel">Spiegel im Spiegel</a> – 1978 musical composition by Arvo Pärt</li> <li><a href="/wiki/Strange_loop" title="Strange loop">Strange loop</a> – Cyclic structure that goes through several levels in a hierarchical system</li> <li><a href="/wiki/Tail_recursion" class="mw-redirect" title="Tail recursion">Tail recursion</a> – Subroutine call performed as final action of a procedure<span style="display:none" class="category-annotation-with-redirected-description">Pages displaying short descriptions of redirect targets</span></li> <li><a href="/wiki/Tupper%27s_self-referential_formula" title="Tupper's self-referential formula">Tupper's self-referential formula</a> – Formula that visually represents itself when graphed</li> <li><a href="/wiki/Turtles_all_the_way_down" title="Turtles all the way down">Turtles all the way down</a> – Statement of infinite regress</li></ul> <div class="mw-heading mw-heading2"><h2 id="References">References</h2></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap mw-references-columns"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFCausey2006" class="citation book cs1">Causey, Robert L. (2006). <a rel="nofollow" class="external text" href="https://www.worldcat.org/oclc/62093042"><i>Logic, sets, and recursion</i></a> (2nd ed.). Sudbury, Mass.: Jones and Bartlett Publishers. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-7637-3784-4" title="Special:BookSources/0-7637-3784-4"><bdi>0-7637-3784-4</bdi></a>. <a href="/wiki/OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/62093042">62093042</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Logic%2C+sets%2C+and+recursion&rft.place=Sudbury%2C+Mass.&rft.edition=2nd&rft.pub=Jones+and+Bartlett+Publishers&rft.date=2006&rft_id=info%3Aoclcnum%2F62093042&rft.isbn=0-7637-3784-4&rft.aulast=Causey&rft.aufirst=Robert+L.&rft_id=https%3A%2F%2Fwww.worldcat.org%2Foclc%2F62093042&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.britannica.com/science/Peano-axioms">"Peano axioms | mathematics"</a>. <i>Encyclopedia Britannica</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2019-10-24</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=Encyclopedia+Britannica&rft.atitle=Peano+axioms+%7C+mathematics&rft_id=https%3A%2F%2Fwww.britannica.com%2Fscience%2FPeano-axioms&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></span> </li> <li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.merriam-webster.com/dictionary/recursive">"Definition of RECURSIVE"</a>. <i>www.merriam-webster.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2019-10-24</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=www.merriam-webster.com&rft.atitle=Definition+of+RECURSIVE&rft_id=https%3A%2F%2Fwww.merriam-webster.com%2Fdictionary%2Frecursive&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFPinker1994" class="citation book cs1">Pinker, Steven (1994). <i>The Language Instinct</i>. William Morrow.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=The+Language+Instinct&rft.pub=William+Morrow&rft.date=1994&rft.aulast=Pinker&rft.aufirst=Steven&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFPinkerJackendoff2005" class="citation journal cs1">Pinker, Steven; Jackendoff, Ray (2005). "The faculty of language: What's so special about it?". <i>Cognition</i>. <b>95</b> (2): <span class="nowrap">201–</span>236. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.116.7784">10.1.1.116.7784</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.cognition.2004.08.004">10.1016/j.cognition.2004.08.004</a>. <a href="/wiki/PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/15694646">15694646</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1599505">1599505</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Cognition&rft.atitle=The+faculty+of+language%3A+What%27s+so+special+about+it%3F&rft.volume=95&rft.issue=2&rft.pages=%3Cspan+class%3D%22nowrap%22%3E201-%3C%2Fspan%3E236&rft.date=2005&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.116.7784%23id-name%3DCiteSeerX&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A1599505%23id-name%3DS2CID&rft_id=info%3Apmid%2F15694646&rft_id=info%3Adoi%2F10.1016%2Fj.cognition.2004.08.004&rft.aulast=Pinker&rft.aufirst=Steven&rft.au=Jackendoff%2C+Ray&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></span> </li> <li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFNordquist" class="citation web cs1">Nordquist, Richard. <a rel="nofollow" class="external text" href="https://www.thoughtco.com/recursion-grammar-1691901">"What Is Recursion in English Grammar?"</a>. <i>ThoughtCo</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2019-10-24</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=ThoughtCo&rft.atitle=What+Is+Recursion+in+English+Grammar%3F&rft.aulast=Nordquist&rft.aufirst=Richard&rft_id=https%3A%2F%2Fwww.thoughtco.com%2Frecursion-grammar-1691901&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFNevinsPesetskyRodrigues2009" class="citation journal cs1">Nevins, Andrew; Pesetsky, David; Rodrigues, Cilene (2009). <a rel="nofollow" class="external text" href="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">"Evidence and argumentation: A reply to Everett (2009)"</a> <span class="cs1-format">(PDF)</span>. <i>Language</i>. <b>85</b> (3): <span class="nowrap">671–</span>681. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1353%2Flan.0.0140">10.1353/lan.0.0140</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:16915455">16915455</a>. Archived from <a rel="nofollow" class="external text" href="http://web.mit.edu/linguistics/people/faculty/pesetsky/Nevins_Pesetsky_Rodrigues_2_Evidence_and_Argumentation_Reply_to_Everett.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2012-01-06.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Language&rft.atitle=Evidence+and+argumentation%3A+A+reply+to+Everett+%282009%29&rft.volume=85&rft.issue=3&rft.pages=%3Cspan+class%3D%22nowrap%22%3E671-%3C%2Fspan%3E681&rft.date=2009&rft_id=info%3Adoi%2F10.1353%2Flan.0.0140&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A16915455%23id-name%3DS2CID&rft.aulast=Nevins&rft.aufirst=Andrew&rft.au=Pesetsky%2C+David&rft.au=Rodrigues%2C+Cilene&rft_id=http%3A%2F%2Fweb.mit.edu%2Flinguistics%2Fpeople%2Ffaculty%2Fpesetsky%2FNevins_Pesetsky_Rodrigues_2_Evidence_and_Argumentation_Reply_to_Everett.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></span> </li> <li id="cite_note-Drucker2008-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-Drucker2008_8-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFDrucker2008" class="citation book cs1">Drucker, Thomas (4 January 2008). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=R70M4zsVgREC&pg=PA110"><i>Perspectives on the History of Mathematical Logic</i></a>. Springer Science & Business Media. p. 110. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-8176-4768-1" title="Special:BookSources/978-0-8176-4768-1"><bdi>978-0-8176-4768-1</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Perspectives+on+the+History+of+Mathematical+Logic&rft.pages=110&rft.pub=Springer+Science+%26+Business+Media&rft.date=2008-01-04&rft.isbn=978-0-8176-4768-1&rft.aulast=Drucker&rft.aufirst=Thomas&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DR70M4zsVgREC%26pg%3DPA110&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text">Barbara Partee and Mats Rooth. 1983. In Rainer Bäuerle et al., <i>Meaning, Use, and Interpretation of Language</i>. Reprinted in Paul Portner and Barbara Partee, eds. 2002. <i>Formal Semantics: The Essential Readings</i>. Blackwell.</span> </li> <li id="cite_note-ns02-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-ns02_10-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFNederhofSatta2002" class="citation cs2">Nederhof, Mark-Jan; Satta, Giorgio (2002), "Parsing Non-recursive Context-free Grammars", <i>Proceedings of the 40th Annual Meeting on Association for Computational Linguistics (ACL '02)</i>, Stroudsburg, PA, USA: Association for Computational Linguistics, pp. <span class="nowrap">112–</span>119, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.3115%2F1073083.1073104">10.3115/1073083.1073104</a></span></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Parsing+Non-recursive+Context-free+Grammars&rft.btitle=Proceedings+of+the+40th+Annual+Meeting+on+Association+for+Computational+Linguistics+%28ACL+%2702%29&rft.place=Stroudsburg%2C+PA%2C+USA&rft.pages=%3Cspan+class%3D%22nowrap%22%3E112-%3C%2Fspan%3E119&rft.pub=Association+for+Computational+Linguistics&rft.date=2002&rft_id=info%3Adoi%2F10.3115%2F1073083.1073104&rft.aulast=Nederhof&rft.aufirst=Mark-Jan&rft.au=Satta%2C+Giorgio&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span>.</span> </li> <li id="cite_note-Hunter-11"><span class="mw-cite-backlink">^ <a href="#cite_ref-Hunter_11-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Hunter_11-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFHunter2011" class="citation book cs1">Hunter, David (2011). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=kuwhTxCVovQC&q=recursion+joke"><i>Essentials of Discrete Mathematics</i></a>. Jones and Bartlett. p. 494. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9781449604424" title="Special:BookSources/9781449604424"><bdi>9781449604424</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Essentials+of+Discrete+Mathematics&rft.pages=494&rft.pub=Jones+and+Bartlett&rft.date=2011&rft.isbn=9781449604424&rft.aulast=Hunter&rft.aufirst=David&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DkuwhTxCVovQC%26q%3Drecursion%2Bjoke&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></span> </li> <li id="cite_note-Grainger_College-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-Grainger_College_12-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFShaffer" class="citation web cs1">Shaffer, Eric. <a rel="nofollow" class="external text" href="https://courses.engr.illinois.edu/cs173/sp2009/Lectures/lect_19.pdf">"CS 173:Discrete Structures"</a> <span class="cs1-format">(PDF)</span>. University of Illinois at Urbana-Champaign<span class="reference-accessdate">. Retrieved <span class="nowrap">7 July</span> 2023</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=CS+173%3ADiscrete+Structures&rft.pub=University+of+Illinois+at+Urbana-Champaign&rft.aulast=Shaffer&rft.aufirst=Eric&rft_id=https%3A%2F%2Fcourses.engr.illinois.edu%2Fcs173%2Fsp2009%2FLectures%2Flect_19.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></span> </li> <li id="cite_note-Columbia_University-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-Columbia_University_13-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.cs.columbia.edu/~bert/courses/1003/lecture8.pdf">"Introduction to Computer Science and Programming in C; Session 8: September 25, 2008"</a> <span class="cs1-format">(PDF)</span>. Columbia University<span class="reference-accessdate">. Retrieved <span class="nowrap">7 July</span> 2023</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Introduction+to+Computer+Science+and+Programming+in+C%3B+Session+8%3A+September+25%2C+2008&rft.pub=Columbia+University&rft_id=http%3A%2F%2Fwww.cs.columbia.edu%2F~bert%2Fcourses%2F1003%2Flecture8.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></span> </li> <li id="cite_note-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-14">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.google.com/search?q=recursion">"recursion - Google Search"</a>. <i>www.google.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2019-10-24</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=www.google.com&rft.atitle=recursion+-+Google+Search&rft_id=https%3A%2F%2Fwww.google.com%2Fsearch%3Fq%3Drecursion&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></span> </li> <li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text">A. Kanamori, "<a rel="nofollow" class="external text" href="https://math.bu.edu/people/aki/20.pdf">In Praise of Replacement</a>", pp.50--52. Bulletin of Symbolic Logic, vol. 18, no. 1 (2012). Accessed 21 August 2023.</span> </li> <li id="cite_note-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-16">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://twistedsifter.com/2012/12/fractal-cauliflower-romanesco-broccoli/">"Picture of the Day: Fractal Cauliflower"</a>. 28 December 2012<span class="reference-accessdate">. Retrieved <span class="nowrap">19 April</span> 2020</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Picture+of+the+Day%3A+Fractal+Cauliflower&rft.date=2012-12-28&rft_id=https%3A%2F%2Ftwistedsifter.com%2F2012%2F12%2Ffractal-cauliflower-romanesco-broccoli%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></span> </li> <li id="cite_note-17"><span class="mw-cite-backlink"><b><a href="#cite_ref-17">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFBourdieu1992" class="citation journal cs1">Bourdieu, Pierre (1992). "Double Bind et Conversion". <i>Pour Une Anthropologie Réflexive</i>. Paris: Le Seuil.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Pour+Une+Anthropologie+R%C3%A9flexive&rft.atitle=Double+Bind+et+Conversion&rft.date=1992&rft.aulast=Bourdieu&rft.aufirst=Pierre&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></span> </li> <li id="cite_note-18"><span class="mw-cite-backlink"><b><a href="#cite_ref-18">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFGiddens1987" class="citation book cs1">Giddens, Anthony (1987). <i>Social Theory and Modern Sociology</i>. Polity Press.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Social+Theory+and+Modern+Sociology&rft.pub=Polity+Press&rft.date=1987&rft.aulast=Giddens&rft.aufirst=Anthony&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></span> </li> <li id="cite_note-Alejandro2021-19"><span class="mw-cite-backlink"><b><a href="#cite_ref-Alejandro2021_19-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFAlejandro2021" class="citation journal cs1">Alejandro, Audrey (2021). <a rel="nofollow" class="external text" href="https://doi.org/10.1177%2F1354066120969789">"Reflexive discourse analysis: A methodology for the practice of reflexivity"</a>. <i><a href="/wiki/European_Journal_of_International_Relations" title="European Journal of International Relations">European Journal of International Relations</a></i>. <b>27</b> (1): 171. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1177%2F1354066120969789">10.1177/1354066120969789</a></span>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1354-0661">1354-0661</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:229461433">229461433</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=European+Journal+of+International+Relations&rft.atitle=Reflexive+discourse+analysis%3A+A+methodology+for+the+practice+of+reflexivity&rft.volume=27&rft.issue=1&rft.pages=171&rft.date=2021&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A229461433%23id-name%3DS2CID&rft.issn=1354-0661&rft_id=info%3Adoi%2F10.1177%2F1354066120969789&rft.aulast=Alejandro&rft.aufirst=Audrey&rft_id=https%3A%2F%2Fdoi.org%2F10.1177%252F1354066120969789&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></span> </li> <li id="cite_note-20"><span class="mw-cite-backlink"><b><a href="#cite_ref-20">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFRidingHainesThomas1994" class="citation journal cs1">Riding, Allan; Haines, George H.; Thomas, Roland (1994). <a rel="nofollow" class="external text" href="https://journals.sagepub.com/doi/pdf/10.1177/104225879401800401">"The Canadian Small Business–Bank Interface: A Recursive Model"</a>. <i>Entrepreneurship Theory and Practice</i>. <b>18</b> (4). SAGE Journals: <span class="nowrap">5–</span>24. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1177%2F104225879401800401">10.1177/104225879401800401</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Entrepreneurship+Theory+and+Practice&rft.atitle=The+Canadian+Small+Business%E2%80%93Bank+Interface%3A+A+Recursive+Model&rft.volume=18&rft.issue=4&rft.pages=%3Cspan+class%3D%22nowrap%22%3E5-%3C%2Fspan%3E24&rft.date=1994&rft_id=info%3Adoi%2F10.1177%2F104225879401800401&rft.aulast=Riding&rft.aufirst=Allan&rft.au=Haines%2C+George+H.&rft.au=Thomas%2C+Roland&rft_id=https%3A%2F%2Fjournals.sagepub.com%2Fdoi%2Fpdf%2F10.1177%2F104225879401800401&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></span> </li> <li id="cite_note-21"><span class="mw-cite-backlink"><b><a href="#cite_ref-21">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFBeer1972" class="citation book cs1">Beer, Stafford (1972). <i>Brain Of The Firm</i>. John Wiley & Sons. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0471948391" title="Special:BookSources/978-0471948391"><bdi>978-0471948391</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Brain+Of+The+Firm&rft.pub=John+Wiley+%26+Sons&rft.date=1972&rft.isbn=978-0471948391&rft.aulast=Beer&rft.aufirst=Stafford&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></span> </li> <li id="cite_note-22"><span class="mw-cite-backlink"><b><a href="#cite_ref-22">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFTang" class="citation web cs1">Tang, Daisy. <a rel="nofollow" class="external text" href="http://www.cpp.edu/~ftang/courses/CS240/lectures/recursion.htm">"Recursion"</a><span class="reference-accessdate">. Retrieved <span class="nowrap">24 September</span> 2015</span>. <q>More examples of recursion: Russian Matryoshka dolls. Each doll is made of solid wood or is hollow and contains another Matryoshka doll inside it.</q></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Recursion&rft.aulast=Tang&rft.aufirst=Daisy&rft_id=http%3A%2F%2Fwww.cpp.edu%2F~ftang%2Fcourses%2FCS240%2Flectures%2Frecursion.htm&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></span> </li> <li id="cite_note-23"><span class="mw-cite-backlink"><b><a href="#cite_ref-23">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://mv.vatican.va/3_EN/pages/PIN/PIN_Sala02_03.html">"Giotto di Bondone and assistants: Stefaneschi triptych"</a>. The Vatican<span class="reference-accessdate">. Retrieved <span class="nowrap">16 September</span> 2015</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Giotto+di+Bondone+and+assistants%3A+Stefaneschi+triptych&rft.pub=The+Vatican&rft_id=http%3A%2F%2Fmv.vatican.va%2F3_EN%2Fpages%2FPIN%2FPIN_Sala02_03.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></span> </li> <li id="cite_note-24"><span class="mw-cite-backlink"><b><a href="#cite_ref-24">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFSvozil2018" class="citation book cs1">Svozil, Karl (2018). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=gxBMDwAAQBAJ&pg=PA12"><i>Physical (A)Causality: Determinism, Randomness and Uncaused Events</i></a>. Springer. p. 12. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9783319708157" title="Special:BookSources/9783319708157"><bdi>9783319708157</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Physical+%28A%29Causality%3A+Determinism%2C+Randomness+and+Uncaused+Events&rft.pages=12&rft.pub=Springer&rft.date=2018&rft.isbn=9783319708157&rft.aulast=Svozil&rft.aufirst=Karl&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DgxBMDwAAQBAJ%26pg%3DPA12&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></span> </li> <li id="cite_note-25"><span class="mw-cite-backlink"><b><a href="#cite_ref-25">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFCooper2007" class="citation web cs1">Cooper, Jonathan (5 September 2007). <a rel="nofollow" class="external text" href="https://unwrappingart.com/art/art-and-mathematics/">"Art and Mathematics"</a><span class="reference-accessdate">. Retrieved <span class="nowrap">5 July</span> 2020</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Art+and+Mathematics&rft.date=2007-09-05&rft.aulast=Cooper&rft.aufirst=Jonathan&rft_id=https%3A%2F%2Funwrappingart.com%2Fart%2Fart-and-mathematics%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></span> </li> <li id="cite_note-26"><span class="mw-cite-backlink"><b><a href="#cite_ref-26">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://neologisms.rice.edu/index.php?a=term&d=1&t=17573">"-ception – The Rice University Neologisms Database"</a>. Rice University. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170705153941/http://neologisms.rice.edu/index.php?a=term&d=1&t=17573">Archived</a> from the original on July 5, 2017<span class="reference-accessdate">. Retrieved <span class="nowrap">December 23,</span> 2016</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=-ception+%E2%80%93+The+Rice+University+Neologisms+Database&rft.pub=Rice+University&rft_id=http%3A%2F%2Fneologisms.rice.edu%2Findex.php%3Fa%3Dterm%26d%3D1%26t%3D17573&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="Bibliography">Bibliography</h2></div> <style data-mw-deduplicate="TemplateStyles:r1239549316">.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}</style><div class="refbegin" style=""> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFDijkstra1960" class="citation journal cs1"><a href="/wiki/Edsger_W._Dijkstra" title="Edsger W. Dijkstra">Dijkstra, Edsger W.</a> (1960). "Recursive Programming". <i>Numerische Mathematik</i>. <b>2</b> (1): <span class="nowrap">312–</span>318. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01386232">10.1007/BF01386232</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:127891023">127891023</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Numerische+Mathematik&rft.atitle=Recursive+Programming&rft.volume=2&rft.issue=1&rft.pages=%3Cspan+class%3D%22nowrap%22%3E312-%3C%2Fspan%3E318&rft.date=1960&rft_id=info%3Adoi%2F10.1007%2FBF01386232&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A127891023%23id-name%3DS2CID&rft.aulast=Dijkstra&rft.aufirst=Edsger+W.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFJohnsonbaugh,_Richard2004" class="citation book cs1"><a href="/wiki/Richard_Johnsonbaugh" title="Richard Johnsonbaugh">Johnsonbaugh, Richard</a> (2004). <i>Discrete Mathematics</i>. Prentice Hall. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-13-117686-7" title="Special:BookSources/978-0-13-117686-7"><bdi>978-0-13-117686-7</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Discrete+Mathematics&rft.pub=Prentice+Hall&rft.date=2004&rft.isbn=978-0-13-117686-7&rft.au=Johnsonbaugh%2C+Richard&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFHofstadter,_Douglas1999" class="citation book cs1"><a href="/wiki/Douglas_Hofstadter" title="Douglas Hofstadter">Hofstadter, Douglas</a> (1999). <a rel="nofollow" class="external text" href="https://archive.org/details/gdelescherbachet00hofs"><i>Gödel, Escher, Bach: an Eternal Golden Braid</i></a>. Basic Books. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-465-02656-2" title="Special:BookSources/978-0-465-02656-2"><bdi>978-0-465-02656-2</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=G%C3%B6del%2C+Escher%2C+Bach%3A+an+Eternal+Golden+Braid&rft.pub=Basic+Books&rft.date=1999&rft.isbn=978-0-465-02656-2&rft.au=Hofstadter%2C+Douglas&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Fgdelescherbachet00hofs&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFShoenfield,_Joseph_R.2000" class="citation book cs1"><a href="/wiki/Joseph_R._Shoenfield" title="Joseph R. Shoenfield">Shoenfield, Joseph R.</a> (2000). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/recursiontheory0000shoe"><i>Recursion Theory</i></a></span>. A K Peters Ltd. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-56881-149-9" title="Special:BookSources/978-1-56881-149-9"><bdi>978-1-56881-149-9</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Recursion+Theory&rft.pub=A+K+Peters+Ltd&rft.date=2000&rft.isbn=978-1-56881-149-9&rft.au=Shoenfield%2C+Joseph+R.&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Frecursiontheory0000shoe&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFCausey,_Robert_L.2001" class="citation book cs1"><a href="/wiki/Causey,_Robert_L." class="mw-redirect" title="Causey, Robert L.">Causey, Robert L.</a> (2001). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/logicsetsrecursi0000caus"><i>Logic, Sets, and Recursion</i></a></span>. Jones & Bartlett. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-7637-1695-0" title="Special:BookSources/978-0-7637-1695-0"><bdi>978-0-7637-1695-0</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Logic%2C+Sets%2C+and+Recursion&rft.pub=Jones+%26+Bartlett&rft.date=2001&rft.isbn=978-0-7637-1695-0&rft.au=Causey%2C+Robert+L.&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Flogicsetsrecursi0000caus&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFCori,_ReneLascar,_DanielPelletier,_Donald_H.2001" class="citation book cs1">Cori, Rene; Lascar, Daniel; Pelletier, Donald H. (2001). <i>Recursion Theory, Gödel's Theorems, Set Theory, Model Theory</i>. Oxford University Press. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-19-850050-6" title="Special:BookSources/978-0-19-850050-6"><bdi>978-0-19-850050-6</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Recursion+Theory%2C+G%C3%B6del%27s+Theorems%2C+Set+Theory%2C+Model+Theory&rft.pub=Oxford+University+Press&rft.date=2001&rft.isbn=978-0-19-850050-6&rft.au=Cori%2C+Rene&rft.au=Lascar%2C+Daniel&rft.au=Pelletier%2C+Donald+H.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFBarwise,_JonMoss,_Lawrence_S.1996" class="citation book cs1"><a href="/wiki/Jon_Barwise" title="Jon Barwise">Barwise, Jon</a>; Moss, Lawrence S. (1996). <i>Vicious Circles</i>. Stanford Univ Center for the Study of Language and Information. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-19-850050-6" title="Special:BookSources/978-0-19-850050-6"><bdi>978-0-19-850050-6</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Vicious+Circles&rft.pub=Stanford+Univ+Center+for+the+Study+of+Language+and+Information&rft.date=1996&rft.isbn=978-0-19-850050-6&rft.au=Barwise%2C+Jon&rft.au=Moss%2C+Lawrence+S.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span> - offers a treatment of <a href="/wiki/Corecursion" title="Corecursion">corecursion</a>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFRosen,_Kenneth_H.2002" class="citation book cs1">Rosen, Kenneth H. (2002). <i>Discrete Mathematics and Its Applications</i>. McGraw-Hill College. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-07-293033-7" title="Special:BookSources/978-0-07-293033-7"><bdi>978-0-07-293033-7</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Discrete+Mathematics+and+Its+Applications&rft.pub=McGraw-Hill+College&rft.date=2002&rft.isbn=978-0-07-293033-7&rft.au=Rosen%2C+Kenneth+H.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFCormenLeisersonRivestStein2001" class="citation book cs1">Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). <i>Introduction to Algorithms</i>. Mit Pr. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-262-03293-3" title="Special:BookSources/978-0-262-03293-3"><bdi>978-0-262-03293-3</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Introduction+to+Algorithms&rft.pub=Mit+Pr&rft.date=2001&rft.isbn=978-0-262-03293-3&rft.aulast=Cormen&rft.aufirst=Thomas+H.&rft.au=Leiserson%2C+Charles+E.&rft.au=Rivest%2C+Ronald+L.&rft.au=Stein%2C+Clifford&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFKernighan,_B.Ritchie,_D.1988" class="citation book cs1">Kernighan, B.; Ritchie, D. (1988). <a rel="nofollow" class="external text" href="https://archive.org/details/cprogramminglang00bria"><i>The C programming Language</i></a>. Prentice Hall. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-13-110362-7" title="Special:BookSources/978-0-13-110362-7"><bdi>978-0-13-110362-7</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=The+C+programming+Language&rft.pub=Prentice+Hall&rft.date=1988&rft.isbn=978-0-13-110362-7&rft.au=Kernighan%2C+B.&rft.au=Ritchie%2C+D.&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Fcprogramminglang00bria&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFStokey,_NancyRobert_LucasEdward_Prescott1989" class="citation book cs1">Stokey, Nancy; Robert Lucas; Edward Prescott (1989). <i>Recursive Methods in Economic Dynamics</i>. Harvard University Press. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-674-75096-8" title="Special:BookSources/978-0-674-75096-8"><bdi>978-0-674-75096-8</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Recursive+Methods+in+Economic+Dynamics&rft.pub=Harvard+University+Press&rft.date=1989&rft.isbn=978-0-674-75096-8&rft.au=Stokey%2C+Nancy&rft.au=Robert+Lucas&rft.au=Edward+Prescott&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFHungerford1980" class="citation book cs1">Hungerford (1980). <i>Algebra</i>. Springer. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-387-90518-1" title="Special:BookSources/978-0-387-90518-1"><bdi>978-0-387-90518-1</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Algebra&rft.pub=Springer&rft.date=1980&rft.isbn=978-0-387-90518-1&rft.au=Hungerford&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARecursion" class="Z3988"></span>, first chapter on set theory.</li></ul> </div> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div> <style data-mw-deduplicate="TemplateStyles:r1235681985">.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}</style><style data-mw-deduplicate="TemplateStyles:r1237033735">@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}</style><div class="side-box side-box-right plainlinks sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}</style> <div class="side-box-flex"> <div class="side-box-image"><span class="noviewer" typeof="mw:File"><a href="/wiki/File:Commons-logo.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/40px-Commons-logo.svg.png" decoding="async" width="30" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/60px-Commons-logo.svg.png 1.5x" data-file-width="1024" data-file-height="1376" /></a></span></div> <div class="side-box-text plainlist">Wikimedia Commons has media related to <span style="font-weight: bold; font-style: italic;"><a href="https://commons.wikimedia.org/wiki/Category:Recursion" class="extiw" title="commons:Category:Recursion">Recursion</a></span>.</div></div> </div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1235681985" /><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1237033735" /><div class="side-box side-box-right plainlinks sistersitebox"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1126788409" /> <div class="side-box-flex"> <div class="side-box-image"><span class="noviewer" typeof="mw:File"><a href="/wiki/File:Wiktionary-logo-en-v2.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/9/99/Wiktionary-logo-en-v2.svg/40px-Wiktionary-logo-en-v2.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/9/99/Wiktionary-logo-en-v2.svg/60px-Wiktionary-logo-en-v2.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/9/99/Wiktionary-logo-en-v2.svg/120px-Wiktionary-logo-en-v2.svg.png 2x" data-file-width="512" data-file-height="512" /></a></span></div> <div class="side-box-text plainlist">Look up <i><b><a href="https://en.wiktionary.org/wiki/recursion" class="extiw" title="wiktionary:recursion">recursion</a></b></i> or <i><b><a href="https://en.wiktionary.org/wiki/recursivity" class="extiw" title="wiktionary:recursivity">recursivity</a></b></i> in Wiktionary, the free dictionary.</div></div> </div> <ul><li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20050206051223/http://www.freenetpages.co.uk/hp/alan.gauld/tutrecur.htm">Recursion</a> - tutorial by Alan Gauld</li> <li><a rel="nofollow" class="external text" href="http://research.swtch.com/2010/03/zip-files-all-way-down.html">Zip Files All The Way Down</a></li> <li><a rel="nofollow" class="external text" href="http://www.ucl.ac.uk/psychlangsci/staff/linguistics-staff/nevins-publications/npr09b">Nevins, Andrew and David Pesetsky and Cilene Rodrigues. Evidence and Argumentation: A Reply to Everett (2009). Language 85.3: 671--681 (2009)</a></li></ul> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Fractals328" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374" /><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Fractals" title="Template:Fractals"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Fractals" title="Template talk:Fractals"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Fractals" title="Special:EditPage/Template:Fractals"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Fractals328" style="font-size:114%;margin:0 4em"><a href="/wiki/Fractal" title="Fractal">Fractals</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Characteristics</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Fractal_dimension" title="Fractal dimension">Fractal dimensions</a> <ul><li><a href="/wiki/Assouad_dimension" title="Assouad dimension">Assouad</a></li> <li><a href="/wiki/Minkowski%E2%80%93Bouligand_dimension" title="Minkowski–Bouligand dimension">Box-counting</a> <ul><li><a href="/wiki/Higuchi_dimension" title="Higuchi dimension">Higuchi</a></li></ul></li> <li><a href="/wiki/Correlation_dimension" title="Correlation dimension">Correlation</a></li> <li><a href="/wiki/Hausdorff_dimension" title="Hausdorff dimension">Hausdorff</a></li> <li><a href="/wiki/Packing_dimension" title="Packing dimension">Packing</a></li> <li><a href="/wiki/Lebesgue_covering_dimension" title="Lebesgue covering dimension">Topological</a></li></ul></li> <li><a class="mw-selflink selflink">Recursion</a></li> <li><a href="/wiki/Self-similarity" title="Self-similarity">Self-similarity</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Iterated_function_system" title="Iterated function system">Iterated function <br />system</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Barnsley_fern" title="Barnsley fern">Barnsley fern</a></li> <li><a href="/wiki/Cantor_set" title="Cantor set">Cantor set</a></li> <li><a href="/wiki/Koch_snowflake" title="Koch snowflake">Koch snowflake</a></li> <li><a href="/wiki/Menger_sponge" title="Menger sponge">Menger sponge</a></li> <li><a href="/wiki/Sierpi%C5%84ski_carpet" title="Sierpiński carpet">Sierpiński carpet</a></li> <li><a href="/wiki/Sierpi%C5%84ski_triangle" title="Sierpiński triangle">Sierpiński triangle</a></li> <li><a href="/wiki/Apollonian_gasket" title="Apollonian gasket">Apollonian gasket</a></li> <li><a href="/wiki/Fibonacci_word_fractal" title="Fibonacci word fractal">Fibonacci word</a></li> <li><a href="/wiki/Space-filling_curve" title="Space-filling curve">Space-filling curve</a> <ul><li><a href="/wiki/Blancmange_curve" title="Blancmange curve">Blancmange curve</a></li> <li><a href="/wiki/De_Rham_curve" title="De Rham curve">De Rham curve</a> <ul><li><a href="/wiki/Minkowski_sausage" title="Minkowski sausage">Minkowski</a></li></ul></li> <li><a href="/wiki/Dragon_curve" title="Dragon curve">Dragon curve</a></li> <li><a href="/wiki/Hilbert_curve" title="Hilbert curve">Hilbert curve</a></li> <li><a href="/wiki/Koch_snowflake" title="Koch snowflake">Koch curve</a></li> <li><a href="/wiki/L%C3%A9vy_C_curve" title="Lévy C curve">Lévy C curve</a></li> <li><a href="/wiki/Moore_curve" title="Moore curve">Moore curve</a></li> <li><a href="/wiki/Peano_curve" title="Peano curve">Peano curve</a></li> <li><a href="/wiki/Sierpi%C5%84ski_curve" title="Sierpiński curve">Sierpiński curve</a></li> <li><a href="/wiki/Z-order_curve" title="Z-order curve">Z-order curve</a></li></ul></li> <li><a href="/wiki/Fractal_string" title="Fractal string">String</a></li> <li><a href="/wiki/T-square_(fractal)" title="T-square (fractal)">T-square</a></li> <li><a href="/wiki/N-flake" title="N-flake">n-flake</a></li> <li><a href="/wiki/Vicsek_fractal" title="Vicsek fractal">Vicsek fractal</a></li> <li><a href="/wiki/Gosper_curve" title="Gosper curve">Gosper curve</a></li> <li><a href="/wiki/Pythagoras_tree_(fractal)" title="Pythagoras tree (fractal)">Pythagoras tree</a></li> <li><a href="/wiki/Weierstrass_function" title="Weierstrass function">Weierstrass function</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Attractor#Strange_attractor" title="Attractor">Strange attractor</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Multifractal_system" title="Multifractal system">Multifractal system</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/L-system" title="L-system">L-system</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Fractal_canopy" title="Fractal canopy">Fractal canopy</a></li> <li><a href="/wiki/Space-filling_curve" title="Space-filling curve">Space-filling curve</a> <ul><li><a href="/wiki/H_tree" title="H tree">H tree</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Fractal#Common_techniques_for_generating_fractals" title="Fractal">Escape-time <br />fractals</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Burning_Ship_fractal" title="Burning Ship fractal">Burning Ship fractal</a></li> <li><a href="/wiki/Julia_set" title="Julia set">Julia set</a> <ul><li><a href="/wiki/Filled_Julia_set" title="Filled Julia set">Filled</a></li> <li><a href="/wiki/Newton_fractal" title="Newton fractal">Newton fractal</a></li> <li><a href="/wiki/Douady_rabbit" title="Douady rabbit">Douady rabbit</a></li></ul></li> <li><a href="/wiki/Lyapunov_fractal" title="Lyapunov fractal">Lyapunov fractal</a></li> <li><a href="/wiki/Mandelbrot_set" title="Mandelbrot set">Mandelbrot set</a> <ul><li><a href="/wiki/Misiurewicz_point" title="Misiurewicz point">Misiurewicz point</a></li></ul></li> <li><a href="/wiki/Multibrot_set" title="Multibrot set">Multibrot set</a></li> <li><a href="/wiki/Newton_fractal" title="Newton fractal">Newton fractal</a></li> <li><a href="/wiki/Tricorn_(mathematics)" title="Tricorn (mathematics)">Tricorn</a></li> <li><a href="/wiki/Mandelbox" title="Mandelbox">Mandelbox</a></li> <li><a href="/wiki/Mandelbulb" title="Mandelbulb">Mandelbulb</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Rendering_(computer_graphics)" title="Rendering (computer graphics)">Rendering</a> techniques</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Buddhabrot" title="Buddhabrot">Buddhabrot</a></li> <li><a href="/wiki/Orbit_trap" title="Orbit trap">Orbit trap</a></li> <li><a href="/wiki/Pickover_stalk" title="Pickover stalk">Pickover stalk</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Chaos_game" title="Chaos game">Random</a> fractals</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Brownian_motion" title="Brownian motion">Brownian motion</a> <ul><li><a href="/wiki/Diffusion-limited_aggregation" title="Diffusion-limited aggregation">Brownian tree</a></li> <li><a href="/wiki/Brownian_motor" title="Brownian motor">Brownian motor</a></li></ul></li> <li><a href="/wiki/Fractal_landscape" title="Fractal landscape">Fractal landscape</a></li> <li><a href="/wiki/L%C3%A9vy_flight" title="Lévy flight">Lévy flight</a></li> <li><a href="/wiki/Percolation_theory" title="Percolation theory">Percolation theory</a></li> <li><a href="/wiki/Self-avoiding_walk" title="Self-avoiding walk">Self-avoiding walk</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">People</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Michael_Barnsley" title="Michael Barnsley">Michael Barnsley</a></li> <li><a href="/wiki/Georg_Cantor" title="Georg Cantor">Georg Cantor</a></li> <li><a href="/wiki/Bill_Gosper" title="Bill Gosper">Bill Gosper</a></li> <li><a href="/wiki/Felix_Hausdorff" title="Felix Hausdorff">Felix Hausdorff</a></li> <li><a href="/wiki/Desmond_Paul_Henry" title="Desmond Paul Henry">Desmond Paul Henry</a></li> <li><a href="/wiki/Gaston_Julia" title="Gaston Julia">Gaston Julia</a></li> <li><a href="/wiki/Niels_Fabian_Helge_von_Koch" title="Niels Fabian Helge von Koch">Niels Fabian Helge von Koch</a></li> <li><a href="/wiki/Paul_L%C3%A9vy_(mathematician)" title="Paul Lévy (mathematician)">Paul Lévy</a></li> <li><a href="/wiki/Aleksandr_Lyapunov" title="Aleksandr Lyapunov">Aleksandr Lyapunov</a></li> <li><a href="/wiki/Benoit_Mandelbrot" title="Benoit Mandelbrot">Benoit Mandelbrot</a></li> <li><a href="/wiki/Hamid_Naderi_Yeganeh" title="Hamid Naderi Yeganeh">Hamid Naderi Yeganeh</a></li> <li><a href="/wiki/Lewis_Fry_Richardson" title="Lewis Fry Richardson">Lewis Fry Richardson</a></li> <li><a href="/wiki/Wac%C5%82aw_Sierpi%C5%84ski" title="Wacław Sierpiński">Wacław Sierpiński</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Coastline_paradox" title="Coastline paradox">Coastline paradox</a></li> <li><a href="/wiki/Fractal_art" title="Fractal art">Fractal art</a></li> <li><a href="/wiki/List_of_fractals_by_Hausdorff_dimension" title="List of fractals by Hausdorff dimension">List of fractals by Hausdorff dimension</a></li> <li><i><a href="/wiki/The_Fractal_Geometry_of_Nature" title="The Fractal Geometry of Nature">The Fractal Geometry of Nature</a></i> (1982 book)</li> <li><i><a href="/wiki/The_Beauty_of_Fractals" title="The Beauty of Fractals">The Beauty of Fractals</a></i> (1986 book)</li> <li><i><a href="/wiki/Chaos:_Making_a_New_Science" title="Chaos: Making a New Science">Chaos: Making a New Science</a></i> (1987 book)</li> <li><a href="/wiki/Kaleidoscope" title="Kaleidoscope">Kaleidoscope</a></li> <li><a href="/wiki/Chaos_theory" title="Chaos theory">Chaos theory</a></li></ul> </div></td></tr></tbody></table></div> <div class="navbox-styles"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374" /><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236075235" /></div><div role="navigation" class="navbox" aria-labelledby="Mathematical_logic326" style="padding:3px"><table class="nowraplinks mw-collapsible mw-collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374" /><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1239400231" /><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Mathematical_logic" title="Template:Mathematical logic"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Mathematical_logic" title="Template talk:Mathematical logic"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Mathematical_logic" title="Special:EditPage/Template:Mathematical logic"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Mathematical_logic326" style="font-size:114%;margin:0 4em"><a href="/wiki/Mathematical_logic" title="Mathematical logic">Mathematical logic</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Axiom" title="Axiom">Axiom</a> <ul><li><a href="/wiki/List_of_axioms" title="List of axioms">list</a></li></ul></li> <li><a href="/wiki/Cardinality" title="Cardinality">Cardinality</a></li> <li><a href="/wiki/First-order_logic" title="First-order logic">First-order logic</a></li> <li><a href="/wiki/Formal_proof" title="Formal proof">Formal proof</a></li> <li><a href="/wiki/Formal_semantics_(logic)" class="mw-redirect" title="Formal semantics (logic)">Formal semantics</a></li> <li><a href="/wiki/Foundations_of_mathematics" title="Foundations of mathematics">Foundations of mathematics</a></li> <li><a href="/wiki/Information_theory" title="Information theory">Information theory</a></li> <li><a href="/wiki/Lemma_(mathematics)" title="Lemma (mathematics)">Lemma</a></li> <li><a href="/wiki/Logical_consequence" title="Logical consequence">Logical consequence</a></li> <li><a href="/wiki/Structure_(mathematical_logic)" title="Structure (mathematical logic)">Model</a></li> <li><a href="/wiki/Theorem" title="Theorem">Theorem</a></li> <li><a href="/wiki/Theory_(mathematical_logic)" title="Theory (mathematical logic)">Theory</a></li> <li><a href="/wiki/Type_theory" title="Type theory">Type theory</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Theorems (<a href="/wiki/Category:Theorems_in_the_foundations_of_mathematics" title="Category:Theorems in the foundations of mathematics">list</a>)<br /> and <a href="/wiki/Paradoxes_of_set_theory" title="Paradoxes of set theory">paradoxes</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/G%C3%B6del%27s_completeness_theorem" title="Gödel's completeness theorem">Gödel's completeness</a> and <a href="/wiki/G%C3%B6del%27s_incompleteness_theorems" title="Gödel's incompleteness theorems">incompleteness theorems</a></li> <li><a href="/wiki/Tarski%27s_undefinability_theorem" title="Tarski's undefinability theorem">Tarski's undefinability</a></li> <li><a href="/wiki/Banach%E2%80%93Tarski_paradox" title="Banach–Tarski paradox">Banach–Tarski paradox</a></li> <li>Cantor's <a href="/wiki/Cantor%27s_theorem" title="Cantor's theorem">theorem,</a> <a href="/wiki/Cantor%27s_paradox" title="Cantor's paradox">paradox</a> and <a href="/wiki/Cantor%27s_diagonal_argument" title="Cantor's diagonal argument">diagonal argument</a></li> <li><a href="/wiki/Compactness_theorem" title="Compactness theorem">Compactness</a></li> <li><a href="/wiki/Halting_problem" title="Halting problem">Halting problem</a></li> <li><a href="/wiki/Lindstr%C3%B6m%27s_theorem" title="Lindström's theorem">Lindström's</a></li> <li><a href="/wiki/L%C3%B6wenheim%E2%80%93Skolem_theorem" title="Löwenheim–Skolem theorem">Löwenheim–Skolem</a></li> <li><a href="/wiki/Russell%27s_paradox" title="Russell's paradox">Russell's paradox</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Logic" title="Logic">Logics</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Traditional95" scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Term_logic" title="Term logic">Traditional</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Classical_logic" title="Classical logic">Classical logic</a></li> <li><a href="/wiki/Logical_truth" title="Logical truth">Logical truth</a></li> <li><a href="/wiki/Tautology_(logic)" title="Tautology (logic)">Tautology</a></li> <li><a href="/wiki/Proposition" title="Proposition">Proposition</a></li> <li><a href="/wiki/Inference" title="Inference">Inference</a></li> <li><a href="/wiki/Logical_equivalence" title="Logical equivalence">Logical equivalence</a></li> <li><a href="/wiki/Consistency" title="Consistency">Consistency</a> <ul><li><a href="/wiki/Equiconsistency" title="Equiconsistency">Equiconsistency</a></li></ul></li> <li><a href="/wiki/Argument" title="Argument">Argument</a></li> <li><a href="/wiki/Soundness" title="Soundness">Soundness</a></li> <li><a href="/wiki/Validity_(logic)" title="Validity (logic)">Validity</a></li> <li><a href="/wiki/Syllogism" title="Syllogism">Syllogism</a></li> <li><a href="/wiki/Square_of_opposition" title="Square of opposition">Square of opposition</a></li> <li><a href="/wiki/Venn_diagram" title="Venn diagram">Venn diagram</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Propositional_calculus" title="Propositional calculus">Propositional</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Boolean_algebra" title="Boolean algebra">Boolean algebra</a></li> <li><a href="/wiki/Boolean_function" title="Boolean function">Boolean functions</a></li> <li><a href="/wiki/Logical_connective" title="Logical connective">Logical connectives</a></li> <li><a href="/wiki/Propositional_calculus" title="Propositional calculus">Propositional calculus</a></li> <li><a href="/wiki/Propositional_formula" title="Propositional formula">Propositional formula</a></li> <li><a href="/wiki/Truth_table" title="Truth table">Truth tables</a></li> <li><a href="/wiki/Many-valued_logic" title="Many-valued logic">Many-valued logic</a> <ul><li><a href="/wiki/Three-valued_logic" title="Three-valued logic">3</a></li> <li><a href="/wiki/Finite-valued_logic" title="Finite-valued logic">finite</a></li> <li><a href="/wiki/Infinite-valued_logic" title="Infinite-valued logic">∞</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Predicate_logic" class="mw-redirect" title="Predicate logic">Predicate</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/First-order_logic" title="First-order logic">First-order</a> <ul><li><a href="/wiki/List_of_first-order_theories" title="List of first-order theories"><span style="font-size: 85%;">list</span></a></li></ul></li> <li><a href="/wiki/Second-order_logic" title="Second-order logic">Second-order</a> <ul><li><a href="/wiki/Monadic_second-order_logic" title="Monadic second-order logic">Monadic</a></li></ul></li> <li><a href="/wiki/Higher-order_logic" title="Higher-order logic">Higher-order</a></li> <li><a href="/wiki/Fixed-point_logic" title="Fixed-point logic">Fixed-point</a></li> <li><a href="/wiki/Free_logic" title="Free logic">Free</a></li> <li><a href="/wiki/Quantifier_(logic)" title="Quantifier (logic)">Quantifiers</a></li> <li><a href="/wiki/Predicate_(mathematical_logic)" class="mw-redirect" title="Predicate (mathematical logic)">Predicate</a></li> <li><a href="/wiki/Monadic_predicate_calculus" title="Monadic predicate calculus">Monadic predicate calculus</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Set_theory" title="Set theory">Set theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><td colspan="2" class="navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Zermelo%E2%80%93Fraenkel_set_theory" title="Zermelo–Fraenkel set theory">Set</a> <ul><li><a href="/wiki/Hereditary_set" title="Hereditary set">hereditary</a></li></ul></li> <li><a href="/wiki/Class_(set_theory)" title="Class (set theory)">Class</a></li> <li>(<a href="/wiki/Urelement" title="Urelement">Ur-</a>)<a href="/wiki/Element_(mathematics)" title="Element (mathematics)">Element</a></li> <li><a href="/wiki/Ordinal_number" title="Ordinal number">Ordinal number</a></li> <li><a href="/wiki/Extensionality" title="Extensionality">Extensionality</a></li> <li><a href="/wiki/Forcing_(mathematics)" title="Forcing (mathematics)">Forcing</a></li> <li><a href="/wiki/Relation_(mathematics)" title="Relation (mathematics)">Relation</a> <ul><li><a href="/wiki/Equivalence_relation" title="Equivalence relation">equivalence</a></li> <li><a href="/wiki/Partition_of_a_set" title="Partition of a set">partition</a></li></ul></li> <li>Set operations: <ul><li><a href="/wiki/Intersection_(set_theory)" title="Intersection (set theory)">intersection</a></li> <li><a href="/wiki/Union_(set_theory)" title="Union (set theory)">union</a></li> <li><a href="/wiki/Complement_(set_theory)" title="Complement (set theory)">complement</a></li> <li><a href="/wiki/Cartesian_product" title="Cartesian product">Cartesian product</a></li> <li><a href="/wiki/Power_set" title="Power set">power set</a></li> <li><a href="/wiki/List_of_set_identities_and_relations" title="List of set identities and relations">identities</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Types of <a href="/wiki/Set_(mathematics)" title="Set (mathematics)">sets</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Countable_set" title="Countable set">Countable</a></li> <li><a href="/wiki/Uncountable_set" title="Uncountable set">Uncountable</a></li> <li><a href="/wiki/Empty_set" title="Empty set">Empty</a></li> <li><a href="/wiki/Inhabited_set" title="Inhabited set">Inhabited</a></li> <li><a href="/wiki/Singleton_(mathematics)" title="Singleton (mathematics)">Singleton</a></li> <li><a href="/wiki/Finite_set" title="Finite set">Finite</a></li> <li><a href="/wiki/Infinite_set" title="Infinite set">Infinite</a></li> <li><a href="/wiki/Transitive_set" title="Transitive set">Transitive</a></li> <li><a href="/wiki/Ultrafilter_(set_theory)" class="mw-redirect" title="Ultrafilter (set theory)">Ultrafilter</a></li> <li><a href="/wiki/Recursive_set" class="mw-redirect" title="Recursive set">Recursive</a></li> <li><a href="/wiki/Fuzzy_set" title="Fuzzy set">Fuzzy</a></li> <li><a href="/wiki/Universal_set" title="Universal set">Universal</a></li> <li><a href="/wiki/Universe_(mathematics)" title="Universe (mathematics)">Universe</a> <ul><li><a href="/wiki/Constructible_universe" title="Constructible universe">constructible</a></li> <li><a href="/wiki/Grothendieck_universe" title="Grothendieck universe">Grothendieck</a></li> <li><a href="/wiki/Von_Neumann_universe" title="Von Neumann universe">Von Neumann</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Map_(mathematics)" title="Map (mathematics)">Maps</a> and <a href="/wiki/Cardinality" title="Cardinality">cardinality</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Function_(mathematics)" title="Function (mathematics)">Function</a>/<a href="/wiki/Map_(mathematics)" title="Map (mathematics)">Map</a> <ul><li><a href="/wiki/Domain_of_a_function" title="Domain of a function">domain</a></li> <li><a href="/wiki/Codomain" title="Codomain">codomain</a></li> <li><a href="/wiki/Image_(mathematics)" title="Image (mathematics)">image</a></li></ul></li> <li><a href="/wiki/Injective_function" title="Injective function">In</a>/<a href="/wiki/Surjective_function" title="Surjective function">Sur</a>/<a href="/wiki/Bijection" title="Bijection">Bi</a>-jection</li> <li><a href="/wiki/Schr%C3%B6der%E2%80%93Bernstein_theorem" title="Schröder–Bernstein theorem">Schröder–Bernstein theorem</a></li> <li><a href="/wiki/Isomorphism" title="Isomorphism">Isomorphism</a></li> <li><a href="/wiki/G%C3%B6del_numbering" title="Gödel numbering">Gödel numbering</a></li> <li><a href="/wiki/Enumeration" title="Enumeration">Enumeration</a></li> <li><a href="/wiki/Large_cardinal" title="Large cardinal">Large cardinal</a> <ul><li><a href="/wiki/Inaccessible_cardinal" title="Inaccessible cardinal">inaccessible</a></li></ul></li> <li><a href="/wiki/Aleph_number" title="Aleph number">Aleph number</a></li> <li><a href="/wiki/Operation_(mathematics)" title="Operation (mathematics)">Operation</a> <ul><li><a href="/wiki/Binary_operation" title="Binary operation">binary</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Set theories</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Zermelo%E2%80%93Fraenkel_set_theory" title="Zermelo–Fraenkel set theory">Zermelo–Fraenkel</a> <ul><li><a href="/wiki/Axiom_of_choice" title="Axiom of choice">axiom of choice</a></li> <li><a href="/wiki/Continuum_hypothesis" title="Continuum hypothesis">continuum hypothesis</a></li></ul></li> <li><a href="/wiki/General_set_theory" title="General set theory">General</a></li> <li><a href="/wiki/Kripke%E2%80%93Platek_set_theory" title="Kripke–Platek set theory">Kripke–Platek</a></li> <li><a href="/wiki/Morse%E2%80%93Kelley_set_theory" title="Morse–Kelley set theory">Morse–Kelley</a></li> <li><a href="/wiki/Naive_set_theory" title="Naive set theory">Naive</a></li> <li><a href="/wiki/New_Foundations" title="New Foundations">New Foundations</a></li> <li><a href="/wiki/Tarski%E2%80%93Grothendieck_set_theory" title="Tarski–Grothendieck set theory">Tarski–Grothendieck</a></li> <li><a href="/wiki/Von_Neumann%E2%80%93Bernays%E2%80%93G%C3%B6del_set_theory" title="Von Neumann–Bernays–Gödel set theory">Von Neumann–Bernays–Gödel</a></li> <li><a href="/wiki/Ackermann_set_theory" title="Ackermann set theory">Ackermann</a></li> <li><a href="/wiki/Constructive_set_theory" title="Constructive set theory">Constructive</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Formal_system" title="Formal system">Formal systems</a> (<a href="/wiki/List_of_formal_systems" title="List of formal systems"><span style="font-size: 85%;">list</span></a>),<br /><a href="/wiki/Formal_language" title="Formal language">language</a> and <a href="/wiki/Syntax_(logic)" title="Syntax (logic)">syntax</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><td colspan="2" class="navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Alphabet_(formal_languages)" title="Alphabet (formal languages)">Alphabet</a></li> <li><a href="/wiki/Arity" title="Arity">Arity</a></li> <li><a href="/wiki/Automata_theory" title="Automata theory">Automata</a></li> <li><a href="/wiki/Axiom_schema" title="Axiom schema">Axiom schema</a></li> <li><a href="/wiki/Expression_(mathematics)" title="Expression (mathematics)">Expression</a> <ul><li><a href="/wiki/Ground_expression" title="Ground expression">ground</a></li></ul></li> <li><a href="/wiki/Extension_by_new_constant_and_function_names" title="Extension by new constant and function names">Extension</a> <ul><li><a href="/wiki/Extension_by_definitions" title="Extension by definitions">by definition</a></li> <li><a href="/wiki/Conservative_extension" title="Conservative extension">conservative</a></li></ul></li> <li><a href="/wiki/Finitary_relation" title="Finitary relation">Relation</a></li> <li><a href="/wiki/Formation_rule" title="Formation rule">Formation rule</a></li> <li><a href="/wiki/Formal_grammar" title="Formal grammar">Grammar</a></li> <li><a href="/wiki/Well-formed_formula" title="Well-formed formula">Formula</a> <ul><li><a href="/wiki/Atomic_formula" title="Atomic formula">atomic</a></li> <li><a href="/wiki/Sentence_(mathematical_logic)" title="Sentence (mathematical logic)">closed</a></li> <li><a href="/wiki/Ground_formula" class="mw-redirect" title="Ground formula">ground</a></li> <li><a href="/wiki/Open_formula" title="Open formula">open</a></li></ul></li> <li><a href="/wiki/Free_variables_and_bound_variables" title="Free variables and bound variables">Free/bound variable</a></li> <li><a href="/wiki/Formal_language" title="Formal language">Language</a></li> <li><a href="/wiki/Metalanguage" title="Metalanguage">Metalanguage</a></li> <li><a href="/wiki/Logical_connective" title="Logical connective">Logical connective</a> <ul><li><a href="/wiki/Negation" title="Negation">¬</a></li> <li><a href="/wiki/Logical_disjunction" title="Logical disjunction">∨</a></li> <li><a href="/wiki/Logical_conjunction" title="Logical conjunction">∧</a></li> <li><a href="/wiki/Material_conditional" title="Material conditional">→</a></li> <li><a href="/wiki/Logical_biconditional" title="Logical biconditional">↔</a></li> <li><a href="/wiki/Logical_equality" title="Logical equality">=</a></li></ul></li> <li><a href="/wiki/Predicate_(mathematical_logic)" class="mw-redirect" title="Predicate (mathematical logic)">Predicate</a> <ul><li><a href="/wiki/Functional_predicate" title="Functional predicate">functional</a></li> <li><a href="/wiki/Predicate_variable" title="Predicate variable">variable</a></li> <li><a href="/wiki/Propositional_variable" title="Propositional variable">propositional variable</a></li></ul></li> <li><a href="/wiki/Formal_proof" title="Formal proof">Proof</a></li> <li><a href="/wiki/Quantifier_(logic)" title="Quantifier (logic)">Quantifier</a> <ul><li><a href="/wiki/Existential_quantification" title="Existential quantification">∃</a></li> <li><a href="/wiki/Uniqueness_quantification" title="Uniqueness quantification">!</a></li> <li><a href="/wiki/Universal_quantification" title="Universal quantification">∀</a></li> <li><a href="/wiki/Quantifier_rank" title="Quantifier rank">rank</a></li></ul></li> <li><a href="/wiki/Sentence_(mathematical_logic)" title="Sentence (mathematical logic)">Sentence</a> <ul><li><a href="/wiki/Atomic_sentence" title="Atomic sentence">atomic</a></li> <li><a href="/wiki/Spectrum_of_a_sentence" title="Spectrum of a sentence">spectrum</a></li></ul></li> <li><a href="/wiki/Signature_(logic)" title="Signature (logic)">Signature</a></li> <li><a href="/wiki/String_(formal_languages)" class="mw-redirect" title="String (formal languages)">String</a></li> <li><a href="/wiki/Substitution_(logic)" title="Substitution (logic)">Substitution</a></li> <li><a href="/wiki/Symbol_(formal)" title="Symbol (formal)">Symbol</a> <ul><li><a href="/wiki/Uninterpreted_function" title="Uninterpreted function">function</a></li> <li><a href="/wiki/Logical_constant" title="Logical constant">logical/constant</a></li> <li><a href="/wiki/Non-logical_symbol" title="Non-logical symbol">non-logical</a></li> <li><a href="/wiki/Variable_(mathematics)" title="Variable (mathematics)">variable</a></li></ul></li> <li><a href="/wiki/Term_(logic)" title="Term (logic)">Term</a></li> <li><a href="/wiki/Theory_(mathematical_logic)" title="Theory (mathematical logic)">Theory</a> <ul><li><a href="/wiki/List_of_mathematical_theories" title="List of mathematical theories"><span style="font-size: 85%;">list</span></a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><span class="nowrap">Example <a href="/wiki/Axiomatic_system" title="Axiomatic system">axiomatic<br />systems</a> <span style="font-size: 85%;">(<a href="/wiki/List_of_first-order_theories" title="List of first-order theories">list</a>)</span></span></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li>of <a href="/wiki/True_arithmetic" title="True arithmetic">arithmetic</a>: <ul><li><a href="/wiki/Peano_axioms" title="Peano axioms">Peano</a></li> <li><a href="/wiki/Second-order_arithmetic" title="Second-order arithmetic">second-order</a></li> <li><a href="/wiki/Elementary_function_arithmetic" title="Elementary function arithmetic">elementary function</a></li> <li><a href="/wiki/Primitive_recursive_arithmetic" title="Primitive recursive arithmetic">primitive recursive</a></li> <li><a href="/wiki/Robinson_arithmetic" title="Robinson arithmetic">Robinson</a></li> <li><a href="/wiki/Skolem_arithmetic" title="Skolem arithmetic">Skolem</a></li></ul></li> <li>of the <a href="/wiki/Construction_of_the_real_numbers" title="Construction of the real numbers">real numbers</a> <ul><li><a href="/wiki/Tarski%27s_axiomatization_of_the_reals" title="Tarski's axiomatization of the reals">Tarski's axiomatization</a></li></ul></li> <li>of <a href="/wiki/Axiomatization_of_Boolean_algebras" class="mw-redirect" title="Axiomatization of Boolean algebras">Boolean algebras</a> <ul><li><a href="/wiki/Boolean_algebras_canonically_defined" title="Boolean algebras canonically defined">canonical</a></li> <li><a href="/wiki/Minimal_axioms_for_Boolean_algebra" title="Minimal axioms for Boolean algebra">minimal axioms</a></li></ul></li> <li>of <a href="/wiki/Foundations_of_geometry" title="Foundations of geometry">geometry</a>: <ul><li><a href="/wiki/Euclidean_geometry" title="Euclidean geometry">Euclidean</a>: <ul><li><a href="/wiki/Euclid%27s_Elements" title="Euclid's Elements"><i>Elements</i></a></li> <li><a href="/wiki/Hilbert%27s_axioms" title="Hilbert's axioms">Hilbert's</a></li> <li><a href="/wiki/Tarski%27s_axioms" title="Tarski's axioms">Tarski's</a></li></ul></li> <li><a href="/wiki/Non-Euclidean_geometry" title="Non-Euclidean geometry">non-Euclidean</a></li></ul></li></ul> <ul><li><i><a href="/wiki/Principia_Mathematica" title="Principia Mathematica">Principia Mathematica</a></i></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Proof_theory" title="Proof theory">Proof theory</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Formal_proof" title="Formal proof">Formal proof</a></li> <li><a href="/wiki/Natural_deduction" title="Natural deduction">Natural deduction</a></li> <li><a href="/wiki/Logical_consequence" title="Logical consequence">Logical consequence</a></li> <li><a href="/wiki/Rule_of_inference" title="Rule of inference">Rule of inference</a></li> <li><a href="/wiki/Sequent_calculus" title="Sequent calculus">Sequent calculus</a></li> <li><a href="/wiki/Theorem" title="Theorem">Theorem</a></li> <li><a href="/wiki/Formal_system" title="Formal system">Systems</a> <ul><li><a href="/wiki/Axiomatic_system" title="Axiomatic system">axiomatic</a></li> <li><a href="/wiki/Deductive_system" class="mw-redirect" title="Deductive system">deductive</a></li> <li><a href="/wiki/Hilbert_system" title="Hilbert system">Hilbert</a> <ul><li><a href="/wiki/List_of_Hilbert_systems" class="mw-redirect" title="List of Hilbert systems">list</a></li></ul></li></ul></li> <li><a href="/wiki/Complete_theory" title="Complete theory">Complete theory</a></li> <li><a href="/wiki/Independence_(mathematical_logic)" title="Independence (mathematical logic)">Independence</a> (<a href="/wiki/List_of_statements_independent_of_ZFC" title="List of statements independent of ZFC">from ZFC</a>)</li> <li><a href="/wiki/Proof_of_impossibility" title="Proof of impossibility">Proof of impossibility</a></li> <li><a href="/wiki/Ordinal_analysis" title="Ordinal analysis">Ordinal analysis</a></li> <li><a href="/wiki/Reverse_mathematics" title="Reverse mathematics">Reverse mathematics</a></li> <li><a href="/wiki/Self-verifying_theories" title="Self-verifying theories">Self-verifying theories</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Model_theory" title="Model theory">Model theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Interpretation_(logic)" title="Interpretation (logic)">Interpretation</a> <ul><li><a href="/wiki/Interpretation_function" class="mw-redirect" title="Interpretation function">function</a></li> <li><a href="/wiki/Interpretation_(model_theory)" title="Interpretation (model theory)">of models</a></li></ul></li> <li><a href="/wiki/Structure_(mathematical_logic)" title="Structure (mathematical logic)">Model</a> <ul><li><a href="/wiki/Elementary_equivalence" title="Elementary equivalence">equivalence</a></li> <li><a href="/wiki/Finite_model_theory" title="Finite model theory">finite</a></li> <li><a href="/wiki/Saturated_model" title="Saturated model">saturated</a></li> <li><a href="/wiki/Spectrum_of_a_theory" title="Spectrum of a theory">spectrum</a></li> <li><a href="/wiki/Substructure_(mathematics)" title="Substructure (mathematics)">submodel</a></li></ul></li> <li><a href="/wiki/Non-standard_model" title="Non-standard model">Non-standard model</a> <ul><li><a href="/wiki/Non-standard_model_of_arithmetic" title="Non-standard model of arithmetic">of arithmetic</a></li></ul></li> <li><a href="/wiki/Diagram_(mathematical_logic)" title="Diagram (mathematical logic)">Diagram</a> <ul><li><a href="/wiki/Elementary_diagram" title="Elementary diagram">elementary</a></li></ul></li> <li><a href="/wiki/Categorical_theory" title="Categorical theory">Categorical theory</a></li> <li><a href="/wiki/Model_complete_theory" title="Model complete theory">Model complete theory</a></li> <li><a href="/wiki/Satisfiability" title="Satisfiability">Satisfiability</a></li> <li><a href="/wiki/Semantics_of_logic" title="Semantics of logic">Semantics of logic</a></li> <li><a href="/wiki/Strength_(mathematical_logic)" title="Strength (mathematical logic)">Strength</a></li> <li><a href="/wiki/Theories_of_truth" class="mw-redirect" title="Theories of truth">Theories of truth</a> <ul><li><a href="/wiki/Semantic_theory_of_truth" title="Semantic theory of truth">semantic</a></li> <li><a href="/wiki/Tarski%27s_theory_of_truth" class="mw-redirect" title="Tarski's theory of truth">Tarski's</a></li> <li><a href="/wiki/Kripke%27s_theory_of_truth" class="mw-redirect" title="Kripke's theory of truth">Kripke's</a></li></ul></li> <li><a href="/wiki/T-schema" title="T-schema">T-schema</a></li> <li><a href="/wiki/Transfer_principle" title="Transfer principle">Transfer principle</a></li> <li><a href="/wiki/Truth_predicate" title="Truth predicate">Truth predicate</a></li> <li><a href="/wiki/Truth_value" title="Truth value">Truth value</a></li> <li><a href="/wiki/Type_(model_theory)" title="Type (model theory)">Type</a></li> <li><a href="/wiki/Ultraproduct" title="Ultraproduct">Ultraproduct</a></li> <li><a href="/wiki/Validity_(logic)" title="Validity (logic)">Validity</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Computability_theory" title="Computability theory">Computability theory</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Church_encoding" title="Church encoding">Church encoding</a></li> <li><a href="/wiki/Church%E2%80%93Turing_thesis" title="Church–Turing thesis">Church–Turing thesis</a></li> <li><a href="/wiki/Computably_enumerable_set" title="Computably enumerable set">Computably enumerable</a></li> <li><a href="/wiki/Computable_function" title="Computable function">Computable function</a></li> <li><a href="/wiki/Computable_set" title="Computable set">Computable set</a></li> <li><a href="/wiki/Decision_problem" title="Decision problem">Decision problem</a> <ul><li><a href="/wiki/Decidability_(logic)" title="Decidability (logic)">decidable</a></li> <li><a href="/wiki/Undecidable_problem" title="Undecidable problem">undecidable</a></li> <li><a href="/wiki/P_(complexity)" title="P (complexity)">P</a></li> <li><a href="/wiki/NP_(complexity)" title="NP (complexity)">NP</a></li> <li><a href="/wiki/P_versus_NP_problem" title="P versus NP problem">P versus NP problem</a></li></ul></li> <li><a href="/wiki/Kolmogorov_complexity" title="Kolmogorov complexity">Kolmogorov complexity</a></li> <li><a href="/wiki/Lambda_calculus" title="Lambda calculus">Lambda calculus</a></li> <li><a href="/wiki/Primitive_recursive_function" title="Primitive recursive function">Primitive recursive function</a></li> <li><a class="mw-selflink selflink">Recursion</a></li> <li><a href="/wiki/Recursive_set" class="mw-redirect" title="Recursive set">Recursive set</a></li> <li><a href="/wiki/Turing_machine" title="Turing machine">Turing machine</a></li> <li><a href="/wiki/Type_theory" title="Type theory">Type theory</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Related</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Abstract_logic" title="Abstract logic">Abstract logic</a></li> <li><a href="/wiki/Algebraic_logic" title="Algebraic logic">Algebraic logic</a></li> <li><a href="/wiki/Automated_theorem_proving" title="Automated theorem proving">Automated theorem proving</a></li> <li><a href="/wiki/Category_theory" title="Category theory">Category theory</a></li> <li><a href="/wiki/Concrete_category" title="Concrete category">Concrete</a>/<a href="/wiki/Category_(mathematics)" title="Category (mathematics)">Abstract category</a></li> <li><a href="/wiki/Category_of_sets" title="Category of sets">Category of sets</a></li> <li><a href="/wiki/History_of_logic" title="History of logic">History of logic</a></li> <li><a href="/wiki/History_of_mathematical_logic" class="mw-redirect" title="History of mathematical logic">History of mathematical logic</a> <ul><li><a href="/wiki/Timeline_of_mathematical_logic" title="Timeline of mathematical logic">timeline</a></li></ul></li> <li><a href="/wiki/Logicism" title="Logicism">Logicism</a></li> <li><a href="/wiki/Mathematical_object" title="Mathematical object">Mathematical object</a></li> <li><a href="/wiki/Philosophy_of_mathematics" title="Philosophy of mathematics">Philosophy of mathematics</a></li> <li><a href="/wiki/Supertask" title="Supertask">Supertask</a></li></ul> </div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div><b><span class="nowrap"><span class="noviewer" typeof="mw:File"><a href="/wiki/File:Nuvola_apps_edu_mathematics_blue-p.svg" class="mw-file-description"><img alt="icon" src="//upload.wikimedia.org/wikipedia/commons/thumb/3/3e/Nuvola_apps_edu_mathematics_blue-p.svg/15px-Nuvola_apps_edu_mathematics_blue-p.svg.png" decoding="async" width="15" height="15" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/3/3e/Nuvola_apps_edu_mathematics_blue-p.svg/23px-Nuvola_apps_edu_mathematics_blue-p.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/3/3e/Nuvola_apps_edu_mathematics_blue-p.svg/30px-Nuvola_apps_edu_mathematics_blue-p.svg.png 2x" data-file-width="128" data-file-height="128" /></a></span> </span><a href="/wiki/Portal:Mathematics" title="Portal:Mathematics">Mathematics portal</a></b></div></td></tr></tbody></table></div> <div class="navbox-styles"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374" /><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236075235" /></div><div role="navigation" class="navbox authority-control" aria-label="Navbox390" style="padding:3px"><table class="nowraplinks hlist navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Help:Authority_control" title="Help:Authority control">Authority control databases</a>: National <span class="mw-valign-text-top noprint" typeof="mw:File/Frameless"><a href="https://www.wikidata.org/wiki/Q179976#identifiers" title="Edit this at Wikidata"><img alt="Edit this at Wikidata" src="//upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/10px-OOjs_UI_icon_edit-ltr-progressive.svg.png" decoding="async" width="10" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/15px-OOjs_UI_icon_edit-ltr-progressive.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/20px-OOjs_UI_icon_edit-ltr-progressive.svg.png 2x" data-file-width="20" data-file-height="20" /></a></span></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4191814-9">Germany</a></span></li></ul></div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?useformat=desktop&type=1x1&usesul3=0" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Recursion&oldid=1279552408">https://en.wikipedia.org/w/index.php?title=Recursion&oldid=1279552408</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Recursion" title="Category:Recursion">Recursion</a></li><li><a href="/wiki/Category:Theory_of_computation" title="Category:Theory of computation">Theory of computation</a></li><li><a href="/wiki/Category:Self-reference" title="Category:Self-reference">Self-reference</a></li><li><a href="/wiki/Category:Feedback" title="Category:Feedback">Feedback</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_matches_Wikidata" title="Category:Short description matches Wikidata">Short description matches Wikidata</a></li><li><a href="/wiki/Category:Wikipedia_pages_semi-protected_against_vandalism" title="Category:Wikipedia pages semi-protected against vandalism">Wikipedia pages semi-protected against vandalism</a></li><li><a href="/wiki/Category:Pages_displaying_short_descriptions_of_redirect_targets_via_Module:Annotated_link" title="Category:Pages displaying short descriptions of redirect targets via Module:Annotated link">Pages displaying short descriptions of redirect targets via Module:Annotated link</a></li><li><a href="/wiki/Category:Commons_category_link_from_Wikidata" title="Category:Commons category link from Wikidata">Commons category link from Wikidata</a></li><li><a href="/wiki/Category:Articles_with_example_C_code" title="Category:Articles with example C code">Articles with example C code</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 9 March 2025, at 05:59<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Recursion&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://www.wikimedia.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><picture><source media="(min-width: 500px)" srcset="/static/images/footer/wikimedia-button.svg" width="84" height="29"><img src="/static/images/footer/wikimedia.svg" width="25" height="25" alt="Wikimedia Foundation" lang="en" loading="lazy"></picture></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><picture><source media="(min-width: 500px)" srcset="/w/resources/assets/poweredby_mediawiki.svg" width="88" height="31"><img src="/w/resources/assets/mediawiki_compact.svg" alt="Powered by MediaWiki" lang="en" width="25" height="25" loading="lazy"></picture></a></li> </ul> </footer> </div> </div> </div> <div class="vector-header-container vector-sticky-header-container"> <div id="vector-sticky-header" class="vector-sticky-header"> <div class="vector-sticky-header-start"> <div class="vector-sticky-header-icon-start vector-button-flush-left vector-button-flush-right" aria-hidden="true"> <button class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-sticky-header-search-toggle" tabindex="-1" data-event-name="ui.vector-sticky-search-form.icon"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </button> </div> <div role="search" class="vector-search-box-vue vector-search-box-show-thumbnail vector-search-box"> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail"> <form action="/w/index.php" id="vector-sticky-search-form" class="cdx-search-input cdx-search-input--has-end-button"> <div class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia"> <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <div class="vector-sticky-header-context-bar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-sticky-header-toc" class="vector-dropdown mw-portlet mw-portlet-sticky-header-toc vector-sticky-header-toc vector-button-flush-left" > <input type="checkbox" id="vector-sticky-header-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-sticky-header-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-sticky-header-toc-label" for="vector-sticky-header-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-sticky-header-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div class="vector-sticky-header-context-bar-primary" aria-hidden="true" ><span class="mw-page-title-main">Recursion</span></div> </div> </div> <div class="vector-sticky-header-end" aria-hidden="true"> <div class="vector-sticky-header-icons"> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-talk-sticky-header" tabindex="-1" data-event-name="talk-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbles mw-ui-icon-wikimedia-speechBubbles"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-subject-sticky-header" tabindex="-1" data-event-name="subject-sticky-header"><span class="vector-icon mw-ui-icon-article mw-ui-icon-wikimedia-article"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-history-sticky-header" tabindex="-1" data-event-name="history-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-history mw-ui-icon-wikimedia-wikimedia-history"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only mw-watchlink" id="ca-watchstar-sticky-header" tabindex="-1" data-event-name="watch-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-star mw-ui-icon-wikimedia-wikimedia-star"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-edit-sticky-header" tabindex="-1" data-event-name="wikitext-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-wikiText mw-ui-icon-wikimedia-wikimedia-wikiText"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-ve-edit-sticky-header" tabindex="-1" data-event-name="ve-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-edit mw-ui-icon-wikimedia-wikimedia-edit"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-viewsource-sticky-header" tabindex="-1" data-event-name="ve-edit-protected-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-editLock mw-ui-icon-wikimedia-wikimedia-editLock"></span> <span></span> </a> </div> <div class="vector-sticky-header-buttons"> <button class="cdx-button cdx-button--weight-quiet mw-interlanguage-selector" id="p-lang-btn-sticky-header" tabindex="-1" data-event-name="ui.dropdown-p-lang-btn-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-language mw-ui-icon-wikimedia-wikimedia-language"></span> <span>61 languages</span> </button> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive" id="ca-addsection-sticky-header" tabindex="-1" data-event-name="addsection-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbleAdd-progressive mw-ui-icon-wikimedia-speechBubbleAdd-progressive"></span> <span>Add topic</span> </a> </div> <div class="vector-sticky-header-icon-end"> <div class="vector-user-links"> </div> </div> </div> </div> </div> <div class="mw-portlet mw-portlet-dock-bottom emptyPortlet" id="p-dock-bottom"> <ul> </ul> </div> <script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-5c6f46dcf-n8px7","wgBackendResponseTime":186,"wgPageParseReport":{"limitreport":{"cputime":"0.865","walltime":"1.245","ppvisitednodes":{"value":6786,"limit":1000000},"postexpandincludesize":{"value":155746,"limit":2097152},"templateargumentsize":{"value":3873,"limit":2097152},"expansiondepth":{"value":15,"limit":100},"expensivefunctioncount":{"value":15,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":141005,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 997.624 1 -total"," 26.63% 265.624 22 Template:Annotated_link"," 21.28% 212.278 1 Template:Reflist"," 15.80% 157.583 18 Template:Cite_book"," 12.11% 120.830 5 Template:Navbox"," 7.93% 79.105 1 Template:Fractals"," 6.96% 69.481 1 Template:Short_description"," 6.63% 66.146 1 Template:Quote"," 6.24% 62.257 1 Template:Commons_category"," 6.19% 61.776 2 Template:Sister_project"]},"scribunto":{"limitreport-timeusage":{"value":"0.552","limit":"10.000"},"limitreport-memusage":{"value":21792466,"limit":52428800},"limitreport-logs":"anchor_id_list = table#1 {\n [\"CITEREFAlejandro2021\"] = 1,\n [\"CITEREFBarwise,_JonMoss,_Lawrence_S.1996\"] = 1,\n [\"CITEREFBeer1972\"] = 1,\n [\"CITEREFBourdieu1992\"] = 1,\n [\"CITEREFCausey,_Robert_L.2001\"] = 1,\n [\"CITEREFCausey2006\"] = 1,\n [\"CITEREFCooper2007\"] = 1,\n [\"CITEREFCori,_ReneLascar,_DanielPelletier,_Donald_H.2001\"] = 1,\n [\"CITEREFCormenLeisersonRivestStein2001\"] = 1,\n [\"CITEREFDijkstra1960\"] = 1,\n [\"CITEREFDrucker2008\"] = 1,\n [\"CITEREFGiddens1987\"] = 1,\n [\"CITEREFHofstadter,_Douglas1999\"] = 1,\n [\"CITEREFHungerford1980\"] = 1,\n [\"CITEREFHunter2011\"] = 1,\n [\"CITEREFJohnsonbaugh,_Richard2004\"] = 1,\n [\"CITEREFKernighan,_B.Ritchie,_D.1988\"] = 1,\n [\"CITEREFNederhofSatta2002\"] = 1,\n [\"CITEREFNevinsPesetskyRodrigues2009\"] = 1,\n [\"CITEREFNordquist\"] = 1,\n [\"CITEREFPinker1994\"] = 1,\n [\"CITEREFPinkerJackendoff2005\"] = 1,\n [\"CITEREFRidingHainesThomas1994\"] = 1,\n [\"CITEREFRosen,_Kenneth_H.2002\"] = 1,\n [\"CITEREFShaffer\"] = 1,\n [\"CITEREFShoenfield,_Joseph_R.2000\"] = 1,\n [\"CITEREFStokey,_NancyRobert_LucasEdward_Prescott1989\"] = 1,\n [\"CITEREFSvozil2018\"] = 1,\n [\"CITEREFTang\"] = 1,\n [\"base_case\"] = 1,\n [\"recursive_step\"] = 1,\n}\ntemplate_list = table#1 {\n [\"!\"] = 1,\n [\"Anchor\"] = 2,\n [\"Annotated link\"] = 22,\n [\"Authority control\"] = 1,\n [\"Citation\"] = 1,\n [\"Cite book\"] = 18,\n [\"Cite journal\"] = 6,\n [\"Cite web\"] = 11,\n [\"Clear\"] = 1,\n [\"Code\"] = 2,\n [\"Commons category\"] = 1,\n [\"Fractals\"] = 1,\n [\"Further information\"] = 1,\n [\"Harvp\"] = 1,\n [\"Main\"] = 3,\n [\"Math\"] = 13,\n [\"Mathematical logic\"] = 1,\n [\"Mvar\"] = 7,\n [\"Nowrap\"] = 1,\n [\"Other uses\"] = 1,\n [\"Pp-vandalism\"] = 1,\n [\"Quote\"] = 1,\n [\"Refbegin\"] = 1,\n [\"Refend\"] = 1,\n [\"Reflist\"] = 1,\n [\"See also\"] = 2,\n [\"Short description\"] = 1,\n [\"Wiktionary\"] = 1,\n}\narticle_whitelist = table#1 {\n}\nciteref_patterns = table#1 {\n}\n"},"cachereport":{"origin":"mw-web.codfw.main-5d5f45b5c6-6w5bs","timestamp":"20250328135556","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Recursion","url":"https:\/\/en.wikipedia.org\/wiki\/Recursion","sameAs":"http:\/\/www.wikidata.org\/entity\/Q179976","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q179976","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2001-11-10T23:05:26Z","dateModified":"2025-03-09T05:59:59Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/d\/d9\/Droste_Cacao_Alcalinise_blikje%2C_foto4.JPG","headline":"process of repeating items in a self-similar way"}</script> </body> </html>