CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-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-toc-available" lang="fr" dir="ltr"> <head> <meta charset="UTF-8"> <title>Algorithme récursif — Wikipédia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-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-toc-available";var cookie=document.cookie.match(/(?:^|; )frwikimwclientpreferences=([^;]+)/);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":[",\t."," \t,"],"wgDigitTransformTable":["",""], "wgDefaultDateFormat":"dmy","wgMonthNames":["","janvier","février","mars","avril","mai","juin","juillet","août","septembre","octobre","novembre","décembre"],"wgRequestId":"a9eacdbd-30b7-4a7d-95c6-c729cce0b295","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Algorithme_récursif","wgTitle":"Algorithme récursif","wgCurRevisionId":220490945,"wgRevisionId":220490945,"wgArticleId":28491,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Article à référence souhaitée","Article contenant un appel à traduction en anglais","Portail:Informatique théorique/Articles liés","Portail:Informatique/Articles liés","Projet:Mathématiques/Articles","Portail:Logique/Articles liés","Portail:Sciences/Articles liés","Méthode algorithmique","Langage fonctionnel"],"wgPageViewLanguage":"fr","wgPageContentLanguage":"fr","wgPageContentModel":"wikitext","wgRelevantPageName": "Algorithme_récursif","wgRelevantArticleId":28491,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":true,"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"fr","pageLanguageDir":"ltr","pageVariantFallbacks":"fr"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":true,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":30000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q264164","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"], "GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":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","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","ext.pygments.view","mediawiki.page.media","site","mediawiki.page.ready","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ArchiveLinks","ext.gadget.Wdsearch","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.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</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=fr&modules=ext.cite.styles%7Cext.math.styles%7Cext.pygments%2CwikimediaBadges%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediamessages.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=fr&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=fr&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.5"> <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/f/f7/RecursiveTree.JPG"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="1582"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/f/f7/RecursiveTree.JPG"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="1055"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="844"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Algorithme récursif — Wikipédia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//fr.m.wikipedia.org/wiki/Algorithme_r%C3%A9cursif"> <link rel="alternate" type="application/x-wiki" title="Modifier" href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit"> <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="Wikipédia (fr)"> <link rel="EditURI" type="application/rsd+xml" href="//fr.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://fr.wikipedia.org/wiki/Algorithme_r%C3%A9cursif"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.fr"> <link rel="alternate" type="application/atom+xml" title="Flux Atom de Wikipédia" href="/w/index.php?title=Sp%C3%A9cial:Modifications_r%C3%A9centes&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 mw-editable page-Algorithme_récursif rootpage-Algorithme_récursif skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Aller au contenu</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" > <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="Menu principal" > <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">Menu principal</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">Menu principal</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">déplacer vers la barre latérale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">masquer</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/Wikip%C3%A9dia:Accueil_principal" title="Accueil général [z]" accesskey="z"><span>Accueil</span></a></li><li id="n-thema" class="mw-list-item"><a href="/wiki/Portail:Accueil"><span>Portails thématiques</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Page_au_hasard" title="Affiche un article au hasard [x]" accesskey="x"><span>Article au hasard</span></a></li><li id="n-contact" class="mw-list-item"><a href="/wiki/Wikip%C3%A9dia:Contact"><span>Contact</span></a></li> </ul> </div> </div> <div id="p-Contribuer" class="vector-menu mw-portlet mw-portlet-Contribuer" > <div class="vector-menu-heading"> Contribuer </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-aboutwp" class="mw-list-item"><a href="/wiki/Aide:D%C3%A9buter"><span>Débuter sur Wikipédia</span></a></li><li id="n-help" class="mw-list-item"><a href="/wiki/Aide:Accueil" title="Accès à l’aide"><span>Aide</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikip%C3%A9dia:Accueil_de_la_communaut%C3%A9" title="À propos du projet, ce que vous pouvez faire, où trouver les informations"><span>Communauté</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Modifications_r%C3%A9centes" title="Liste des modifications récentes sur le wiki [r]" accesskey="r"><span>Modifications récentes</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Wikip%C3%A9dia:Accueil_principal" 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="Wikipédia" src="/static/images/mobile/copyright/wikipedia-wordmark-fr.svg" style="width: 7.4375em; height: 1.125em;"> <img class="mw-logo-tagline" alt="l'encyclopédie libre" src="/static/images/mobile/copyright/wikipedia-tagline-fr.svg" width="120" height="13" style="width: 7.5em; 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/Sp%C3%A9cial:Recherche" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Rechercher sur Wikipédia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Rechercher</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="Rechercher sur Wikipédia" aria-label="Rechercher sur Wikipédia" autocapitalize="sentences" title="Rechercher sur Wikipédia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Spécial:Recherche"> </div> <button class="cdx-button cdx-search-input__end-button">Rechercher</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Outils personnels"> <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="Apparence"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Modifier l'apparence de la taille, de la largeur et de la couleur de la police de la page" > <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="Apparence" > <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">Apparence</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="//donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_fr.wikipedia.org&uselang=fr" class=""><span>Faire un don</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=Sp%C3%A9cial:Cr%C3%A9er_un_compte&returnto=Algorithme+r%C3%A9cursif" title="Nous vous encourageons à créer un compte utilisateur et vous connecter ; ce n’est cependant pas obligatoire." class=""><span>Créer un compte</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=Sp%C3%A9cial:Connexion&returnto=Algorithme+r%C3%A9cursif" title="Nous vous encourageons à vous connecter ; ce n’est cependant pas obligatoire. [o]" accesskey="o" class=""><span>Se connecter</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="Plus d’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="Outils personnels" > <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">Outils personnels</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="Menu utilisateur" > <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="//donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_fr.wikipedia.org&uselang=fr"><span>Faire un don</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:Cr%C3%A9er_un_compte&returnto=Algorithme+r%C3%A9cursif" title="Nous vous encourageons à créer un compte utilisateur et vous connecter ; ce n’est cependant pas obligatoire."><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Créer un compte</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:Connexion&returnto=Algorithme+r%C3%A9cursif" title="Nous vous encourageons à vous connecter ; ce n’est cependant pas obligatoire. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Se connecter</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 pour les contributeurs déconnectés <a href="/wiki/Aide:Premiers_pas" aria-label="En savoir plus sur la contribution"><span>en savoir plus</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/Sp%C3%A9cial:Mes_contributions" title="Une liste des modifications effectuées depuis cette adresse IP [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Mes_discussions" title="La page de discussion pour les contributions depuis cette adresse IP [n]" accesskey="n"><span>Discussion</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="Sommaire" 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">Sommaire</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">déplacer vers la barre latérale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">masquer</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">Début</div> </a> </li> <li id="toc-Un_exemple_préliminaire_:_les_permutations" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Un_exemple_préliminaire_:_les_permutations"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Un exemple préliminaire : les permutations</span> </div> </a> <button aria-controls="toc-Un_exemple_préliminaire_:_les_permutations-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>Afficher / masquer la sous-section Un exemple préliminaire : les permutations</span> </button> <ul id="toc-Un_exemple_préliminaire_:_les_permutations-sublist" class="vector-toc-list"> <li id="toc-Les_permutations_courtes" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Les_permutations_courtes"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.1</span> <span>Les permutations courtes</span> </div> </a> <ul id="toc-Les_permutations_courtes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Bien_démarrer" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Bien_démarrer"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.2</span> <span>Bien démarrer</span> </div> </a> <ul id="toc-Bien_démarrer-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Un_exemple_liminaire_:_la_factorielle" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Un_exemple_liminaire_:_la_factorielle"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Un exemple liminaire : la factorielle</span> </div> </a> <button aria-controls="toc-Un_exemple_liminaire_:_la_factorielle-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>Afficher / masquer la sous-section Un exemple liminaire : la factorielle</span> </button> <ul id="toc-Un_exemple_liminaire_:_la_factorielle-sublist" class="vector-toc-list"> <li id="toc-Présentation_plus_mathématique" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Présentation_plus_mathématique"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.1</span> <span>Présentation plus mathématique</span> </div> </a> <ul id="toc-Présentation_plus_mathématique-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Un_autre_exemple_:_le_nombre_de_partitions_d'un_entier_naturel_en_au_plus_q_parties" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Un_autre_exemple_:_le_nombre_de_partitions_d'un_entier_naturel_en_au_plus_q_parties"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Un autre exemple : le nombre de partitions d'un entier naturel en au plus q parties</span> </div> </a> <ul id="toc-Un_autre_exemple_:_le_nombre_de_partitions_d'un_entier_naturel_en_au_plus_q_parties-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-D'autres_fonctions_récursives_à_plusieurs_arguments" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#D'autres_fonctions_récursives_à_plusieurs_arguments"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>D'autres fonctions récursives à plusieurs arguments</span> </div> </a> <ul id="toc-D'autres_fonctions_récursives_à_plusieurs_arguments-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Algorithmes_récursifs_non_numériques" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Algorithmes_récursifs_non_numériques"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Algorithmes récursifs non numériques</span> </div> </a> <button aria-controls="toc-Algorithmes_récursifs_non_numériques-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>Afficher / masquer la sous-section Algorithmes récursifs non numériques</span> </button> <ul id="toc-Algorithmes_récursifs_non_numériques-sublist" class="vector-toc-list"> <li id="toc-Algorithmes_récursifs_sur_les_listes" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Algorithmes_récursifs_sur_les_listes"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.1</span> <span>Algorithmes récursifs sur les listes</span> </div> </a> <ul id="toc-Algorithmes_récursifs_sur_les_listes-sublist" class="vector-toc-list"> <li id="toc-++" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#++"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.1.1</span> <span>++</span> </div> </a> <ul id="toc-++-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-map" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#map"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.1.2</span> <span>map</span> </div> </a> <ul id="toc-map-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-ins" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#ins"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.1.3</span> <span>ins</span> </div> </a> <ul id="toc-ins-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-concat" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#concat"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.1.4</span> <span>concat</span> </div> </a> <ul id="toc-concat-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-permutations" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#permutations"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.1.5</span> <span>permutations</span> </div> </a> <ul id="toc-permutations-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Algorithmes_récursifs_sur_les_arbres_binaires" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Algorithmes_récursifs_sur_les_arbres_binaires"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.2</span> <span>Algorithmes récursifs sur les arbres binaires</span> </div> </a> <ul id="toc-Algorithmes_récursifs_sur_les_arbres_binaires-sublist" class="vector-toc-list"> <li id="toc-taille" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#taille"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.2.1</span> <span>taille</span> </div> </a> <ul id="toc-taille-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-motDesFeuilles" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#motDesFeuilles"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.2.2</span> <span>motDesFeuilles</span> </div> </a> <ul id="toc-motDesFeuilles-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> </ul> </li> <li id="toc-Prouver_la_correction_d'un_algorithme_récursif" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Prouver_la_correction_d'un_algorithme_récursif"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Prouver la correction d'un algorithme récursif</span> </div> </a> <button aria-controls="toc-Prouver_la_correction_d'un_algorithme_récursif-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>Afficher / masquer la sous-section Prouver la correction d'un algorithme récursif</span> </button> <ul id="toc-Prouver_la_correction_d'un_algorithme_récursif-sublist" class="vector-toc-list"> <li id="toc-Problème_de_la_terminaison" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Problème_de_la_terminaison"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.1</span> <span>Problème de la terminaison</span> </div> </a> <ul id="toc-Problème_de_la_terminaison-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Théorème_de_terminaison" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Théorème_de_terminaison"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.2</span> <span>Théorème de terminaison</span> </div> </a> <ul id="toc-Théorème_de_terminaison-sublist" class="vector-toc-list"> <li id="toc-Terminaison_de_la_fonction_d_qui_calcule_le_nombre_de_décompositions_de_p_en_au_plus_q_sommants" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Terminaison_de_la_fonction_d_qui_calcule_le_nombre_de_décompositions_de_p_en_au_plus_q_sommants"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.2.1</span> <span>Terminaison de la fonction d qui calcule le nombre de décompositions de p en au plus q sommants</span> </div> </a> <ul id="toc-Terminaison_de_la_fonction_d_qui_calcule_le_nombre_de_décompositions_de_p_en_au_plus_q_sommants-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Terminaison_de_la_fonction_Syracuse" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Terminaison_de_la_fonction_Syracuse"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.2.2</span> <span>Terminaison de la fonction Syracuse</span> </div> </a> <ul id="toc-Terminaison_de_la_fonction_Syracuse-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Problème_de_la_correction_partielle" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Problème_de_la_correction_partielle"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.3</span> <span>Problème de la correction partielle</span> </div> </a> <ul id="toc-Problème_de_la_correction_partielle-sublist" class="vector-toc-list"> <li id="toc-Correction_partielle_sur_l'exemple_du_pgcd" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Correction_partielle_sur_l'exemple_du_pgcd"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.3.1</span> <span>Correction partielle sur l'exemple du pgcd</span> </div> </a> <ul id="toc-Correction_partielle_sur_l'exemple_du_pgcd-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> </ul> </li> <li id="toc-Efficacité" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Efficacité"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Efficacité</span> </div> </a> <button aria-controls="toc-Efficacité-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>Afficher / masquer la sous-section Efficacité</span> </button> <ul id="toc-Efficacité-sublist" class="vector-toc-list"> <li id="toc-Simplicité_de_description_versus_efficacité" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Simplicité_de_description_versus_efficacité"> <div class="vector-toc-text"> <span class="vector-toc-numb">7.1</span> <span>Simplicité de description versus efficacité</span> </div> </a> <ul id="toc-Simplicité_de_description_versus_efficacité-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Contributions" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Contributions"> <div class="vector-toc-text"> <span class="vector-toc-numb">7.2</span> <span>Contributions</span> </div> </a> <ul id="toc-Contributions-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Récursion_terminale" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Récursion_terminale"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>Récursion terminale</span> </div> </a> <ul id="toc-Récursion_terminale-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Autres_situations_et_corécursivité" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Autres_situations_et_corécursivité"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>Autres situations et corécursivité</span> </div> </a> <ul id="toc-Autres_situations_et_corécursivité-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Notes_et_références" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Notes_et_références"> <div class="vector-toc-text"> <span class="vector-toc-numb">10</span> <span>Notes et références</span> </div> </a> <button aria-controls="toc-Notes_et_références-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>Afficher / masquer la sous-section Notes et références</span> </button> <ul id="toc-Notes_et_références-sublist" class="vector-toc-list"> <li id="toc-Références" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Références"> <div class="vector-toc-text"> <span class="vector-toc-numb">10.1</span> <span>Références</span> </div> </a> <ul id="toc-Références-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Notes" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Notes"> <div class="vector-toc-text"> <span class="vector-toc-numb">10.2</span> <span>Notes</span> </div> </a> <ul id="toc-Notes-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Voir_aussi" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Voir_aussi"> <div class="vector-toc-text"> <span class="vector-toc-numb">11</span> <span>Voir aussi</span> </div> </a> <button aria-controls="toc-Voir_aussi-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>Afficher / masquer la sous-section Voir aussi</span> </button> <ul id="toc-Voir_aussi-sublist" class="vector-toc-list"> <li id="toc-Articles_connexes" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Articles_connexes"> <div class="vector-toc-text"> <span class="vector-toc-numb">11.1</span> <span>Articles connexes</span> </div> </a> <ul id="toc-Articles_connexes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Bibliographie" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Bibliographie"> <div class="vector-toc-text"> <span class="vector-toc-numb">11.2</span> <span>Bibliographie</span> </div> </a> <ul id="toc-Bibliographie-sublist" class="vector-toc-list"> <li id="toc-En_français" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#En_français"> <div class="vector-toc-text"> <span class="vector-toc-numb">11.2.1</span> <span>En français</span> </div> </a> <ul id="toc-En_français-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-En_anglais" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#En_anglais"> <div class="vector-toc-text"> <span class="vector-toc-numb">11.2.2</span> <span>En anglais</span> </div> </a> <ul id="toc-En_anglais-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> </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="Sommaire" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <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="Basculer la table des matières" > <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">Basculer la table des matières</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">Algorithme récursif</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="Aller à un article dans une autre langue. Disponible en 28 langues." > <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-28" 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">28 langues</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_(%D8%B9%D9%84%D9%85_%D8%A7%D9%84%D8%AD%D8%A7%D8%B3%D9%88%D8%A8)" title="عودية (علم الحاسوب) – arabe" lang="ar" hreflang="ar" data-title="عودية (علم الحاسوب)" data-language-autonym="العربية" data-language-local-name="arabe" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-bar mw-list-item"><a href="https://bar.wikipedia.org/wiki/Rekursive_Programmierung" title="Rekursive Programmierung – bavarois" lang="bar" hreflang="bar" data-title="Rekursive Programmierung" data-language-autonym="Boarisch" data-language-local-name="bavarois" class="interlanguage-link-target"><span>Boarisch</span></a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Algorisme_recursiu" title="Algorisme recursiu – catalan" lang="ca" hreflang="ca" data-title="Algorisme recursiu" 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_(programov%C3%A1n%C3%AD)" title="Rekurze (programování) – tchèque" lang="cs" hreflang="cs" data-title="Rekurze (programování)" data-language-autonym="Čeština" data-language-local-name="tchèque" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-cv mw-list-item"><a href="https://cv.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D0%B2%D0%BB%C4%83_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8" title="Рекурсивлă функци – tchouvache" lang="cv" hreflang="cv" data-title="Рекурсивлă функци" data-language-autonym="Чӑвашла" data-language-local-name="tchouvache" class="interlanguage-link-target"><span>Чӑвашла</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Rekursive_Programmierung" title="Rekursive Programmierung – allemand" lang="de" hreflang="de" data-title="Rekursive Programmierung" data-language-autonym="Deutsch" data-language-local-name="allemand" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-en mw-list-item"><a href="https://en.wikipedia.org/wiki/Recursion_(computer_science)" title="Recursion (computer science) – anglais" lang="en" hreflang="en" data-title="Recursion (computer science)" data-language-autonym="English" data-language-local-name="anglais" class="interlanguage-link-target"><span>English</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Recursi%C3%B3n_(ciencias_de_computaci%C3%B3n)" title="Recursión (ciencias de computación) – espagnol" lang="es" hreflang="es" data-title="Recursión (ciencias de computación)" data-language-autonym="Español" data-language-local-name="espagnol" class="interlanguage-link-target"><span>Español</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_(%D8%B9%D9%84%D9%88%D9%85_%D8%B1%D8%A7%DB%8C%D8%A7%D9%86%D9%87)" title="بازگشت (علوم رایانه) – persan" lang="fa" hreflang="fa" data-title="بازگشت (علوم رایانه)" data-language-autonym="فارسی" data-language-local-name="persan" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fi mw-list-item"><a href="https://fi.wikipedia.org/wiki/Rekursiivinen_algoritmi" title="Rekursiivinen algoritmi – finnois" lang="fi" hreflang="fi" data-title="Rekursiivinen algoritmi" data-language-autonym="Suomi" data-language-local-name="finnois" class="interlanguage-link-target"><span>Suomi</span></a></li><li class="interlanguage-link interwiki-hi mw-list-item"><a href="https://hi.wikipedia.org/wiki/%E0%A4%AA%E0%A5%81%E0%A4%A8%E0%A4%B0%E0%A4%BE%E0%A4%B5%E0%A5%83%E0%A4%A4%E0%A5%8D%E0%A4%A4%E0%A4%BF_(%E0%A4%95%E0%A4%82%E0%A4%AA%E0%A5%8D%E0%A4%AF%E0%A5%82%E0%A4%9F%E0%A4%B0_%E0%A4%B5%E0%A4%BF%E0%A4%9C%E0%A5%8D%E0%A4%9E%E0%A4%BE%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-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_(%D5%AB%D5%B6%D6%86%D5%B8%D6%80%D5%B4%D5%A1%D5%BF%D5%AB%D5%AF%D5%A1)" title="Ռեկուրսիա (ինֆորմատիկա) – arménien" lang="hy" hreflang="hy" data-title="Ռեկուրսիա (ինֆորմատիկա)" data-language-autonym="Հայերեն" data-language-local-name="arménien" class="interlanguage-link-target"><span>Հայերեն</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Algoritmo_ricorsivo" title="Algoritmo ricorsivo – italien" lang="it" hreflang="it" data-title="Algoritmo ricorsivo" data-language-autonym="Italiano" data-language-local-name="italien" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-ja badge-Q70893996 mw-list-item" title=""><a href="https://ja.wikipedia.org/wiki/%E5%86%8D%E5%B8%B0%E7%9A%84%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0" title="再帰的アルゴリズム – japonais" lang="ja" hreflang="ja" data-title="再帰的アルゴリズム" data-language-autonym="日本語" data-language-local-name="japonais" 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%D0%B2%D1%82%D1%96_%D1%84%D1%83%D0%BD%D0%BA%D1%86%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-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EC%9E%AC%EA%B7%80_(%EC%BB%B4%ED%93%A8%ED%84%B0_%EA%B3%BC%ED%95%99)" title="재귀 (컴퓨터 과학) – coréen" lang="ko" hreflang="ko" data-title="재귀 (컴퓨터 과학)" data-language-autonym="한국어" data-language-local-name="coréen" 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_(informatica)" title="Recursie (informatica) – néerlandais" lang="nl" hreflang="nl" data-title="Recursie (informatica)" data-language-autonym="Nederlands" data-language-local-name="néerlandais" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Recursividade_(ci%C3%AAncia_da_computa%C3%A7%C3%A3o)" title="Recursividade (ciência da computação) – portugais" lang="pt" hreflang="pt" data-title="Recursividade (ciência da computação)" data-language-autonym="Português" data-language-local-name="portugais" class="interlanguage-link-target"><span>Português</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%D0%B2%D0%BD%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F" title="Рекурсивная функция – russe" lang="ru" hreflang="ru" data-title="Рекурсивная функция" data-language-autonym="Русский" data-language-local-name="russe" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-simple mw-list-item"><a href="https://simple.wikipedia.org/wiki/Recursive_algorithm" title="Recursive algorithm – Simple English" lang="en-simple" hreflang="en-simple" data-title="Recursive algorithm" 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_(informatika)" title="Rekurzia (informatika) – slovaque" lang="sk" hreflang="sk" data-title="Rekurzia (informatika)" data-language-autonym="Slovenčina" data-language-local-name="slovaque" 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_(%D0%BA%D0%BE%D0%BC%D0%BF%D1%98%D1%83%D1%82%D0%B5%D1%80%D1%81%D0%BA%D0%B5_%D0%BD%D0%B0%D1%83%D0%BA%D0%B5)" title="Рекурзија (компјутерске науке) – serbe" lang="sr" hreflang="sr" data-title="Рекурзија (компјутерске науке)" data-language-autonym="Српски / srpski" data-language-local-name="serbe" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-sv mw-list-item"><a href="https://sv.wikipedia.org/wiki/Rekursiv_algoritm" title="Rekursiv algoritm – suédois" lang="sv" hreflang="sv" data-title="Rekursiv algoritm" data-language-autonym="Svenska" data-language-local-name="suédois" class="interlanguage-link-target"><span>Svenska</span></a></li><li class="interlanguage-link interwiki-ta mw-list-item"><a href="https://ta.wikipedia.org/wiki/%E0%AE%9A%E0%AF%81%E0%AE%B4%E0%AE%B2%E0%AF%8D" title="சுழல் – tamoul" lang="ta" hreflang="ta" data-title="சுழல்" data-language-autonym="தமிழ்" data-language-local-name="tamoul" class="interlanguage-link-target"><span>தமிழ்</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_(%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F)" title="Рекурсія (програмування) – ukrainien" lang="uk" hreflang="uk" data-title="Рекурсія (програмування)" data-language-autonym="Українська" data-language-local-name="ukrainien" 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_(tin_h%E1%BB%8Dc)" title="Đệ quy (tin học) – vietnamien" lang="vi" hreflang="vi" data-title="Đệ quy (tin học)" data-language-autonym="Tiếng Việt" data-language-local-name="vietnamien" class="interlanguage-link-target"><span>Tiếng Việt</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_(%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6)" title="递归 (计算机科学) – chinois" lang="zh" hreflang="zh" data-title="递归 (计算机科学)" data-language-autonym="中文" data-language-local-name="chinois" 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_(%E9%9B%BB%E8%85%A6%E7%A7%91%E5%AD%B8)" title="遞歸 (電腦科學) – cantonais" lang="yue" hreflang="yue" data-title="遞歸 (電腦科學)" data-language-autonym="粵語" data-language-local-name="cantonais" 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/Q264164#sitelinks-wikipedia" title="Modifier les liens interlangues" class="wbc-editpage">Modifier les liens</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="Espaces de noms"> <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/Algorithme_r%C3%A9cursif" title="Voir le contenu de la page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Discussion:Algorithme_r%C3%A9cursif" rel="discussion" title="Discussion au sujet de cette page de contenu [t]" accesskey="t"><span>Discussion</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="Modifier la variante de langue" > <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">français</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="Affichages"> <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/Algorithme_r%C3%A9cursif"><span>Lire</span></a></li><li id="ca-ve-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit" title="Modifier cette page [v]" accesskey="v"><span>Modifier</span></a></li><li id="ca-edit" class="collapsible vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit" title="Modifier le wikicode de cette page [e]" accesskey="e"><span>Modifier le code</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=history" title="Historique des versions de cette page [h]" accesskey="h"><span>Voir l’historique</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Outils de la page"> <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="Outils" > <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">Outils</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">Outils</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">déplacer vers la barre latérale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">masquer</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="Plus d’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/Algorithme_r%C3%A9cursif"><span>Lire</span></a></li><li id="ca-more-ve-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit" title="Modifier cette page [v]" accesskey="v"><span>Modifier</span></a></li><li id="ca-more-edit" class="collapsible vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit" title="Modifier le wikicode de cette page [e]" accesskey="e"><span>Modifier le code</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=history"><span>Voir l’historique</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> Général </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Pages_li%C3%A9es/Algorithme_r%C3%A9cursif" title="Liste des pages liées qui pointent sur celle-ci [j]" accesskey="j"><span>Pages liées</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Suivi_des_liens/Algorithme_r%C3%A9cursif" rel="nofollow" title="Liste des modifications récentes des pages appelées par celle-ci [k]" accesskey="k"><span>Suivi des pages liées</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Aide:Importer_un_fichier" title="Téléverser des fichiers [u]" accesskey="u"><span>Téléverser un fichier</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Pages_sp%C3%A9ciales" title="Liste de toutes les pages spéciales [q]" accesskey="q"><span>Pages spéciales</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&oldid=220490945" title="Adresse permanente de cette version de cette page"><span>Lien permanent</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=info" title="Davantage d’informations sur cette page"><span>Informations sur la page</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:Citer&page=Algorithme_r%C3%A9cursif&id=220490945&wpFormIdentifier=titleform" title="Informations sur la manière de citer cette page"><span>Citer cette page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:UrlShortener&url=https%3A%2F%2Ffr.wikipedia.org%2Fwiki%2FAlgorithme_r%25C3%25A9cursif"><span>Obtenir l'URL raccourcie</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:QrCode&url=https%3A%2F%2Ffr.wikipedia.org%2Fwiki%2FAlgorithme_r%25C3%25A9cursif"><span>Télécharger le code QR</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"> Imprimer / exporter </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-create_a_book" class="mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:Livre&bookcmd=book_creator&referer=Algorithme+r%C3%A9cursif"><span>Créer un livre</span></a></li><li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:DownloadAsPdf&page=Algorithme_r%C3%A9cursif&action=show-download-screen"><span>Télécharger comme PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&printable=yes" title="Version imprimable de cette page [p]" accesskey="p"><span>Version imprimable</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"> Dans d’autres projets </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-wikiversity mw-list-item"><a href="https://fr.wikiversity.org/wiki/R%C3%A9cursivit%C3%A9_dans_l%27algorithmique_et_la_programmation" hreflang="fr"><span>Wikiversité</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/Q264164" title="Lien vers l’élément dans le dépôt de données connecté [g]" accesskey="g"><span>Élément Wikidata</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="Outils de la page"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Apparence"> <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">Apparence</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">déplacer vers la barre latérale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">masquer</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> <div id="siteSub" class="noprint">Un article de Wikipédia, l'encyclopédie libre.</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="fr" dir="ltr"><figure typeof="mw:File/Thumb"><a href="/wiki/Fichier:RecursiveTree.JPG" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/f/f7/RecursiveTree.JPG/300px-RecursiveTree.JPG" decoding="async" width="300" height="396" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/f/f7/RecursiveTree.JPG 1.5x" data-file-width="380" data-file-height="501" /></a><figcaption>Arbre dessiné par un algorithme récursif. On remarque que chaque branche est elle-même une version plus petite d'un arbre.</figcaption></figure><p>Un <b>algorithme récursif</b> est un <a href="/wiki/Algorithme" title="Algorithme">algorithme</a> qui résout un problème en calculant des solutions d'<a href="/wiki/Instance_(programmation)" title="Instance (programmation)">instances</a> plus petites du même problème<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite_crochet">[</span>1<span class="cite_crochet">]</span></a></sup>. L'approche <a href="/wiki/R%C3%A9cursivit%C3%A9" title="Récursivité">récursive</a> est un des concepts de base en <a href="/wiki/Informatique" title="Informatique">informatique</a>. </p><p>Les premiers <a href="/wiki/Langage_de_programmation" title="Langage de programmation">langages de programmation</a> qui ont autorisé l'emploi de la récursivité sont <a href="/wiki/Lisp_(langage)" class="mw-redirect" title="Lisp (langage)">LISP</a> et <a href="/wiki/Algol_(langage)" title="Algol (langage)">Algol 60</a>. Depuis, tous les langages de programmation généraux réalisent une <a href="/wiki/Mise_en_%C5%93uvre" title="Mise en œuvre">implémentation</a> de la récursivité. Pour répéter des opérations, typiquement, un algorithme récursif s'appelle lui-même. On oppose généralement les algorithmes récursifs aux algorithmes itératifs, qui eux, utilisent plutôt des boucles <i>pour</i> et des boucles <i>tant que</i>, pour répéter des opérations. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Un_exemple_préliminaire_:_les_permutations"><span id="Un_exemple_pr.C3.A9liminaire_:_les_permutations"></span>Un exemple préliminaire : les permutations</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=1" title="Modifier la section : Un exemple préliminaire : les permutations" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=1" title="Modifier le code source de la section : Un exemple préliminaire : les permutations"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="bandeau-container bandeau-section metadata bandeau-niveau-information"><div class="bandeau-cell bandeau-icone-css biblio">Sauf indication contraire ou complémentaire, les informations contenues dans cette section proviennent de la source suivante : Haskell basic library <a rel="nofollow" class="external text" href="https://hackage.haskell.org/package/base-4.12.0.0/docs/Data-List.html">Data.List</a>.</div></div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/Fichier:Permutations_de_Belle_Marquise.png" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/c/c8/Permutations_de_Belle_Marquise.png/330px-Permutations_de_Belle_Marquise.png" decoding="async" width="330" height="245" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/c8/Permutations_de_Belle_Marquise.png/495px-Permutations_de_Belle_Marquise.png 1.5x, //upload.wikimedia.org/wikipedia/commons/c/c8/Permutations_de_Belle_Marquise.png 2x" data-file-width="649" data-file-height="481" /></a><figcaption>Permutations de la phrase « Belle Marquise vos beaux yeux me font mourir d'amour »</figcaption></figure> <p>Commençons par un exemple tiré du <i><a href="/wiki/Le_Bourgeois_gentilhomme" title="Le Bourgeois gentilhomme">Bourgeois gentilhomme</a></i> <a href="https://fr.wikisource.org/wiki/Le_Bourgeois_gentilhomme_(Imprimerie_nationale)#Scène_IV" class="extiw" title="s:Le Bourgeois gentilhomme (Imprimerie nationale)">(Acte II Scène IV)</a> de <a href="/wiki/Moli%C3%A8re" title="Molière">Molière</a>. Le héros, Monsieur Jourdain, veut connaître toutes les manières « galantes » d'écrire un billet. De la phrase <i>Belle Marquise, vos beaux yeux, me font mourir d'amour</i>, il pourrait tirer <i>Vos beaux yeux, belle Marquise, d'amour me font mourir</i>, puis <i>Vos beaux yeux, me font mourir, belle Marquise, d'amour</i>, puis <i>Vos beaux yeux, me font mourir d'amour, belle Marquise</i> et ainsi de suite. </p><p>Comment Monsieur Jourdain devrait-il procéder pour engendrer toutes ces <a href="/wiki/Permutation" title="Permutation">permutations</a> ? Le mieux pour lui pour être sûr d'y arriver est d'utiliser un procédé récursif. L'un de ceux-ci est le suivant<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite_crochet">[</span>2<span class="cite_crochet">]</span></a></sup><sup class="reference cite_virgule">,</sup><sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite_crochet">[</span>3<span class="cite_crochet">]</span></a></sup>, mais le lecteur peut en imaginer d'autres. Tout d'abord on construit toutes les permutations de la phrase <i>vos beaux yeux -- me font mourir -- d'amour</i>; puis, dans ces permutations, on insère en première position, puis en deuxième position, puis en troisième position, puis en quatrième position le morceau de phrase <i>belle Marquise</i>. L'algorithme est <i><b>récursif</b></i> parce qu'il s'invoque lui-même. En effet, pour construire toutes les permutations de <i>belle Marquise -- vos beaux yeux -- me font mourir -- d'amour</i>, il faut construire toutes les permutations de <i>vos beaux yeux -- me font mourir -- d'amour</i>. De plus, l'algorithme est bien un algorithme général, car si Monsieur Jourdain veut améliorer son côté poétique et veut construire, comme le lui dit son maître de philosophie, toutes les permutations de la phrase <i>belle Marquise -- vos beaux yeux -- me font -- mourir -- d'amour</i>, qui a maintenant cinq constituants il procédera de la même façon et encore de la même façon pour la phrase <i>belle Marquise -- vos beaux yeux -- me font -- mourir -- d'amour -- pour vous</i>, qui a six constituants. </p> <div class="mw-heading mw-heading3"><h3 id="Les_permutations_courtes">Les permutations courtes</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=2" title="Modifier la section : Les permutations courtes" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=2" title="Modifier le code source de la section : Les permutations courtes"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Pour construire les permutations de <i>Belle marquise -- vos beaux yeux -- me font mourir -- d'amour</i>, il faut auparavant construire toutes les permutations de la phrase <i>vos beaux yeux -- me font mourir -- d'amour</i>. Ces permutations sont au nombre de six et sont construites en insérant le morceau de phrase <i>vos beaux yeux</i> en première, deuxième et troisième position dans les deux permutations de la phrase <i>me font mourir -- d'amour</i> (à savoir <i>me font mourir -- d'amour</i> et <i>d'amour -- me font mourir</i>). Comment sont construites ces deux permutations ? En insérant en première position et en deuxième position le segment <i>me font mourir</i> dans les permutations de la phrase <i>d'amour</i>. L'aspect récursif<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite_crochet">[</span>note 1<span class="cite_crochet">]</span></a></sup> de l'algorithme apparaît clairement. </p> <div class="mw-heading mw-heading3"><h3 id="Bien_démarrer"><span id="Bien_d.C3.A9marrer"></span>Bien démarrer</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=3" title="Modifier la section : Bien démarrer" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=3" title="Modifier le code source de la section : Bien démarrer"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Combien y a-t-il de permutations de la phrase <i>d'amour</i> ? Il n'y en a qu'une seule et c'est le point de départ de l'algorithme récursif. Avoir un cas de base est nécessaire, parce qu'il faut toujours qu'un algorithme récursif ait un point (ou des points) de départ, car sinon, il ne se terminerait pas. </p> <div class="mw-heading mw-heading2"><h2 id="Un_exemple_liminaire_:_la_factorielle">Un exemple liminaire : la factorielle</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=4" title="Modifier la section : Un exemple liminaire : la factorielle" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=4" title="Modifier le code source de la section : Un exemple liminaire : la factorielle"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Prenons l'exemple de la <a href="/wiki/Factorielle" title="Factorielle">factorielle</a>. Celle-ci se définit pour des entiers naturels de la fonction suivante : </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 n!=1\times 2\times 3\times \cdots \times (n-1)\times n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>!</mo> <mo>=</mo> <mn>1</mn> <mo>×</mo> <mn>2</mn> <mo>×</mo> <mn>3</mn> <mo>×</mo> <mo>⋯</mo> <mo>×</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>×</mo> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n!=1\times 2\times 3\times \cdots \times (n-1)\times n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/022e35f3832a916d9b50f48306b8dd8ef6055a15" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:34.154ex; height:2.843ex;" alt="{\displaystyle n!=1\times 2\times 3\times \cdots \times (n-1)\times n}"></span></dd></dl> <p>autrement dit : </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 n!=(n-1)!\times n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>!</mo> <mo>=</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>!</mo> <mo>×</mo> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n!=(n-1)!\times n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/26e73582aebf788c8a3ab8bfd3864bf22211fcc0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.229ex; height:2.843ex;" alt="{\displaystyle n!=(n-1)!\times n}"></span></dd></dl> <p>Donc pour définir la fonction qui calcule la factorielle de n, il suffit d'appeler cette même fonction mais en lui demandant de calculer la factorielle de (n-1), et de multiplier le résultat par n. La factorielle de (n-1) sera calculée en calculant la factorielle de (n-2) et ainsi de suite. Il suffit juste de définir que la factorielle de 0 est 1 pour "arrêter la récursion" et ne plus appeler la fonction qui calcule la factorielle. </p><p>On voit avec cet exemple deux points majeurs de la récursion : </p> <ul><li>L'algorithme s'appelle lui-même, <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!}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>!</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n!}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bae971720be3cc9b8d82f4cdac89cb89877514a6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.042ex; height:2.176ex;" alt="{\displaystyle n!}"></span> a besoin de <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-1)!}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>!</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (n-1)!}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7eb71a5f562b97650728f30493f43e96c15b4287" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.854ex; height:2.843ex;" alt="{\displaystyle (n-1)!}"></span></li> <li>Il est nécessaire d'"arrêter la récursion", en définissant un (ou des) cas ("cas de base") où l'algorithme n'a pas besoin de s'appeler lui-même, ceci afin que l'algorithme ne s'invoque pas lui-même indéfiniment.</li></ul> <div class="mw-heading mw-heading3"><h3 id="Présentation_plus_mathématique"><span id="Pr.C3.A9sentation_plus_math.C3.A9matique"></span>Présentation plus mathématique</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=5" title="Modifier la section : Présentation plus mathématique" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=5" title="Modifier le code source de la section : Présentation plus mathématique"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <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 n!=\prod _{i=1}^{n}i=1\times 2\times 3\times \cdots \times (n-1)\times n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>!</mo> <mo>=</mo> <munderover> <mo>∏</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </munderover> <mi>i</mi> <mo>=</mo> <mn>1</mn> <mo>×</mo> <mn>2</mn> <mo>×</mo> <mn>3</mn> <mo>×</mo> <mo>⋯</mo> <mo>×</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>×</mo> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n!=\prod _{i=1}^{n}i=1\times 2\times 3\times \cdots \times (n-1)\times n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4dd20ccc2143b7218018bb383cdb6cb6e081ccc1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:41.412ex; height:6.843ex;" alt="{\displaystyle n!=\prod _{i=1}^{n}i=1\times 2\times 3\times \cdots \times (n-1)\times n}"></span></dd></dl> <p>L'idée de la récursivité est d'utiliser une définition équivalente, à savoir une définition par récurrence sur la valeur de l'argument : </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 n!={\begin{cases}1&{\text{si }}n=0\\n\times (n-1)!&{\text{sinon}}\end{cases}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>!</mo> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>{</mo> <mtable columnalign="left left" rowspacing=".2em" columnspacing="1em" displaystyle="false"> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mtext>si </mtext> </mrow> <mi>n</mi> <mo>=</mo> <mn>0</mn> </mtd> </mtr> <mtr> <mtd> <mi>n</mi> <mo>×</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>!</mo> </mtd> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mtext>sinon</mtext> </mrow> </mtd> </mtr> </mtable> <mo fence="true" stretchy="true" symmetric="true"></mo> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n!={\begin{cases}1&{\text{si }}n=0\\n\times (n-1)!&{\text{sinon}}\end{cases}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0d874c0b7970a6eb8014d3fa09991c32e9515013" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:29.845ex; height:6.176ex;" alt="{\displaystyle n!={\begin{cases}1&{\text{si }}n=0\\n\times (n-1)!&{\text{sinon}}\end{cases}}}"></span></dd></dl> <p>Autrement dit, la factorielle d'un nombre qui n'est pas 0 est obtenue en multipliant par <i>n</i> la factorielle de <i>n</i> – 1. Cette définition de la <i>factorielle</i> peut se traduire par le programme suivant en <a href="/wiki/Pseudo-code" title="Pseudo-code">pseudo-code</a> : </p> <pre>factorielle(n) = <span style="color:blue">si</span> (n = 0) <span style="color:blue">alors</span> 1 <span style="color:blue">sinon</span> n * factorielle(n-1) </pre> <p>Préciser que <i>factorielle</i>(0) = 1 est fondamental : sans cela la fonction ne serait pas définie et l'algorithme s'invoquerait indéfiniment. Le cas <i>n</i> = 0 est appelé <i>cas de base</i>. Sans sa présence, l'algorithme ne peut pas se terminer. L'autre cas est appelé <i>cas de propagation</i>, c'est lui qui contient l'appel récursif. On peut programmer ainsi d'autres suites telles que la <a href="/wiki/Suite_de_Fibonacci" title="Suite de Fibonacci">suite de Fibonacci</a>, tandis que la fonction suivante : </p> <pre>syracuse(n) = <span style="color:blue">si</span> (n = 0) <span style="color:blue">ou</span> (n = 1) <span style="color:blue">alors</span> 1 <span style="color:blue">sinon</span> <span style="color:blue">si</span> (n mod 2 = 0) <span style="color:blue">alors</span> syracuse(n/2) <span style="color:blue">sinon</span> syracuse(3*n + 1) </pre> <p>définit la fonction identiquement égale à 1 si la <a href="/wiki/Conjecture_de_Syracuse" title="Conjecture de Syracuse">conjecture de Syracuse</a> est vraie. </p><p>Mais, comme nous l'avons vu dans l'exemple préliminaire, les algorithmes récursifs ne se limitent évidemment pas au calcul de suites récurrentes et de fonctions sur les entiers naturels. Ils permettent de travailler sur des structures de données définies récursivement comme les chaînes de caractères, les listes ou les <a href="/wiki/Arbre_(informatique)" class="mw-redirect" title="Arbre (informatique)">arbres</a>, ou plus généralement sur des ensembles munis d'une <a href="/wiki/Relation_bien_fond%C3%A9e" title="Relation bien fondée">relation bien fondée</a>. Parmi les relations bien fondées les plus connues, il y a l'ordre sur la structure des objets qui donne lieu à la <a href="/wiki/R%C3%A9currence_structurelle" class="mw-redirect" title="Récurrence structurelle">récurrence structurelle</a> et l'ordre naturel sur les entiers positifs qui donne lieu à la récursivité numérique (ou récursivité sur les entiers). Le <a href="/wiki/Algorithme_de_tri" title="Algorithme de tri">tri</a>, le problème des <a href="/wiki/Tours_de_Hano%C3%AF" title="Tours de Hanoï">tours de Hanoï</a> et la génération des <a href="/wiki/Permutation" title="Permutation">permutations</a> (c'est-à-dire la généralisation de l'exemple de Monsieur Jourdain) sont des exemples paradigmatiques d'application d'algorithmes récursifs. </p> <div class="mw-heading mw-heading2"><h2 id="Un_autre_exemple_:_le_nombre_de_partitions_d'un_entier_naturel_en_au_plus_q_parties"><span id="Un_autre_exemple_:_le_nombre_de_partitions_d.27un_entier_naturel_en_au_plus_q_parties"></span>Un autre exemple : le nombre de partitions d'un entier naturel en au plus q parties</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=6" title="Modifier la section : Un autre exemple : le nombre de partitions d'un entier naturel en au plus q parties" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=6" title="Modifier le code source de la section : Un autre exemple : le nombre de partitions d'un entier naturel en au plus q parties"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Nous allons considérer un cas tiré des mathématiques où l'approche récursive s'impose (voir l'article <a href="/wiki/Partition_d%27un_entier" title="Partition d'un entier">Partition d'un entier</a>) : </p><p><b>Un exemple :</b> Une <i>partie</i> est un naturel positif qui entre dans une somme quand on décompose un nombre en somme de naturels décroissants. Ainsi, les partitions de 5 en au plus 3 parties sont 5, 4+1, 3+2, 3+1+1, 2+2+1. Si on écrit <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 d(5,3)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> <mo stretchy="false">(</mo> <mn>5</mn> <mo>,</mo> <mn>3</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d(5,3)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7bd5521a7ab0ea45d01986af403eeffa09bd2b98" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.384ex; height:2.843ex;" alt="{\displaystyle d(5,3)}"></span> le nombre de partitions de 5 en <i>au plus</i> 3 parties, on a <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 d(5,3)=5}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> <mo stretchy="false">(</mo> <mn>5</mn> <mo>,</mo> <mn>3</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mn>5</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d(5,3)=5}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1b6a0ce14e7464a08d41f7dbebc1c05064c50698" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.645ex; height:2.843ex;" alt="{\displaystyle d(5,3)=5}"></span> et si on écrit <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 d'(5,3)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>d</mi> <mo>′</mo> </msup> <mo stretchy="false">(</mo> <mn>5</mn> <mo>,</mo> <mn>3</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d'(5,3)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f0ae4d06bcc963f272c5eaeffa861235e491c718" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.071ex; height:3.009ex;" alt="{\displaystyle d'(5,3)}"></span> le nombre de partitions de 5 en <i>exactement</i> 3 parties, on a <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 d'(5,3)=2}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>d</mi> <mo>′</mo> </msup> <mo stretchy="false">(</mo> <mn>5</mn> <mo>,</mo> <mn>3</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mn>2</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d'(5,3)=2}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7671cf7af33c4df35da7eed22a6bf8bdf6fa5a19" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.332ex; height:3.009ex;" alt="{\displaystyle d'(5,3)=2}"></span>, ces partitions sont 3+1+1 et 2+2+1. </p><p><b>Les cas aux limites :</b> </p> <ul><li><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 d(0,q)=1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> <mo stretchy="false">(</mo> <mn>0</mn> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d(0,q)=1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e124e74393a6dd840e7df00c892eb19381d5e746" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.552ex; height:2.843ex;" alt="{\displaystyle d(0,q)=1}"></span>, parce que la seule partition de 0 est celle constituée d'aucune partie.</li> <li><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 d(p+1,0)=0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> <mo stretchy="false">(</mo> <mi>p</mi> <mo>+</mo> <mn>1</mn> <mo>,</mo> <mn>0</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d(p+1,0)=0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/12aac515390687304845b9f19828054f414c701e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.655ex; height:2.843ex;" alt="{\displaystyle d(p+1,0)=0}"></span> parce que toute partition d'un entier strictement positif a au moins une partie.</li> <li><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 d(p,q)=d(p,p)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>d</mi> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>p</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d(p,q)=d(p,p)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c62fa0fccc350b24eeab18c4ebcffb80bee3a4f6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.795ex; height:2.843ex;" alt="{\displaystyle d(p,q)=d(p,p)}"></span> pour <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 p<q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <mo><</mo> <mi>q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p<q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9f86c7ea4068f76f93c6a2a92c849c27303c9ba9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:5.427ex; height:2.176ex;" alt="{\displaystyle p<q}"></span>, parce que le nombre de parties d'un entier est au plus égal à sa valeur.</li></ul> <p><b>Le cas général :</b> On voit facilement que le nombre de partitions de p en <i>au plus</i> q parties est le nombre de partitions de p en <i>exactement</i> q parties plus le nombre de partitions de p en <i>au plus</i> q-1 parties. Donc </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 d(p,q)=d'(p,q)+d(p,q-1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mo>=</mo> <msup> <mi>d</mi> <mo>′</mo> </msup> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mi>d</mi> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d(p,q)=d'(p,q)+d(p,q-1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/099f7031035923271b0ad04ba74da2eefa69a8e7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.523ex; height:3.009ex;" alt="{\displaystyle d(p,q)=d'(p,q)+d(p,q-1)}"></span>.</dd></dl> <p>Or si p a exactement q parties cela veut dire que toutes ces parties sont strictement positives, on peut donc leur retirer 1. Or si on retire 1 à chacune de ces parties on obtient une partition de p - q en au plus q parties, d'où : </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 d'(p,q)=d(p-q,q)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>d</mi> <mo>′</mo> </msup> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>d</mi> <mo stretchy="false">(</mo> <mi>p</mi> <mo>−</mo> <mi>q</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d'(p,q)=d(p-q,q)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/88dd5fdcbd3654224f254fbe4b4f009cae1d6bf8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.292ex; height:3.009ex;" alt="{\displaystyle d'(p,q)=d(p-q,q)}"></span></dd></dl> <p>et finalement </p> <ul><li><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 d(p,q)=d(p-q,q)+d(p,q-1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>d</mi> <mo stretchy="false">(</mo> <mi>p</mi> <mo>−</mo> <mi>q</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mi>d</mi> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d(p,q)=d(p-q,q)+d(p,q-1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c031826e541789b2635769ddcc4a5a0f13e8b543" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:32.746ex; height:2.843ex;" alt="{\displaystyle d(p,q)=d(p-q,q)+d(p,q-1)}"></span>.</li></ul> <p>Autrement dit, <i>si <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 p\geq q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <mo>≥</mo> <mi>q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p\geq q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a9310145894a9811bbf3e939153e71630532c872" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:5.427ex; height:2.343ex;" alt="{\displaystyle p\geq q}"></span>, le nombre de partitions de p en au plus q parties est le nombre de partitions de p-q en au plus q parties plus le nombre de partitions de p en au plus q-1 parties</i>. </p><p>On a bien un énoncé récursif. </p><p><b>Retour à l'exemple</b> : on a donc (le lecteur est invité à faire tous les calculs intermédiaires) </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 d(5,3)=d(2,3)+d(5,2)=d(2,2)+d(3,2)+d(5,1)=d(0,2)+d(2,1)+d(1,2)+d(3,1)+d(4,1)+d(5,0)=...=1+1+1+1+1+0=5.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> <mo stretchy="false">(</mo> <mn>5</mn> <mo>,</mo> <mn>3</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mi>d</mi> <mo stretchy="false">(</mo> <mn>2</mn> <mo>,</mo> <mn>3</mn> <mo stretchy="false">)</mo> <mo>+</mo> <mi>d</mi> <mo stretchy="false">(</mo> <mn>5</mn> <mo>,</mo> <mn>2</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mi>d</mi> <mo stretchy="false">(</mo> <mn>2</mn> <mo>,</mo> <mn>2</mn> <mo stretchy="false">)</mo> <mo>+</mo> <mi>d</mi> <mo stretchy="false">(</mo> <mn>3</mn> <mo>,</mo> <mn>2</mn> <mo stretchy="false">)</mo> <mo>+</mo> <mi>d</mi> <mo stretchy="false">(</mo> <mn>5</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mi>d</mi> <mo stretchy="false">(</mo> <mn>0</mn> <mo>,</mo> <mn>2</mn> <mo stretchy="false">)</mo> <mo>+</mo> <mi>d</mi> <mo stretchy="false">(</mo> <mn>2</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>+</mo> <mi>d</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo stretchy="false">)</mo> <mo>+</mo> <mi>d</mi> <mo stretchy="false">(</mo> <mn>3</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>+</mo> <mi>d</mi> <mo stretchy="false">(</mo> <mn>4</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>+</mo> <mi>d</mi> <mo stretchy="false">(</mo> <mn>5</mn> <mo>,</mo> <mn>0</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>=</mo> <mn>1</mn> <mo>+</mo> <mn>1</mn> <mo>+</mo> <mn>1</mn> <mo>+</mo> <mn>1</mn> <mo>+</mo> <mn>1</mn> <mo>+</mo> <mn>0</mn> <mo>=</mo> <mn>5.</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d(5,3)=d(2,3)+d(5,2)=d(2,2)+d(3,2)+d(5,1)=d(0,2)+d(2,1)+d(1,2)+d(3,1)+d(4,1)+d(5,0)=...=1+1+1+1+1+0=5.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d28909da1501a55bf84183cc3bef91f88b5c00d7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:142.72ex; height:2.843ex;" alt="{\displaystyle d(5,3)=d(2,3)+d(5,2)=d(2,2)+d(3,2)+d(5,1)=d(0,2)+d(2,1)+d(1,2)+d(3,1)+d(4,1)+d(5,0)=...=1+1+1+1+1+0=5.}"></span>.</dd></dl> <p>Voici la forme complète de la fonction récursive : </p> <pre>d(p, q) = <b>si</b> p = 0 <b>alors</b> 1 <b>sinon</b> <b>si</b> q = 0 <b>alors</b> 0 <b>sinon</b> <b>si</b> q > p <b>alors</b> d(p, p) <b>sinon</b> d(p-q, q) + d(p, q-1) </pre> <div class="mw-heading mw-heading2"><h2 id="D'autres_fonctions_récursives_à_plusieurs_arguments"><span id="D.27autres_fonctions_r.C3.A9cursives_.C3.A0_plusieurs_arguments"></span>D'autres fonctions récursives à plusieurs arguments</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=7" title="Modifier la section : D'autres fonctions récursives à plusieurs arguments" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=7" title="Modifier le code source de la section : D'autres fonctions récursives à plusieurs arguments"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Parmi les fonctions récursives à deux arguments on trouve la <a href="/wiki/Fonction_d%27Ackermann" title="Fonction d'Ackermann">fonction d'Ackermann</a>-<a href="/wiki/R%C3%B3zsa_P%C3%A9ter" title="Rózsa Péter">Péter</a>. Le <a href="/wiki/Plus_grand_commun_diviseur" title="Plus grand commun diviseur">pgcd</a> peut aussi être présenté récursivement, </p> <pre>pgcd(p, q) = <b>si</b> p = 0 <b>alors</b> q <b>sinon</b> <b>si</b> q = 0 <b>alors</b> p <b>sinon</b> <b>si</b> q ≤ p <b>alors</b> pgcd(p-q, q) <b>sinon</b> pgcd(p, q-p) </pre> <p>de même que les <a href="/wiki/Coefficient_binomial#Propriété_récursive_des_coefficients_binomiaux_d'entiers" title="Coefficient binomial">coefficients binomiaux</a> quand ils sont définis par la formule de Pascal. </p><p>La <a href="/wiki/Fonction_de_Sudan" title="Fonction de Sudan">fonction de Sudan</a> est une fonction à trois arguments (l'indice <i>n</i> est le troisième argument). </p> <div class="mw-heading mw-heading2"><h2 id="Algorithmes_récursifs_non_numériques"><span id="Algorithmes_r.C3.A9cursifs_non_num.C3.A9riques"></span>Algorithmes récursifs non numériques</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=8" title="Modifier la section : Algorithmes récursifs non numériques" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=8" title="Modifier le code source de la section : Algorithmes récursifs non numériques"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Nous avons vu dans l'introduction, une présentation informelle d'un algorithme récursif engendrant les permutations, puis nous avons vu des algorithmes récursifs sur les entiers naturels. Nous allons maintenant présenter des algorithmes récursifs sur d'autres structures de données que les entiers naturels. </p> <div class="mw-heading mw-heading3"><h3 id="Algorithmes_récursifs_sur_les_listes"><span id="Algorithmes_r.C3.A9cursifs_sur_les_listes"></span>Algorithmes récursifs sur les <a href="/wiki/Liste_(informatique)" title="Liste (informatique)">listes</a></h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=9" title="Modifier la section : Algorithmes récursifs sur les listes" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=9" title="Modifier le code source de la section : Algorithmes récursifs sur les listes"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading4"><h4 id="++"><span id=".2B.2B"></span>++</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=10" title="Modifier la section : ++" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=10" title="Modifier le code source de la section : ++"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>L'opérateur <b>++</b> concatène deux listes, autrement dit, prolonge la première liste par la seconde liste. </p> <dl><dd><i>[ ]</i> <b>++</b> ℓ2 = ℓ2</dd> <dd>(x:ℓ1) <b>++</b> ℓ2 = x:(ℓ1 <b>++</b> <i>ℓ2)</i></dd></dl> <p>Le cas de base est <i>[ ]</i> <b>++</b> ℓ2 = ℓ2. </p> <div class="mw-heading mw-heading4"><h4 id="map">map</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=11" title="Modifier la section : map" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=11" title="Modifier le code source de la section : map"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Étant données une fonction et une liste, considérons un algorithme qui produit la liste obtenue en appliquant ladite fonction à tous les éléments de la liste donnée. Traditionnellement cette fonction s'appelle <b>map</b> (en français « applique »). Si la liste donnée est vide, le résultat est la liste vide (qui se note <i>[ ]</i>) ; c'est le cas de base. Si la fonction s'appelle <i>f</i> et si la liste donnée est constituée de <i>x</i> suivi d'une liste <i>ℓ</i> alors le résultat est la liste constituée de <i> f x</i><sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite_crochet">[</span>note 2<span class="cite_crochet">]</span></a></sup> suivi de la liste <b>map</b> <i>f ℓ</i>. </p> <dl><dd><b>map</b> <i>f [ ] = [ ]</i></dd> <dd><b>map</b> <i>f (x:ℓ) = f x : (</i><b>map</b> <i>f ℓ)</i></dd></dl> <div class="mw-heading mw-heading4"><h4 id="ins">ins</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=12" title="Modifier la section : ins" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=12" title="Modifier le code source de la section : ins"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>La fonction <b>ins</b> insère un élément dans une liste à toutes les positions, produisant une liste de listes. </p> <dl><dd><b>ins</b> <i>x [ ] = <a href="/wiki/X_(math%C3%A9matique)" title="X (mathématique)">x</a></i></dd> <dd><b>ins</b> <i>x (y:ℓ) = (x:y:ℓ) :</i> <b>map</b> <i>((:) y) (</i><b>ins</b> <i>x ℓ)</i></dd></dl> <div class="mw-heading mw-heading4"><h4 id="concat">concat</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=13" title="Modifier la section : concat" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=13" title="Modifier le code source de la section : concat"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>La fonction <b>concat</b> prend une liste de listes et concatène ces listes en une seule liste. </p> <dl><dd><b>concat</b> <i>[ ] = [ ]</i></dd> <dd><b>concat</b> <i>(ℓ:ℓℓ) = ℓ ++ (concat ℓℓ)</i></dd></dl> <div class="mw-heading mw-heading4"><h4 id="permutations">permutations</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=14" title="Modifier la section : permutations" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=14" title="Modifier le code source de la section : permutations"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><b>permutations</b> est l'algorithme présenté dans le premier exemple. Il prend une liste et retourne la liste de toutes les permutations de cette liste. </p> <dl><dd><b>permutations</b> <i>[x] = <a href="/wiki/X_(math%C3%A9matique)" title="X (mathématique)">x</a></i></dd> <dd><b>permutations</b> <i>x:ℓ =</i> <b>concat</b> <i>(</i><b>map</b> <i>(</i><b>ins</b> <i>x) (</i><b>permutations</b> <i>ℓ))</i></dd></dl> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/Fichier:Arbre_binaire_bravo.png" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/d/db/Arbre_binaire_bravo.png/220px-Arbre_binaire_bravo.png" decoding="async" width="220" height="108" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/d/db/Arbre_binaire_bravo.png/330px-Arbre_binaire_bravo.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/d/db/Arbre_binaire_bravo.png/440px-Arbre_binaire_bravo.png 2x" data-file-width="647" data-file-height="317" /></a><figcaption>Arbre binaire portant les étiquettes B, R, A, V, O</figcaption></figure> <div class="mw-heading mw-heading3"><h3 id="Algorithmes_récursifs_sur_les_arbres_binaires"><span id="Algorithmes_r.C3.A9cursifs_sur_les_arbres_binaires"></span>Algorithmes récursifs sur les <a href="/wiki/Arbre_binaire" title="Arbre binaire">arbres binaires</a></h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=15" title="Modifier la section : Algorithmes récursifs sur les arbres binaires" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=15" title="Modifier le code source de la section : Algorithmes récursifs sur les arbres binaires"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading4"><h4 id="taille">taille</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=16" title="Modifier la section : taille" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=16" title="Modifier le code source de la section : taille"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>La taille d'un arbre binaire est le nombre de ses nœuds internes </p> <dl><dd><b>taille</b> <i>(Feuille x) = 0</i></dd> <dd><b>taille</b> <i>(t1 • t2) = (</i> <b>taille</b> <i>t1) + (</i> <b>taille</b> <i>t2)</i></dd></dl> <div class="mw-heading mw-heading4"><h4 id="motDesFeuilles">motDesFeuilles</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=17" title="Modifier la section : motDesFeuilles" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=17" title="Modifier le code source de la section : motDesFeuilles"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Étant donné un arbre binaire, on peut construire son <i>mot des feuilles</i>. Ainsi le mot des feuilles de l'arbre de la figure ci-contre est <i>BRAVO</i> ou, plus précisément, la liste <i>[`B`,`R`,`A`,`V`,`O`]</i>. L'algorithme récursif <b>motDesFeuilles</b> prend un arbre binaire et retourne une liste. </p> <dl><dd><b>motDesFeuilles</b> <i>(Feuille x) = [x]</i></dd> <dd><b>motDesFeuilles</b> <i>(t1 • t2) = (</i> <b>motDesFeuilles</b> <i>t1) ++ (</i> <b>motDesFeuilles</b> <i>t2)</i></dd></dl> <div class="mw-heading mw-heading2"><h2 id="Prouver_la_correction_d'un_algorithme_récursif"><span id="Prouver_la_correction_d.27un_algorithme_r.C3.A9cursif"></span>Prouver la correction d'un algorithme récursif</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=18" title="Modifier la section : Prouver la correction d'un algorithme récursif" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=18" title="Modifier le code source de la section : Prouver la correction d'un algorithme récursif"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Prouver le bon fonctionnement d'un algorithme récursif nécessite de vérifier deux propriétés : premièrement <i>l'algorithme se termine</i> et deuxièmement <i>si l'algorithme se termine, il fait bien ce qu'on attend de lui</i> (correction partielle). Dans le cas des algorithmes récursifs, ces méthodes sont spécifiques. </p> <div class="mw-heading mw-heading3"><h3 id="Problème_de_la_terminaison"><span id="Probl.C3.A8me_de_la_terminaison"></span>Problème de la terminaison</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=19" title="Modifier la section : Problème de la terminaison" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=19" title="Modifier le code source de la section : Problème de la terminaison"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Pour prouver la <a href="/wiki/Terminaison_d%27un_algorithme" title="Terminaison d'un algorithme">terminaison</a> d'un algorithme récursif, la méthode la plus usuelle est la suivante: chacun des ensembles dans lesquels les paramètres prennent leurs valeurs sont équipés d'une <a href="/wiki/Relation_d%27ordre" title="Relation d'ordre">relation d'ordre</a>. Cet ordre ne doit avoir que des <i>chaînes descendantes finies</i> (on dit qu'il est <a href="/wiki/Relation_bien_fond%C3%A9e" title="Relation bien fondée">bien fondé</a>) et être tel que les invocations internes de l'algorithme se font avec des valeurs plus petites des paramètres, pour l'ordre en question. </p> <div class="mw-heading mw-heading3"><h3 id="Théorème_de_terminaison"><span id="Th.C3.A9or.C3.A8me_de_terminaison"></span>Théorème de terminaison</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=20" title="Modifier la section : Théorème de terminaison" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=20" title="Modifier le code source de la section : Théorème de terminaison"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Soient <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\,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mspace width="thinmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f\,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ba5397b34cab7d96daac496a937b0c0fa076dff7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.666ex; height:2.509ex;" alt="{\displaystyle f\,}"></span> un algorithme récursif défini sur un ensemble <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 A\,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> <mspace width="thinmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A\,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c6aaf5ce10d6add44b973e28fb3d95f37abf3721" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.13ex; height:2.176ex;" alt="{\displaystyle A\,}"></span> et <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 <\,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo><</mo> <mspace width="thinmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle <\,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c4a3b12f3f0b7214f99d6f699917080b1df02c74" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.195ex; height:1.843ex;" alt="{\displaystyle <\,}"></span> un <a href="/wiki/Ordre_bien_fond%C3%A9" class="mw-redirect" title="Ordre bien fondé">ordre bien fondé</a> sur <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 \,A}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mspace width="thinmathspace" /> <mi>A</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \,A}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f9640470f4f8570957bc5602d1b065e8a8a7035e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.13ex; height:2.176ex;" alt="{\displaystyle \,A}"></span>. </p><p><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 x\in A}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>∈</mo> <mi>A</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x\in A}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/27bcc9b2afb295d4234bc294860cd0c63bcad2ca" 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 x\in A}"></span> étant donné, on note, <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 A_{x}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>A</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A_{x}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/626cb5d94c04152accd89eee76eb7a2613376484" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.916ex; height:2.509ex;" alt="{\displaystyle A_{x}}"></span> l'ensemble des <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 y\,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>y</mi> <mspace width="thinmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y\,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1c8c233e7cc39fac816991250d86e09b515d02e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.543ex; height:2.009ex;" alt="{\displaystyle y\,}"></span> tels que <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(x)\,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mspace width="thinmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f(x)\,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/78b2b66021c2cac2b5654495678c63ff142952e5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.805ex; height:2.843ex;" alt="{\displaystyle f(x)\,}"></span> appelle <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(y)\,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> <mspace width="thinmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f(y)\,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cd064de381e49cba8f557b9926a8846f7e5ba8e4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.63ex; height:2.843ex;" alt="{\displaystyle f(y)\,}"></span>. </p><p>Soit <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 x\in A}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>∈</mo> <mi>A</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x\in A}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/27bcc9b2afb295d4234bc294860cd0c63bcad2ca" 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 x\in A}"></span>, <b>si</b>, <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 \forall y\in A\ (y\in A_{x}\Rightarrow y<x)\,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">∀</mi> <mi>y</mi> <mo>∈</mo> <mi>A</mi> <mtext> </mtext> <mo stretchy="false">(</mo> <mi>y</mi> <mo>∈</mo> <msub> <mi>A</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> </mrow> </msub> <mo stretchy="false">⇒</mo> <mi>y</mi> <mo><</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mspace width="thinmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \forall y\in A\ (y\in A_{x}\Rightarrow y<x)\,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/899c1f60bf64a45fae5c7e7f4eef1c8943093f63" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.918ex; height:2.843ex;" alt="{\displaystyle \forall y\in A\ (y\in A_{x}\Rightarrow y<x)\,}"></span>, <b>alors</b> <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(x)\,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mspace width="thinmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f(x)\,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/78b2b66021c2cac2b5654495678c63ff142952e5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.805ex; height:2.843ex;" alt="{\displaystyle f(x)\,}"></span> se termine. </p> <div class="mw-heading mw-heading4"><h4 id="Terminaison_de_la_fonction_d_qui_calcule_le_nombre_de_décompositions_de_p_en_au_plus_q_sommants"><span id="Terminaison_de_la_fonction_d_qui_calcule_le_nombre_de_d.C3.A9compositions_de_p_en_au_plus_q_sommants"></span>Terminaison de la fonction d qui calcule le nombre de décompositions de p en au plus q sommants</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=21" title="Modifier la section : Terminaison de la fonction d qui calcule le nombre de décompositions de p en au plus q sommants" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=21" title="Modifier le code source de la section : Terminaison de la fonction d qui calcule le nombre de décompositions de p en au plus q sommants"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>L'ordre que l'on prend est l'<a href="/wiki/Ordre_lexicographique" title="Ordre lexicographique">ordre lexicographique</a> sur <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} \times \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> <mo>×</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">N</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {N} \times \mathbb {N} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5b25f8c4219e47350185be7ebdc5250c8d59ab35" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.197ex; height:2.176ex;" alt="{\displaystyle \mathbb {N} \times \mathbb {N} }"></span>. On a </p> <ul><li><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 (p,q)>(p',q')}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mo>></mo> <mo stretchy="false">(</mo> <msup> <mi>p</mi> <mo>′</mo> </msup> <mo>,</mo> <msup> <mi>q</mi> <mo>′</mo> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (p,q)>(p',q')}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/434ae026fa40a6766306243298555bad0eb4d81b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.642ex; height:3.009ex;" alt="{\displaystyle (p,q)>(p',q')}"></span> si et seulement si <ul><li><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 p>p'}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <mo>></mo> <msup> <mi>p</mi> <mo>′</mo> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p>p'}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/988725c5c8770a3b94836dfcafcc35dfd5e1c1d4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:6.211ex; height:2.843ex;" alt="{\displaystyle p>p'}"></span></li> <li>ou <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 p=p'}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <mo>=</mo> <msup> <mi>p</mi> <mo>′</mo> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p=p'}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d4da0e3648b181865af8fb522277196e011af949" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:6.211ex; height:2.843ex;" alt="{\displaystyle p=p'}"></span> et <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 q>q'}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>q</mi> <mo>></mo> <msup> <mi>q</mi> <mo>′</mo> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle q>q'}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fc703024f8e831ef32bc630240acadbeef846130" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.932ex; height:2.843ex;" alt="{\displaystyle q>q'}"></span>.</li></ul></li></ul> <p>Cet ordre est bien fondé. </p> <div class="mw-heading mw-heading4"><h4 id="Terminaison_de_la_fonction_Syracuse">Terminaison de la fonction Syracuse</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=22" title="Modifier la section : Terminaison de la fonction Syracuse" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=22" title="Modifier le code source de la section : Terminaison de la fonction Syracuse"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>La terminaison d'un algorithme récursif peut être un problème extrêmement difficile. Ainsi personne n'a jusqu'à présent été capable de démontrer que la fonction Syracuse présentée plus haut se termine pour toute valeur de <i>n</i>. Si c'était le cas, elle définirait effectivement la fonction identiquement égale à 1. </p> <div class="mw-heading mw-heading3"><h3 id="Problème_de_la_correction_partielle"><span id="Probl.C3.A8me_de_la_correction_partielle"></span>Problème de la correction partielle</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=23" title="Modifier la section : Problème de la correction partielle" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=23" title="Modifier le code source de la section : Problème de la correction partielle"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Il faut montrer que si les appels internes à l'algorithme font ce qu'on attend d'eux, alors l'algorithme entier fait ce qu'on attend de lui. Dans le cas de Monsieur Jourdain, il faut montrer que si on part d'une suite de toutes les permutations de <i>n-1</i> éléments, on aboutira à une suite de toutes les permutations de <i>n</i> éléments. </p> <div class="mw-heading mw-heading4"><h4 id="Correction_partielle_sur_l'exemple_du_pgcd"><span id="Correction_partielle_sur_l.27exemple_du_pgcd"></span>Correction partielle sur l'exemple du pgcd</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=24" title="Modifier la section : Correction partielle sur l'exemple du pgcd" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=24" title="Modifier le code source de la section : Correction partielle sur l'exemple du pgcd"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Prenons l'exemple du <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 {\mathsf {pgcd}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">p</mi> <mi mathvariant="sans-serif">g</mi> <mi mathvariant="sans-serif">c</mi> <mi mathvariant="sans-serif">d</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {pgcd}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1bd276931560447fa62a3bc3fde1c149aae858fa" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.599ex; height:2.509ex;" alt="{\displaystyle {\mathsf {pgcd}}}"></span>, il s'agit de montrer que si <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 \,p}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mspace width="thinmathspace" /> <mi>p</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \,p}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/01f9cce76f4a3b0a80f475e5b344a0cc0bc00c0b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.557ex; height:2.009ex;" alt="{\displaystyle \,p}"></span> et <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 \,q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mspace width="thinmathspace" /> <mi>q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \,q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3aab8df7bc9ebff8f710c7b8071270f7236ae23e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.457ex; height:2.009ex;" alt="{\displaystyle \,q}"></span> sont positifs alors </p> <ul><li><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 {\mathsf {pgcd}}(p,q)|p\wedge {\mathsf {pgcd}}(p,q)|q\wedge (\forall r\geq 0.(r|p\wedge r|q)\Rightarrow r|{\mathsf {pgcd}}(p,q))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">p</mi> <mi mathvariant="sans-serif">g</mi> <mi mathvariant="sans-serif">c</mi> <mi mathvariant="sans-serif">d</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>p</mi> <mo>∧</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">p</mi> <mi mathvariant="sans-serif">g</mi> <mi mathvariant="sans-serif">c</mi> <mi mathvariant="sans-serif">d</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>q</mi> <mo>∧</mo> <mo stretchy="false">(</mo> <mi mathvariant="normal">∀</mi> <mi>r</mi> <mo>≥</mo> <mn>0.</mn> <mo stretchy="false">(</mo> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>p</mi> <mo>∧</mo> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>q</mi> <mo stretchy="false">)</mo> <mo stretchy="false">⇒</mo> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">p</mi> <mi mathvariant="sans-serif">g</mi> <mi mathvariant="sans-serif">c</mi> <mi mathvariant="sans-serif">d</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {pgcd}}(p,q)|p\wedge {\mathsf {pgcd}}(p,q)|q\wedge (\forall r\geq 0.(r|p\wedge r|q)\Rightarrow r|{\mathsf {pgcd}}(p,q))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cfd7314d8d37136beda11959def5f2820fa5ecdf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:62.13ex; height:2.843ex;" alt="{\displaystyle {\mathsf {pgcd}}(p,q)|p\wedge {\mathsf {pgcd}}(p,q)|q\wedge (\forall r\geq 0.(r|p\wedge r|q)\Rightarrow r|{\mathsf {pgcd}}(p,q))}"></span>,</li></ul> <p>ce qui est la caractérisation du plus grand diviseur commun de deux nombres où <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 \,s|t}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mspace width="thinmathspace" /> <mi>s</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>t</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \,s|t}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/81db3430e43a97d71884e10a732dc0b960ee8744" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.964ex; height:2.843ex;" alt="{\displaystyle \,s|t}"></span> signifie que <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 \,s}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mspace width="thinmathspace" /> <mi>s</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \,s}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a8ecb5d31c343d45331201523dd8c8a4a029a5e5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.478ex; height:1.676ex;" alt="{\displaystyle \,s}"></span> divise <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 \,t}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mspace width="thinmathspace" /> <mi>t</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \,t}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e3f7176c0c2c8a0795f31e4bd21ef63765fdca5f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.227ex; height:2.009ex;" alt="{\displaystyle \,t}"></span> (on a, en particulier, <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 \,p|0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mspace width="thinmathspace" /> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \,p|0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b2189eaa39bf6841e850dfdd4b8a5b5cd1e396a0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.366ex; height:2.843ex;" alt="{\displaystyle \,p|0}"></span> pour tout <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 \,p}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mspace width="thinmathspace" /> <mi>p</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \,p}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/01f9cce76f4a3b0a80f475e5b344a0cc0bc00c0b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.557ex; height:2.009ex;" alt="{\displaystyle \,p}"></span>). Notons <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 {\mathcal {P}}_{\mathsf {pgcd}}(p,q)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">P</mi> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">p</mi> <mi mathvariant="sans-serif">g</mi> <mi mathvariant="sans-serif">c</mi> <mi mathvariant="sans-serif">d</mi> </mrow> </mrow> </msub> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {P}}_{\mathsf {pgcd}}(p,q)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b13d667802d1e46a11eca454b7f01fddf63f01e8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:10.184ex; height:3.009ex;" alt="{\displaystyle {\mathcal {P}}_{\mathsf {pgcd}}(p,q)}"></span> cette propriété. </p><p>Pour montrer la correction de l'algorithme ci-dessus, on suppose <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 \forall (p',q')\in \mathbf {N} \times \mathbf {N} .{\mathcal {P}}_{\mathsf {pgcd}}(p',q')}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">∀</mi> <mo stretchy="false">(</mo> <msup> <mi>p</mi> <mo>′</mo> </msup> <mo>,</mo> <msup> <mi>q</mi> <mo>′</mo> </msup> <mo stretchy="false">)</mo> <mo>∈</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="bold">N</mi> </mrow> <mo>×</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="bold">N</mi> </mrow> <mo>.</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">P</mi> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">p</mi> <mi mathvariant="sans-serif">g</mi> <mi mathvariant="sans-serif">c</mi> <mi mathvariant="sans-serif">d</mi> </mrow> </mrow> </msub> <mo stretchy="false">(</mo> <msup> <mi>p</mi> <mo>′</mo> </msup> <mo>,</mo> <msup> <mi>q</mi> <mo>′</mo> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \forall (p',q')\in \mathbf {N} \times \mathbf {N} .{\mathcal {P}}_{\mathsf {pgcd}}(p',q')}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7aee3b3643481bca9af86f2ca6c2449ba80d7a89" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:30.215ex; height:3.176ex;" alt="{\displaystyle \forall (p',q')\in \mathbf {N} \times \mathbf {N} .{\mathcal {P}}_{\mathsf {pgcd}}(p',q')}"></span> et on essaie de montrer <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 {\mathcal {P}}_{\mathsf {f}}(p,q)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">P</mi> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">f</mi> </mrow> </mrow> </msub> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {P}}_{\mathsf {f}}(p,q)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d2b006b190a87a3efc47db446780ea30d4dccd12" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.503ex; height:2.843ex;" alt="{\displaystyle {\mathcal {P}}_{\mathsf {f}}(p,q)}"></span> où <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 \,{\mathsf {f}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mspace width="thinmathspace" /> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">f</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \,{\mathsf {f}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c0bf53c315f8b91e1c87d85cb537e64f22a2fe2b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.194ex; height:2.176ex;" alt="{\displaystyle \,{\mathsf {f}}}"></span> est la fonction <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 \mathbf {si} \ p=0\ \mathbf {alors} \ q\ \mathbf {sinon} \ \mathbf {si} \ q=0\ \mathbf {alors} \ p\ \mathbf {sinon} \ \mathbf {si} \ q\leq p\ \mathbf {alors} \ {\mathsf {pgcd}}(p-q,q)\ \mathbf {sinon} \ {\mathsf {pgcd}}(p,q-p)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="bold">s</mi> <mi mathvariant="bold">i</mi> </mrow> <mtext> </mtext> <mi>p</mi> <mo>=</mo> <mn>0</mn> <mtext> </mtext> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="bold">a</mi> <mi mathvariant="bold">l</mi> <mi mathvariant="bold">o</mi> <mi mathvariant="bold">r</mi> <mi mathvariant="bold">s</mi> </mrow> <mtext> </mtext> <mi>q</mi> <mtext> </mtext> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="bold">s</mi> <mi mathvariant="bold">i</mi> <mi mathvariant="bold">n</mi> <mi mathvariant="bold">o</mi> <mi mathvariant="bold">n</mi> </mrow> <mtext> </mtext> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="bold">s</mi> <mi mathvariant="bold">i</mi> </mrow> <mtext> </mtext> <mi>q</mi> <mo>=</mo> <mn>0</mn> <mtext> </mtext> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="bold">a</mi> <mi mathvariant="bold">l</mi> <mi mathvariant="bold">o</mi> <mi mathvariant="bold">r</mi> <mi mathvariant="bold">s</mi> </mrow> <mtext> </mtext> <mi>p</mi> <mtext> </mtext> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="bold">s</mi> <mi mathvariant="bold">i</mi> <mi mathvariant="bold">n</mi> <mi mathvariant="bold">o</mi> <mi mathvariant="bold">n</mi> </mrow> <mtext> </mtext> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="bold">s</mi> <mi mathvariant="bold">i</mi> </mrow> <mtext> </mtext> <mi>q</mi> <mo>≤</mo> <mi>p</mi> <mtext> </mtext> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="bold">a</mi> <mi mathvariant="bold">l</mi> <mi mathvariant="bold">o</mi> <mi mathvariant="bold">r</mi> <mi mathvariant="bold">s</mi> </mrow> <mtext> </mtext> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">p</mi> <mi mathvariant="sans-serif">g</mi> <mi mathvariant="sans-serif">c</mi> <mi mathvariant="sans-serif">d</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo>−</mo> <mi>q</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mtext> </mtext> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="bold">s</mi> <mi mathvariant="bold">i</mi> <mi mathvariant="bold">n</mi> <mi mathvariant="bold">o</mi> <mi mathvariant="bold">n</mi> </mrow> <mtext> </mtext> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">p</mi> <mi mathvariant="sans-serif">g</mi> <mi mathvariant="sans-serif">c</mi> <mi mathvariant="sans-serif">d</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo>−</mo> <mi>p</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbf {si} \ p=0\ \mathbf {alors} \ q\ \mathbf {sinon} \ \mathbf {si} \ q=0\ \mathbf {alors} \ p\ \mathbf {sinon} \ \mathbf {si} \ q\leq p\ \mathbf {alors} \ {\mathsf {pgcd}}(p-q,q)\ \mathbf {sinon} \ {\mathsf {pgcd}}(p,q-p)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/582dd992b95273e17f2816eb1e54e8fc64e00017" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:94.644ex; height:2.843ex;" alt="{\displaystyle \mathbf {si} \ p=0\ \mathbf {alors} \ q\ \mathbf {sinon} \ \mathbf {si} \ q=0\ \mathbf {alors} \ p\ \mathbf {sinon} \ \mathbf {si} \ q\leq p\ \mathbf {alors} \ {\mathsf {pgcd}}(p-q,q)\ \mathbf {sinon} \ {\mathsf {pgcd}}(p,q-p)}"></span>. </p> <dl><dd>On procède par cas.</dd></dl> <ul><li><ul><li>Si <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 \,p=0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mspace width="thinmathspace" /> <mi>p</mi> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \,p=0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/194dac89d023cd1c2377f97821243002a59da852" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.817ex; height:2.509ex;" alt="{\displaystyle \,p=0}"></span> alors <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 {\mathsf {f}}(p,q)=q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">f</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {f}}(p,q)=q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8793925677180c0b00d80e175f859053b5c64b51" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.057ex; height:2.843ex;" alt="{\displaystyle {\mathsf {f}}(p,q)=q}"></span> et donc <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 {\mathsf {f}}(p,q)|0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">f</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {f}}(p,q)|0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/74216044cefcdb493bb3311a7340ab7252d489d5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.699ex; height:2.843ex;" alt="{\displaystyle {\mathsf {f}}(p,q)|0}"></span>, mais aussi <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 {\mathsf {f}}(p,q)|q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">f</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {f}}(p,q)|q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/517b9a7b4779adbaa189c8bd85f1935613a3a398" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.606ex; height:2.843ex;" alt="{\displaystyle {\mathsf {f}}(p,q)|q}"></span>. De plus, si <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 \,r|0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mspace width="thinmathspace" /> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \,r|0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/96a3840410b40239d47d6a0b58066cb216499f34" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.245ex; height:2.843ex;" alt="{\displaystyle \,r|0}"></span> et si <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 \,r|q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mspace width="thinmathspace" /> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \,r|q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9a4fb8ce56a9d950445eb091145d8645015ab16f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.152ex; height:2.843ex;" alt="{\displaystyle \,r|q}"></span> alors clairement <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 r|{\mathsf {f}}(p,q)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">f</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r|{\mathsf {f}}(p,q)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ccc849b4c5f8412e2b0a6e948aa6d0d16d605976" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.585ex; height:2.843ex;" alt="{\displaystyle r|{\mathsf {f}}(p,q)}"></span>, puisque précisément <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 {\mathsf {f}}(p,q)=q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">f</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {f}}(p,q)=q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8793925677180c0b00d80e175f859053b5c64b51" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.057ex; height:2.843ex;" alt="{\displaystyle {\mathsf {f}}(p,q)=q}"></span>.</li> <li>Si <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 \,q=0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mspace width="thinmathspace" /> <mi>q</mi> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \,q=0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6b9eb7f4fb019e237ef4cfcbfccc9526e3d30775" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.718ex; height:2.509ex;" alt="{\displaystyle \,q=0}"></span> on obtient le même résultat.</li> <li>Si <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 0<q\leq p}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>0</mn> <mo><</mo> <mi>q</mi> <mo>≤</mo> <mi>p</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 0<q\leq p}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c5b08da035c90c14ee90e7fa8f41ab6c69ecf0bc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.598ex; height:2.509ex;" alt="{\displaystyle 0<q\leq p}"></span>, on a <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 {\mathsf {f}}(p,q)={\mathsf {pgcd}}(p-q,q)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">f</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">p</mi> <mi mathvariant="sans-serif">g</mi> <mi mathvariant="sans-serif">c</mi> <mi mathvariant="sans-serif">d</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo>−</mo> <mi>q</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {f}}(p,q)={\mathsf {pgcd}}(p-q,q)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/52b4b603df1ed6730eb87ec3a86dcaa2ee9d94de" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.579ex; height:2.843ex;" alt="{\displaystyle {\mathsf {f}}(p,q)={\mathsf {pgcd}}(p-q,q)}"></span>, d'autre part si on a <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 {\mathsf {pgcd}}(p-q,q)|p-q\wedge {\mathsf {pgcd}}(p-q,q)|q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">p</mi> <mi mathvariant="sans-serif">g</mi> <mi mathvariant="sans-serif">c</mi> <mi mathvariant="sans-serif">d</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo>−</mo> <mi>q</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>p</mi> <mo>−</mo> <mi>q</mi> <mo>∧</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">p</mi> <mi mathvariant="sans-serif">g</mi> <mi mathvariant="sans-serif">c</mi> <mi mathvariant="sans-serif">d</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo>−</mo> <mi>q</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {pgcd}}(p-q,q)|p-q\wedge {\mathsf {pgcd}}(p-q,q)|q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/05718c875f294c92a2d4612ce9e1063f1062fd3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:37.207ex; height:2.843ex;" alt="{\displaystyle {\mathsf {pgcd}}(p-q,q)|p-q\wedge {\mathsf {pgcd}}(p-q,q)|q}"></span> alors <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 {\mathsf {pgcd}}(p-q,q)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">p</mi> <mi mathvariant="sans-serif">g</mi> <mi mathvariant="sans-serif">c</mi> <mi mathvariant="sans-serif">d</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo>−</mo> <mi>q</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {pgcd}}(p-q,q)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a005f28a67766f5f290637ace264728183e4d4ac" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.591ex; height:2.843ex;" alt="{\displaystyle {\mathsf {pgcd}}(p-q,q)}"></span> divise la somme donc <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 {\mathsf {f}}(p,q)|p\wedge {\mathsf {f}}(p,q)|q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">f</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>p</mi> <mo>∧</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">f</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {f}}(p,q)|p\wedge {\mathsf {f}}(p,q)|q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5d80156dae8cb8b1a2f5e8fd05440fa86eb6330f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.894ex; height:2.843ex;" alt="{\displaystyle {\mathsf {f}}(p,q)|p\wedge {\mathsf {f}}(p,q)|q}"></span>. D'autre part, si <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 \,r|p}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mspace width="thinmathspace" /> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>p</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \,r|p}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/25c80849253b0e9c2ce2d329346d27decbb0f128" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.252ex; height:2.843ex;" alt="{\displaystyle \,r|p}"></span> et <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 \,r|q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mspace width="thinmathspace" /> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \,r|q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9a4fb8ce56a9d950445eb091145d8645015ab16f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.152ex; height:2.843ex;" alt="{\displaystyle \,r|q}"></span> alors par hypothèse <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 \,r|(p-q)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mspace width="thinmathspace" /> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo>−</mo> <mi>q</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \,r|(p-q)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9bd434c1bbeba7c4a95586d49a3005f39feb024d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.971ex; height:2.843ex;" alt="{\displaystyle \,r|(p-q)}"></span> et donc <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 r|{\mathsf {pgcd}}(p-q,q))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">p</mi> <mi mathvariant="sans-serif">g</mi> <mi mathvariant="sans-serif">c</mi> <mi mathvariant="sans-serif">d</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo>−</mo> <mi>q</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r|{\mathsf {pgcd}}(p-q,q))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/34a1c8e1b4c7d20b07f67ef21e0f6951f216fb97" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.191ex; height:2.843ex;" alt="{\displaystyle r|{\mathsf {pgcd}}(p-q,q))}"></span> et donc <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 r|{\mathsf {f}}(p,q))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">f</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r|{\mathsf {f}}(p,q))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c00ae56a30f747288c6215c15cc8fab17bdda8be" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.489ex; height:2.843ex;" alt="{\displaystyle r|{\mathsf {f}}(p,q))}"></span>, c.q.f.d.</li> <li>Si <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 \,0<q<p}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mspace width="thinmathspace" /> <mn>0</mn> <mo><</mo> <mi>q</mi> <mo><</mo> <mi>p</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \,0<q<p}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/94d51c9bcac77f56725c5c869c21fdba70c324a6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.985ex; height:2.509ex;" alt="{\displaystyle \,0<q<p}"></span>, on raisonne comme ci-dessus en inversant les rôles de <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 \,p}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mspace width="thinmathspace" /> <mi>p</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \,p}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/01f9cce76f4a3b0a80f475e5b344a0cc0bc00c0b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.557ex; height:2.009ex;" alt="{\displaystyle \,p}"></span> et <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 \,q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mspace width="thinmathspace" /> <mi>q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \,q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3aab8df7bc9ebff8f710c7b8071270f7236ae23e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.457ex; height:2.009ex;" alt="{\displaystyle \,q}"></span>.</li></ul></li></ul> <p>De la démonstration ci-dessus, on déduit que si l'algorithme de <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 {\mathsf {pgcd}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">p</mi> <mi mathvariant="sans-serif">g</mi> <mi mathvariant="sans-serif">c</mi> <mi mathvariant="sans-serif">d</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {pgcd}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1bd276931560447fa62a3bc3fde1c149aae858fa" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.599ex; height:2.509ex;" alt="{\displaystyle {\mathsf {pgcd}}}"></span> se termine alors il satisfait : </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 \forall (p,q)\in \mathbf {N} \times \mathbf {N} .{\mathcal {P}}_{\mathsf {pgcd}}(p,q)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">∀</mi> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mo>∈</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="bold">N</mi> </mrow> <mo>×</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="bold">N</mi> </mrow> <mo>.</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">P</mi> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">p</mi> <mi mathvariant="sans-serif">g</mi> <mi mathvariant="sans-serif">c</mi> <mi mathvariant="sans-serif">d</mi> </mrow> </mrow> </msub> <mo stretchy="false">(</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \forall (p,q)\in \mathbf {N} \times \mathbf {N} .{\mathcal {P}}_{\mathsf {pgcd}}(p,q)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cd16d42944238edf01f52a31181ea8d483e83009" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:27.457ex; height:3.009ex;" alt="{\displaystyle \forall (p,q)\in \mathbf {N} \times \mathbf {N} .{\mathcal {P}}_{\mathsf {pgcd}}(p,q)}"></span> et donc <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 {\mathsf {pgcd}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">p</mi> <mi mathvariant="sans-serif">g</mi> <mi mathvariant="sans-serif">c</mi> <mi mathvariant="sans-serif">d</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {pgcd}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1bd276931560447fa62a3bc3fde1c149aae858fa" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.599ex; height:2.509ex;" alt="{\displaystyle {\mathsf {pgcd}}}"></span> calcule bien le <i>plus grand commun diviseur</i>.</dd></dl> <div class="mw-heading mw-heading2"><h2 id="Efficacité"><span id="Efficacit.C3.A9"></span>Efficacité</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=25" title="Modifier la section : Efficacité" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=25" title="Modifier le code source de la section : Efficacité"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Simplicité_de_description_versus_efficacité"><span id="Simplicit.C3.A9_de_description_versus_efficacit.C3.A9"></span>Simplicité de description versus efficacité</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=26" title="Modifier la section : Simplicité de description versus efficacité" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=26" title="Modifier le code source de la section : Simplicité de description versus efficacité"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>La mise en œuvre des algorithmes récursifs nécessite le plus souvent<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite_crochet">[</span>note 3<span class="cite_crochet">]</span></a></sup> une <a href="/wiki/Pile_(informatique)" title="Pile (informatique)">pile</a>. C'est la difficulté d'implanter cette pile ou d'éviter son emploi qui a fait dire pendant longtemps que les programmes récursifs étaient moins efficaces que les programmes itératifs, mais la situation a changé. En fait, le débat sur le choix entre codage récursif ou itératif est aussi vieux que l'informatique et les progrès de la <a href="/wiki/Compilateur" title="Compilateur">compilation</a> des langages de programmation réduit encore la différence d'efficacité. Voici quelques arguments en faveur de la présentation récursive : </p> <ul><li>La présentation récursive permet d'expliquer simplement des algorithmes beaucoup plus astucieux et efficaces, comme cela a été montré par <a href="/wiki/Tony_Hoare" class="mw-redirect" title="Tony Hoare">Tony Hoare</a> avec son algorithme de <a href="/wiki/Tri_rapide" title="Tri rapide">tri rapide</a>.</li> <li>Les compilateurs d'aujourd'hui sont tellement astucieux que plus le programme leur est présenté de façon abstraite et sans effets de bord, plus ils peuvent mettre en œuvre leurs optimisations et aboutir à des codes objets efficaces<sup class="need_ref_tag" style="padding-left:2px;"><a href="/wiki/Aide:R%C3%A9f%C3%A9rence_n%C3%A9cessaire" title="Aide:Référence nécessaire">[<abbr class="abbr" title="référence">réf.</abbr> souhaitée]</a></sup>.</li> <li>Des structures de données récursives, comme les <a href="/wiki/Quadtree" title="Quadtree">quadtrees</a>, ont été conçues pour leur efficacité. La manière la plus naturelle de les gérer est par des algorithmes récursifs.</li></ul> <div class="mw-heading mw-heading3"><h3 id="Contributions">Contributions</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=27" title="Modifier la section : Contributions" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=27" title="Modifier le code source de la section : Contributions"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li>La contribution la plus percutante dans ce débat a été celle de <a href="/wiki/John_Backus" title="John Backus">John Backus</a>, l'inventeur du <a href="/wiki/Fortran" title="Fortran">Fortran</a>, qui a pris clairement le parti de la programmation fonctionnelle, donc de la programmation récursive, lors de la remise de son <a href="/wiki/Prix_Turing" title="Prix Turing">prix Turing</a> en <a href="/wiki/1977" title="1977">1977</a>.</li> <li><a href="/wiki/Niklaus_Wirth" title="Niklaus Wirth">Niklaus Wirth</a>, l'inventeur du langage de programmation <a href="/wiki/Pascal_(langage)" title="Pascal (langage)">Pascal</a> écrit :</li></ul> <blockquote><p><span class="not_fr_quote" lang="en">« <span class="italique">The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.</span> »</span></p></blockquote><p style="margin:-0.7em 0 0.3em 6em">— Niklaus Wirth, <cite><i>Algorithms + Data Structures = Programs</i><sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite_crochet">[</span>4<span class="cite_crochet">]</span></a></sup>.</cite></p> <blockquote><div> <p>«  La puissance de la récursivité réside évidemment dans la possibilité de définir des ensembles infinis d'objets par une instruction finie. De façon similaire, un nombre infini d'étapes de calcul peut être décrit par un programme récursif fini, même si ce programme ne contient aucune répétition explicite. » </p> </div></blockquote> <ul><li><a href="/wiki/C._A._R._Hoare" class="mw-redirect" title="C. A. R. Hoare">C. A. R. Hoare</a> qui a écrit le premier compilateur (du langage <a href="/wiki/Algol_60" class="mw-redirect" title="Algol 60">Algol 60</a>) implémentant la récursivité, note dans son discours lors de la remise du <a href="/wiki/Prix_Turing" title="Prix Turing">prix Turing</a> en <a href="/wiki/1980" title="1980">1980</a><sup id="cite_ref-Hoare_8-0" class="reference"><a href="#cite_note-Hoare-8"><span class="cite_crochet">[</span>5<span class="cite_crochet">]</span></a></sup> que son algorithme de <a href="/wiki/Tri_rapide" title="Tri rapide">tri rapide</a> a été « très difficile à expliquer » tant qu'il ne connaissait pas l'existence des procédures récursives. Il poursuit en parlant de la récursion :</li></ul> <blockquote><p><span class="not_fr_quote" lang="en">« <span class="italique">I have regarded it as the highest goal of programming langage design to enable good ideas to be elegantly expressed.</span> »</span></p></blockquote><p style="margin:-0.7em 0 0.3em 6em">— C. A. R. Hoare, <cite><i>The Emperor's Old Clothes</i><sup id="cite_ref-Hoare_8-1" class="reference"><a href="#cite_note-Hoare-8"><span class="cite_crochet">[</span>5<span class="cite_crochet">]</span></a></sup>.</cite></p> <blockquote><div> <p>«  J'ai estimé que l'objectif le plus important de la conception d'un langage de programmation était de permettre aux meilleures idées d'être exprimées de manière élégante.  » </p> </div></blockquote> <div class="mw-heading mw-heading2"><h2 id="Récursion_terminale"><span id="R.C3.A9cursion_terminale"></span>Récursion terminale</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=28" title="Modifier la section : Récursion terminale" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=28" title="Modifier le code source de la section : Récursion terminale"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="bandeau-container bandeau-section metadata bandeau-niveau-information"><div class="bandeau-cell bandeau-icone-css loupe">Article détaillé : <a href="/wiki/R%C3%A9cursion_terminale" title="Récursion terminale">Récursion terminale</a>.</div></div> <p>Dans la définition d'une fonction récursive <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}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}"></span>, l'appel récursif est en <i>position terminale</i> si elle est de la forme </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(x)={\begin{cases}g(x)&{\text{si }}p(x){\text{,}}\\f(h(x))&{\text{sinon.}}\end{cases}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>{</mo> <mtable columnalign="left left" rowspacing=".2em" columnspacing="1em" displaystyle="false"> <mtr> <mtd> <mi>g</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mtd> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mtext>si </mtext> </mrow> <mi>p</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mtext>,</mtext> </mrow> </mtd> </mtr> <mtr> <mtd> <mi>f</mi> <mo stretchy="false">(</mo> <mi>h</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mtd> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mtext>sinon.</mtext> </mrow> </mtd> </mtr> </mtable> <mo fence="true" stretchy="true" symmetric="true"></mo> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f(x)={\begin{cases}g(x)&{\text{si }}p(x){\text{,}}\\f(h(x))&{\text{sinon.}}\end{cases}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4816603c9bc4233e60811a154df2813528da755c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:26.998ex; height:6.176ex;" alt="{\displaystyle f(x)={\begin{cases}g(x)&{\text{si }}p(x){\text{,}}\\f(h(x))&{\text{sinon.}}\end{cases}}}"></span></dd></dl> <p>Dans cette écriture, <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}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>g</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle g}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d3556280e66fe2c0d0140df20935a6f057381d77" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}"></span> et <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 h}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>h</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle h}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b26be3e694314bc90c3215047e4a2010c6ee184a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}"></span> sont des fonctions indépendantes de <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}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}"></span>. La fonction <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 p}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}"></span> est la condition d'arrêt. L'important, dans cette définition, est que l'appel de <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}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}"></span> ne soit pas englobé dans une autre expression. Une telle récursion est dite <a href="/wiki/R%C3%A9cursion_terminale" title="Récursion terminale">récursion terminale</a>. En pseudo-code, la définition récursive terminale peut s'écrire </p> <pre><b>fonction</b> f(x) <b>si</b> p(x) <b>retourner</b> g(x) <b>sinon</b> <b>retourner</b> f(h(x)) </pre> <p>où <i>x</i> peut être un <i>n</i>-uplet contenant plusieurs variables. </p><p>La définition récursive terminale se transcrit automatiquement en une définition itérative. En pseudo-code, la définition itérative peut s'écrire </p> <pre><b>fonction</b> f(x) <b>tant que</b> <b>vrai</b> <b>si</b> p(x) <b>retourner</b> g(x) <b>sinon</b> x ← h(x) </pre> <p>Par exemple, ce programme Python donne une définition récursive non terminale <code>fact</code> de la factorielle : </p> <div class="mw-highlight mw-highlight-lang-python mw-content-ltr" dir="ltr"><pre><span></span><span class="k">def</span> <span class="nf">fact</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="mi">1</span> <span class="k">else</span><span class="p">:</span> <span class="k">return</span> <span class="n">n</span> <span class="o">*</span> <span class="n">fact</span><span class="p">(</span><span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> </pre></div> <p>En effet, <code>n * fact(n - 1)</code> englobe l'appel à <code>fact</code>. Mais on peut la transformer en une définition récursive terminale par l'ajout d'un argument <code>a</code> appelé <i>accumulateur</i><sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite_crochet">[</span>6<span class="cite_crochet">]</span></a></sup>. </p><p>Ce programme Python donne une définition récursive terminale <code>fact_iter</code> de la factorielle : </p> <div class="mw-highlight mw-highlight-lang-python mw-content-ltr" dir="ltr"><pre><span></span><span class="k">def</span> <span class="nf">fact_iter</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">a</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">a</span> <span class="k">else</span><span class="p">:</span> <span class="k">return</span> <span class="n">fact_iter</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="n">n</span> <span class="o">*</span> <span class="n">a</span><span class="p">)</span> <span class="k">def</span> <span class="nf">fact</span><span class="p">(</span><span class="n">n</span><span class="p">):</span> <span class="k">return</span> <span class="n">fact_iter</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="mi">1</span><span class="p">)</span> </pre></div> <p>tandis que ce programme Python donne une définition itérative <code>fact_iter</code> de la factorielle : </p> <div class="mw-highlight mw-highlight-lang-python mw-content-ltr" dir="ltr"><pre><span></span><span class="k">def</span> <span class="nf">fact_iter</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">a</span><span class="p">):</span> <span class="k">while</span> <span class="kc">True</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">a</span> <span class="k">else</span><span class="p">:</span> <span class="n">n</span><span class="p">,</span> <span class="n">a</span> <span class="o">=</span> <span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">,</span> <span class="n">n</span> <span class="o">*</span> <span class="n">a</span> <span class="k">def</span> <span class="nf">fact</span><span class="p">(</span><span class="n">n</span><span class="p">):</span> <span class="k">return</span> <span class="n">fact_iter</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="mi">1</span><span class="p">)</span> </pre></div> <div class="mw-heading mw-heading2"><h2 id="Autres_situations_et_corécursivité"><span id="Autres_situations_et_cor.C3.A9cursivit.C3.A9"></span>Autres situations et corécursivité</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=29" title="Modifier la section : Autres situations et corécursivité" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=29" title="Modifier le code source de la section : Autres situations et corécursivité"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>La <a href="/wiki/R%C3%A9cursivit%C3%A9" title="Récursivité">récursivité</a> (et sa duale la <a href="/w/index.php?title=Cor%C3%A9cursivit%C3%A9&action=edit&redlink=1" class="new" title="Corécursivité (page inexistante)">corécursivité</a> <a href="https://en.wikipedia.org/wiki/corecursion" class="extiw" title="en:corecursion"><span class="indicateur-langue" title="Article en anglais : « corecursion »">(en)</span></a>) se retrouvent dans d'autres situations, où elle prend parfois d'autres noms. </p> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/Fichier:Sierpinski_carpet_6,_white_on_black.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/6/67/Sierpinski_carpet_6%2C_white_on_black.svg/220px-Sierpinski_carpet_6%2C_white_on_black.svg.png" decoding="async" width="220" height="220" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/6/67/Sierpinski_carpet_6%2C_white_on_black.svg/330px-Sierpinski_carpet_6%2C_white_on_black.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/6/67/Sierpinski_carpet_6%2C_white_on_black.svg/440px-Sierpinski_carpet_6%2C_white_on_black.svg.png 2x" data-file-width="729" data-file-height="729" /></a><figcaption>Tapis de Sierpiński.</figcaption></figure> <ul><li>L'<a href="/wiki/Autosimilarit%C3%A9" title="Autosimilarité">autosimilarité</a> est le caractère d'un objet dans laquelle on peut trouver des similarités en l'observant à différentes échelles. C'est de la corécursivité.</li> <li>Les <a href="/wiki/Fractale" title="Fractale">fractales</a> ont cette propriété d'autosimilarité, mais elles ont plutôt à voir avec le concept un peu différent qui s'appelle la <a href="/w/index.php?title=Cor%C3%A9cursivit%C3%A9&action=edit&redlink=1" class="new" title="Corécursivité (page inexistante)">corécursivité</a> <a href="https://en.wikipedia.org/wiki/corecursion" class="extiw" title="en:corecursion"><span class="indicateur-langue" title="Article en anglais : « corecursion »">(en)</span></a> (ou corécursion). Le <a href="/wiki/Tapis_de_Sierpi%C5%84ski" title="Tapis de Sierpiński">tapis de Sierpiński</a>, du nom de <a href="/wiki/Wac%C5%82aw_Sierpi%C5%84ski" title="Wacław Sierpiński">Wacław Sierpiński</a>, est une fractale obtenue à partir d'un carré. Le tapis se fabrique en découpant le carré en neuf carrés égaux avec une grille de trois par trois, et en supprimant la pièce centrale, et en appliquant cette procédure récursivement aux huit carrés restants.</li></ul> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/Fichier:Van_Eyck_-_Arnolfini_Portrait.jpg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/3/33/Van_Eyck_-_Arnolfini_Portrait.jpg/220px-Van_Eyck_-_Arnolfini_Portrait.jpg" decoding="async" width="220" height="301" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/3/33/Van_Eyck_-_Arnolfini_Portrait.jpg/330px-Van_Eyck_-_Arnolfini_Portrait.jpg 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/3/33/Van_Eyck_-_Arnolfini_Portrait.jpg/440px-Van_Eyck_-_Arnolfini_Portrait.jpg 2x" data-file-width="4386" data-file-height="6000" /></a><figcaption><i><a href="/wiki/Les_%C3%89poux_Arnolfini" title="Les Époux Arnolfini">Les Époux Arnolfini</a></i> par <a href="/wiki/Jan_van_Eyck" title="Jan van Eyck">Jan van Eyck</a>, <a href="/wiki/National_Gallery" title="National Gallery">National Gallery</a>, Londres.<br />Dans le miroir suspendu sur le mur, on voit le couple de dos et le peintre lui-même qui se reflètent à l’envers.</figcaption></figure> <ul><li>La <a href="/wiki/Mise_en_abyme" title="Mise en abyme">mise en abyme</a> est un procédé consistant à représenter une œuvre dans une œuvre similaire, par exemple en incrustant dans une image cette image elle-même. On retrouve dans ce principe l'« autosimilarité » et le principe des fractales ou de la corécursivité en mathématiques. Des publicités emploient ce procédé, dont la fameuse <i><a href="/wiki/La_vache_qui_rit" title="La vache qui rit">Vache qui rit</a></i> de <a href="/wiki/Benjamin_Rabier" title="Benjamin Rabier">Benjamin Rabier</a>.</li> <li>Quand on écrit</li></ul> <pre>fibs :: [Integer] fibs = 0:1:zipWith (+) (fibs) (tail fibs) </pre> <dl><dd>en <a href="/wiki/Haskell" title="Haskell">Haskell</a>, il s'agit de corécursivité. On définit ainsi une suite infinie (un stream) de toutes les valeurs de la <a href="/wiki/Suite_de_Fibonacci" title="Suite de Fibonacci">suite de Fibonacci</a>. On pourra récupérer la <i>n</i>-ième valeur de <b>fibs</b>, que l'on ne calcule qu'une fois, et obtenir ainsi le <i>n</i>-ième nombre de Fibonacci. Cette suite infinie est décrite en langue naturelle ainsi, c'est la suite <i>fibs</i> qui commence par 0, suivi de 1, puis des éléments obtenus en ajoutant le premier élément de la suite <i>fibs</i> au deuxième de la suite <i>fibs</i> pour former le troisième élément de la suite <i>fibs</i>, puis le deuxième de la suite <i>fibs</i> au troisième de la suite <i>fibs</i> pour former le quatrième élément de la suite <i>fibs</i>, puis ainsi de suite, le i-ème élément de la suite <i>fibs</i> au i+1-ème de la suite <i>fibs</i> pour former le i+2-ème élément de la suite <i>fibs</i>, etc.</dd></dl> <div class="mw-heading mw-heading2"><h2 id="Notes_et_références"><span id="Notes_et_r.C3.A9f.C3.A9rences"></span>Notes et références</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=30" title="Modifier la section : Notes et références" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=30" title="Modifier le code source de la section : Notes et références"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Références"><span id="R.C3.A9f.C3.A9rences"></span>Références</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=31" title="Modifier la section : Références" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=31" title="Modifier le code source de la section : Références"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="references-small decimal" style=""><div class="mw-references-wrap"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink noprint"><a href="#cite_ref-1">↑</a> </span><span class="reference-text"><span class="ouvrage" id="GrahamKnuthPatashnik2003"><span class="ouvrage" id="Ronald_L._GrahamDonald_E._KnuthOren_Patashnik2003">Ronald L. <span class="nom_auteur">Graham</span>, Donald E. <span class="nom_auteur">Knuth</span> et Oren <span class="nom_auteur">Patashnik</span> (<abbr class="abbr" title="traduction">trad.</abbr> Alain Denise), <cite class="italique">Mathématiques concrètes : fondations pour l'informatique</cite>, Vuibert, <abbr class="abbr" title="collection">coll.</abbr> « Vuibert informatique », <time>2003</time>, <abbr class="abbr" title="deuxième">2<sup>e</sup></abbr> <abbr class="abbr" title="édition">éd.</abbr>, 687 <abbr class="abbr" title="pages">p.</abbr> <small style="line-height:1em;">(<a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Sp%C3%A9cial:Ouvrages_de_r%C3%A9f%C3%A9rence/978-2-7117-4824-2" title="Spécial:Ouvrages de référence/978-2-7117-4824-2"><span class="nowrap">978-2-7117-4824-2</span></a>)</small>, <abbr class="abbr" title="page">p.</abbr> 1<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Math%C3%A9matiques+concr%C3%A8tes&rft.pub=Vuibert&rft.edition=2&rft.stitle=fondations+pour+l%27informatique&rft.aulast=Graham&rft.aufirst=Ronald+L.&rft.au=Knuth%2C+Donald+E.&rft.au=Patashnik%2C+Oren&rft.date=2003&rft.pages=1&rft.tpages=687&rft.isbn=978-2-7117-4824-2&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AAlgorithme+r%C3%A9cursif"></span></span></span>.</span> </li> <li id="cite_note-2"><span class="mw-cite-backlink noprint"><a href="#cite_ref-2">↑</a> </span><span class="reference-text"><span class="ouvrage" id="Knuth"><span class="ouvrage" id="Donald_E._Knuth">Donald E. Knuth, <cite class="italique">The Art of Computer Programming (Generating All Tuples and Permutations)</cite>, <abbr class="abbr" title="volume">vol.</abbr> 4.2, Addison Wesley, <abbr class="abbr" title="page">p.</abbr> 41<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=The+Art+of+Computer+Programming+%28Generating+All+Tuples+and+Permutations%29&rft.pub=Addison+Wesley&rft.aulast=Knuth&rft.aufirst=Donald+E.&rft.volume=4.2&rft.pages=41&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AAlgorithme+r%C3%A9cursif"></span></span></span></span> </li> <li id="cite_note-3"><span class="mw-cite-backlink noprint"><a href="#cite_ref-3">↑</a> </span><span class="reference-text"><span class="ouvrage" id="ChristiansenDanilenkoDylus2016"><span class="ouvrage" id="Jan_ChristiansenNikita_DanilenkoSandra_Dylus2016">Jan Christiansen, Nikita Danilenko et Sandra Dylus, « <cite style="font-style:normal">All sorts of permutations (functional pearl)</cite> », <i>Proceedings of the 21st ACM-SIGPLAN International Conference on Functional Programming, (ICFP)</i>,‎ <time class="nowrap" datetime="2016-09" data-sort-value="2016-09">septembre 2016</time>, <abbr class="abbr" title="page(s)">p.</abbr> 168--179 <small style="line-height:1em;">(<a rel="nofollow" class="external text" href="http://doi.acm.org/10.1145/2951913.2951949">lire en ligne</a>)</small><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=All+sorts+of+permutations+%28functional+pearl%29&rft.jtitle=Proceedings+of+the+21st+ACM-SIGPLAN+International+Conference+on+Functional+Programming%2C+%28ICFP%29&rft.aulast=Christiansen&rft.aufirst=Jan&rft.au=Nikita+Danilenko&rft.au=Sandra+Dylus&rft.date=2016-09&rft.pages=168--179&rft_id=http%3A%2F%2Fdoi.acm.org%2F10.1145%2F2951913.2951949&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AAlgorithme+r%C3%A9cursif"></span></span></span></span> </li> <li id="cite_note-7"><span class="mw-cite-backlink noprint"><a href="#cite_ref-7">↑</a> </span><span class="reference-text"><span class="ouvrage" id="Wirth1976"><span class="ouvrage" id="Niklaus_Wirth1976"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> Niklaus Wirth, <cite class="italique" lang="en">Algorithms + Data Structures = Programs</cite>, Englewood Cliffs, New Jersey, Prentice-Hall, Inc., <time>1976</time>, 366 <abbr class="abbr" title="pages">p.</abbr> <small style="line-height:1em;">(<a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Sp%C3%A9cial:Ouvrages_de_r%C3%A9f%C3%A9rence/978-0-13-022418-7" title="Spécial:Ouvrages de référence/978-0-13-022418-7"><span class="nowrap">978-0-13-022418-7</span></a>)</small>, <abbr class="abbr" title="page">p.</abbr> 129<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Algorithms+%2B+Data+Structures+%3D+Programs&rft.place=Englewood+Cliffs%2C+New+Jersey&rft.pub=Prentice-Hall%2C+Inc.&rft.aulast=Wirth&rft.aufirst=Niklaus&rft.date=1976&rft.pages=129&rft.tpages=366&rft.isbn=978-0-13-022418-7&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AAlgorithme+r%C3%A9cursif"></span></span></span>.</span> </li> <li id="cite_note-Hoare-8"><span class="mw-cite-backlink noprint">↑ <sup><a href="#cite_ref-Hoare_8-0">a</a> et <a href="#cite_ref-Hoare_8-1">b</a></sup> </span><span class="reference-text"><span class="ouvrage" id="Hoare1981"><span class="ouvrage" id="Charles_Antony_Richard_Hoare1981"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> <a href="/wiki/Charles_Antony_Richard_Hoare" title="Charles Antony Richard Hoare">Charles Antony Richard <span class="nom_auteur">Hoare</span></a>, « <cite style="font-style:normal" lang="en">The Emperor's Old Clothes</cite> », <i><a href="/wiki/Communications_of_the_ACM" title="Communications of the ACM"><span class="lang-en" lang="en">Communications of the ACM</span></a></i>, <abbr class="abbr" title="volume">vol.</abbr> 24, <abbr class="abbr" title="numéro">n<sup>o</sup></abbr> 2,‎ <time class="nowrap" datetime="1981-02" data-sort-value="1981-02">février 1981</time>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">75-83</span> <small style="line-height:1em;">(<a rel="nofollow" class="external text" href="https://www.cs.fsu.edu/~engelen/courses/COP4610/hoare.pdf">lire en ligne</a>)</small><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=The+Emperor%27s+Old+Clothes&rft.jtitle=Communications+of+the+ACM&rft.issue=2&rft.aulast=Hoare&rft.aufirst=Charles+Antony+Richard&rft.date=1981-02&rft.volume=24&rft.pages=75-83&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AAlgorithme+r%C3%A9cursif"></span></span></span>.</span> </li> <li id="cite_note-9"><span class="mw-cite-backlink noprint"><a href="#cite_ref-9">↑</a> </span><span class="reference-text"><span class="ouvrage" id="Abel">Harold <span class="nom_auteur">Abelson</span>, Gerald Jay <span class="nom_auteur">Sussman</span> (auteurs) et Julie <span class="nom_auteur">Sussman</span> (collaboratrice), <cite class="italique"><a href="/wiki/Structure_and_interpretation_of_computer_programs" class="mw-redirect" title="Structure and interpretation of computer programs">Structure and interpretation of computer programs</a></cite>, <a href="/wiki/MIT_Press" title="MIT Press">MIT Press</a> et <a href="/wiki/McGraw-Hill_Education" title="McGraw-Hill Education">McGraw-Hill</a>, <time>1996</time>, <abbr class="abbr" title="deuxième">2<sup>e</sup></abbr> <abbr class="abbr" title="édition">éd.</abbr>, XXIII+657 <small style="line-height:1em;">(<a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Sp%C3%A9cial:Ouvrages_de_r%C3%A9f%C3%A9rence/978-0-07-000484-9" title="Spécial:Ouvrages de référence/978-0-07-000484-9"><span class="nowrap">978-0-07-000484-9</span></a>, <a rel="nofollow" class="external text" href="http://mitpress.mit.edu/sicp/full-text/book/book.html">lire en ligne</a>)</small>, <abbr class="abbr" title="chapitre(s)">chap.</abbr> 1.2.1 (« <a rel="nofollow" class="external text" href="https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1">Linear Recursion and Iteration</a> »)<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Structure+and+interpretation+of+computer+programs&rft.pub=MIT+Press&rft.edition=2&rft.aulast=Abelson&rft.aufirst=Harold&rft.au=Sussman%2C+Gerald+Jay&rft.au=Sussman%2C+Julie&rft.date=1996&rft.tpages=XXIII%2B657&rft.isbn=978-0-07-000484-9&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AAlgorithme+r%C3%A9cursif"></span></span>.</span> </li> </ol></div> </div> <div class="mw-heading mw-heading3"><h3 id="Notes">Notes</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=32" title="Modifier la section : Notes" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=32" title="Modifier le code source de la section : Notes"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="references-small decimal" style=""><div class="mw-references-wrap"><ol class="references"> <li id="cite_note-4"><span class="mw-cite-backlink noprint"><a href="#cite_ref-4">↑</a> </span><span class="reference-text">L'algorithme s'invoque lui-même de façon répétitive </span> </li> <li id="cite_note-5"><span class="mw-cite-backlink noprint"><a href="#cite_ref-5">↑</a> </span><span class="reference-text">On remarquera que l'on note l'application d'une fonction <i>f x</i> ce qui est traditionnel dans les langages de programmation fondés sur la récursivité.</span> </li> <li id="cite_note-6"><span class="mw-cite-backlink noprint"><a href="#cite_ref-6">↑</a> </span><span class="reference-text">Les fonctions <a href="/wiki/R%C3%A9cursion_terminale" title="Récursion terminale">récursives terminales</a> par exemple ne requièrent pas de pile.</span> </li> </ol></div> </div> <div class="mw-heading mw-heading2"><h2 id="Voir_aussi">Voir aussi</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=33" title="Modifier la section : Voir aussi" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=33" title="Modifier le code source de la section : Voir aussi"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Articles_connexes">Articles connexes</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=34" title="Modifier la section : Articles connexes" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=34" title="Modifier le code source de la section : Articles connexes"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r194021218">.mw-parser-output .autres-projets>.titre{text-align:center;margin:0.2em 0}.mw-parser-output .autres-projets>ul{margin:0;padding:0}.mw-parser-output .autres-projets>ul>li{list-style:none;margin:0.2em 0;text-indent:0;padding-left:24px;min-height:20px;text-align:left;display:block}.mw-parser-output .autres-projets>ul>li>a{font-style:italic}@media(max-width:720px){.mw-parser-output .autres-projets{float:none}}</style><div class="autres-projets boite-grise boite-a-droite noprint js-interprojets"> <p class="titre">Sur les autres projets Wikimedia :</p> <ul class="noarchive plainlinks"> <li class="wikiversity"><a href="https://fr.wikiversity.org/wiki/R%C3%A9cursivit%C3%A9_dans_l%27algorithmique_et_la_programmation" class="extiw" title="v:Récursivité dans l'algorithmique et la programmation">Récursivité dans l'algorithmique et la programmation</a>, <span class="nowrap">sur <span class="project">Wikiversity</span></span></li> </ul> </div> <div style="column-count:3;column-gap:1em;" class="colonnes"> <ul><li><a href="/wiki/Fonction_r%C3%A9cursive" title="Fonction récursive">Fonction récursive</a></li> <li><a href="/wiki/Fonction_r%C3%A9cursive_primitive" title="Fonction récursive primitive">Fonction récursive primitive</a></li> <li><a href="/wiki/R%C3%A9cursion_mutuelle" title="Récursion mutuelle">Récursion mutuelle</a></li> <li><a href="/wiki/Type_r%C3%A9cursif" title="Type récursif">Type récursif</a></li> <li><a href="/wiki/Pile_(informatique)" title="Pile (informatique)">Pile (informatique)</a></li> <li><a href="/wiki/Impr%C3%A9dicativit%C3%A9" title="Imprédicativité">Imprédicativité</a></li> <li><a href="/wiki/%C3%89valuation_paresseuse" title="Évaluation paresseuse">Évaluation paresseuse</a></li> <li><a href="/wiki/Diviser_pour_r%C3%A9gner_(informatique)" title="Diviser pour régner (informatique)">Diviser pour régner (informatique)</a></li> <li><a href="/wiki/Paradigme_(programmation)" title="Paradigme (programmation)">Paradigme de programmation</a></li> <li><a href="/wiki/Programmation_fonctionnelle" title="Programmation fonctionnelle">Programmation fonctionnelle</a></li> <li><a href="/wiki/Fonction_de_Sudan" title="Fonction de Sudan">Fonction de Sudan</a></li> <li><a href="/wiki/Fonction_91_de_McCarthy" title="Fonction 91 de McCarthy">Fonction 91 de McCarthy</a></li> <li><a href="/wiki/Fonction_de_Takeuchi" title="Fonction de Takeuchi">Fonction de Takeuchi</a></li> <li><a href="/wiki/M%C3%A9mo%C3%AFsation" title="Mémoïsation">Mémoïsation</a></li> <li><a href="/wiki/Tri_fusion" title="Tri fusion">Tri fusion</a></li> <li><a href="/wiki/Algorithme_de_Casteljau" title="Algorithme de Casteljau">Algorithme de Casteljau</a></li> <li><a href="/wiki/Th%C3%A9or%C3%A8me_de_Masreliez" title="Théorème de Masreliez">Théorème de Masreliez</a></li> <li><a href="/wiki/Algorithme_X_de_Knuth" title="Algorithme X de Knuth">Algorithme X de Knuth</a></li> <li><a href="/wiki/Probl%C3%A8me_des_huit_dames" title="Problème des huit dames">Problème des huit dames</a></li> <li><a href="/wiki/Exponentiation_rapide" title="Exponentiation rapide">Exponentiation rapide</a></li> <li><a href="/wiki/Algorithme_de_Karatsuba" title="Algorithme de Karatsuba">Algorithme de Karatsuba</a></li> <li><a href="/wiki/Algorithme_des_moindres_carr%C3%A9s_r%C3%A9cursifs" title="Algorithme des moindres carrés récursifs">Algorithme des moindres carrés récursifs</a></li> <li><a href="/wiki/Algorithme_de_Douglas-Peucker" title="Algorithme de Douglas-Peucker">Algorithme de Douglas-Peucker</a></li> <li><a href="/wiki/Algorithme_de_Cooley-Tukey" class="mw-redirect" title="Algorithme de Cooley-Tukey">Algorithme de Cooley-Tukey</a></li> <li><a href="/wiki/Algorithme_de_Lehmer-Schur" title="Algorithme de Lehmer-Schur">Algorithme de Lehmer-Schur</a></li> <li><a href="/wiki/Algorithme_de_Clenshaw" title="Algorithme de Clenshaw">Algorithme de Clenshaw</a></li> <li><a href="/wiki/Acronymie_r%C3%A9cursive" class="mw-redirect" title="Acronymie récursive">Acronymie récursive</a></li> <li><a href="/wiki/Algorithme_de_Havel-Lakimi" class="mw-redirect" title="Algorithme de Havel-Lakimi">Algorithme de Havel-Lakimi</a></li></ul> </div> <div class="mw-heading mw-heading3"><h3 id="Bibliographie">Bibliographie</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=35" title="Modifier la section : Bibliographie" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=35" title="Modifier le code source de la section : Bibliographie"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>De très nombreux livres et articles traitant des algorithmes récursifs ont été publiés. Nous n'en donnons ici qu'une liste non exhaustive. </p> <div class="mw-heading mw-heading4"><h4 id="En_français"><span id="En_fran.C3.A7ais"></span>En français</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=36" title="Modifier la section : En français" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=36" title="Modifier le code source de la section : En français"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li>Anne Brygoo, Titou Durand, Maryse Pelletier, Christian Queinnec <i><abbr class="abbr" title="et alii (« et d’autres »)" lang="la">et al.</abbr></i> <i>Programmation récursive (en Scheme)</i> Cours et exercices corrigés Collection: Sciences Sup, Dunod, 2004</li> <li>Emmanuel Chailloux, Pascal Manoury et Bruno Pagano, <i>Développement d'applications avec Objective Caml</i>, Éditions O'Reilly, Paris, 2000</li> <li>Sylvain Conchon et Jean-Christophe Filliâtre, <i>Apprendre à programmer avec OCaml</i>. Algorithmes et structures de données. Éditions Eyrolles, 2014</li> <li>C. Livercy, <a rel="nofollow" class="external text" href="http://denif.ens-lyon.fr/data/programmation_enslyon/2007_sem2/biblio/Livercy.pdf"><i>Theorie des programmes / schemas, preuves, sémantique</i></a>, Dunod, 1978</li> <li>Niklaus Wirth, <i>Algorithmes et structures de données</i>, 1987, trad. par J.A. Hernandez et P. Kruchten / <abbr class="abbr" title="Deuxième">2<sup>e</sup></abbr> édition / Paris : Eyrolles , rééd. 1989</li> <li>Laurent Arditi et Stéphane Ducasse, <a rel="nofollow" class="external text" href="http://sdmeta.gforge.inria.fr/Books/Scheme/book.html"><i>La programmation : une approche fonctionnelle et récursive avec Scheme</i></a></li></ul> <div class="mw-heading mw-heading4"><h4 id="En_anglais">En anglais</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&veaction=edit&section=37" title="Modifier la section : En anglais" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Algorithme_r%C3%A9cursif&action=edit&section=37" title="Modifier le code source de la section : En anglais"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a rel="nofollow" class="external text" href="http://mitpress.mit.edu/sicp/full-text/book/book.html">Harold Abelson and Gerald Sussman: "Structure and Interpretation Of Computer Programs"</a></li> <li><a rel="nofollow" class="external text" href="http://www.ibm.com/developerworks/linux/library/l-recurs/index.html">Jonathan Bartlett: "Mastering Recursive Programming"</a></li> <li><a rel="nofollow" class="external text" href="http://www.cs.cmu.edu/~dst/LispBook/">David S. Touretzky: "Common Lisp: A Gentle Introduction to Symbolic Computation"</a></li> <li><a rel="nofollow" class="external text" href="http://www.htdp.org/2003-09-26/Book/">Matthias Felleisen: "How To Design Programs: An Introduction to Computing and Programming"</a></li> <li><a rel="nofollow" class="external text" href="http://www.cs.duke.edu/~ola/ap/recurrence.html">Owen L. Astrachan: "Big-Oh for Recursive Functions: Recurrence Relations" </a></li> <li>Richard Bird et Philip Wadler, <i>Introduction to Functional Programming</i>, Prentice Hall International Series in Computing Science, 1988</li> <li>Richard Bird, <i>Introduction to Functional Programming using Haskell</i>, <abbr class="abbr" title="Deuxième">2<sup>e</sup></abbr> éd., Prentice Hall International Series in Computing Science, 1998</li> <li>Guy Cousineau et Michel Mauny, <i>The Functional Approach to Programming</i>, <a href="/wiki/Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>, Cambridge, 1998</li> <li>Edsger Dijkstra, <i>A Discipline of Programming</i>, 1976</li> <li><a href="/wiki/Anatoli_Maltsev" title="Anatoli Maltsev">Anatoli Maltsev</a>, <i>Algorithms and Recursive Functions</i> , Wolters-Noordhof Publishing Co. "Groningen", 1970</li> <li>John McCarthy, « Recursive Functions of Symbolic Expressions », <i>Comm. of the ACM</i>, 1960, 3 (4), <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">184–195</span></li> <li>John C. Mitchell, <i>Concepts in Programming Languages</i>, Cambridge University Press, 2002</li> <li>Graham Hutton, <i>Programming in Haskell,</i> Cambridge University Press, 2007</li> <li>Chris Okasaki, <i>Purely functional data structures</i>, Cambridge University Press, 1998</li> <li>Rózsa Péter, <i>Recursive Functions</i>, traduit par István Földes, New York, Academic Press, 1967</li> <li>Benjamin C. Pierce, <i>Types and Programming Languages</i>, The MIT Press 2002</li> <li>Jeffrey Soden Rohl, <i>Recursion Via Pascal</i>, Cambridge University Press, 1984</li></ul> <ul id="bandeau-portail" class="bandeau-portail"><li><span class="bandeau-portail-element"><span class="bandeau-portail-icone"><span class="noviewer skin-invert-image" typeof="mw:File"><a href="/wiki/Portail:Informatique_th%C3%A9orique" title="Portail de l'informatique théorique"><img alt="icône décorative" src="//upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Max-cut.svg/30px-Max-cut.svg.png" decoding="async" width="30" height="24" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Max-cut.svg/45px-Max-cut.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Max-cut.svg/60px-Max-cut.svg.png 2x" data-file-width="200" data-file-height="160" /></a></span></span> <span class="bandeau-portail-texte"><a href="/wiki/Portail:Informatique_th%C3%A9orique" title="Portail:Informatique théorique">Portail de l'informatique théorique</a></span> </span></li> <li><span class="bandeau-portail-element"><span class="bandeau-portail-icone"><span class="noviewer skin-invert-image" typeof="mw:File"><a href="/wiki/Portail:Logique" title="Portail de la logique"><img alt="icône décorative" src="//upload.wikimedia.org/wikipedia/commons/thumb/e/e7/Logic.svg/48px-Logic.svg.png" decoding="async" width="48" height="16" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/e/e7/Logic.svg/72px-Logic.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/e/e7/Logic.svg/96px-Logic.svg.png 2x" data-file-width="85" data-file-height="28" /></a></span></span> <span class="bandeau-portail-texte"><a href="/wiki/Portail:Logique" title="Portail:Logique">Portail de la logique</a></span> </span></li> </ul>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Ce document provient de « <a dir="ltr" href="https://fr.wikipedia.org/w/index.php?title=Algorithme_récursif&oldid=220490945">https://fr.wikipedia.org/w/index.php?title=Algorithme_récursif&oldid=220490945</a> ».</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Cat%C3%A9gorie:Accueil" title="Catégorie:Accueil">Catégories</a> : <ul><li><a href="/wiki/Cat%C3%A9gorie:M%C3%A9thode_algorithmique" title="Catégorie:Méthode algorithmique">Méthode algorithmique</a></li><li><a href="/wiki/Cat%C3%A9gorie:Langage_fonctionnel" title="Catégorie:Langage fonctionnel">Langage fonctionnel</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Catégories cachées : <ul><li><a href="/wiki/Cat%C3%A9gorie:Article_%C3%A0_r%C3%A9f%C3%A9rence_souhait%C3%A9e" title="Catégorie:Article à référence souhaitée">Article à référence souhaitée</a></li><li><a href="/wiki/Cat%C3%A9gorie:Article_contenant_un_appel_%C3%A0_traduction_en_anglais" title="Catégorie:Article contenant un appel à traduction en anglais">Article contenant un appel à traduction en anglais</a></li><li><a href="/wiki/Cat%C3%A9gorie:Portail:Informatique_th%C3%A9orique/Articles_li%C3%A9s" title="Catégorie:Portail:Informatique théorique/Articles liés">Portail:Informatique théorique/Articles liés</a></li><li><a href="/wiki/Cat%C3%A9gorie:Portail:Informatique/Articles_li%C3%A9s" title="Catégorie:Portail:Informatique/Articles liés">Portail:Informatique/Articles liés</a></li><li><a href="/wiki/Cat%C3%A9gorie:Projet:Math%C3%A9matiques/Articles" title="Catégorie:Projet:Mathématiques/Articles">Projet:Mathématiques/Articles</a></li><li><a href="/wiki/Cat%C3%A9gorie:Portail:Logique/Articles_li%C3%A9s" title="Catégorie:Portail:Logique/Articles liés">Portail:Logique/Articles liés</a></li><li><a href="/wiki/Cat%C3%A9gorie:Portail:Sciences/Articles_li%C3%A9s" title="Catégorie:Portail:Sciences/Articles liés">Portail:Sciences/Articles liés</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"> La dernière modification de cette page a été faite le 21 novembre 2024 à 17:23.</li> <li id="footer-info-copyright"><span style="white-space: normal"><a href="/wiki/Wikip%C3%A9dia:Citation_et_r%C3%A9utilisation_du_contenu_de_Wikip%C3%A9dia" title="Wikipédia:Citation et réutilisation du contenu de Wikipédia">Droit d'auteur</a> : les textes sont disponibles sous <a rel="nofollow" class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.fr">licence Creative Commons attribution, partage dans les mêmes conditions</a> ; d’autres conditions peuvent s’appliquer. Voyez les <a class="external text" href="https://foundation.wikimedia.org/wiki/Policy:Terms_of_Use/fr">conditions d’utilisation</a> pour plus de détails, ainsi que les <a href="/wiki/Wikip%C3%A9dia:Cr%C3%A9dits_graphiques" title="Wikipédia:Crédits graphiques">crédits graphiques</a>. En cas de réutilisation des textes de cette page, voyez <a href="/wiki/Sp%C3%A9cial:Citer/Algorithme_r%C3%A9cursif" title="Spécial:Citer/Algorithme récursif">comment citer les auteurs et mentionner la licence</a>.<br /> Wikipedia® est une marque déposée de la <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, organisation de bienfaisance régie par le paragraphe <a href="/wiki/501c" title="501c">501(c)(3)</a> du code fiscal des États-Unis.</span><br /></li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy/fr">Politique de confidentialité</a></li> <li id="footer-places-about"><a href="/wiki/Wikip%C3%A9dia:%C3%80_propos_de_Wikip%C3%A9dia">À propos de Wikipédia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikip%C3%A9dia:Avertissements_g%C3%A9n%C3%A9raux">Avertissements</a></li> <li id="footer-places-contact"><a href="//fr.wikipedia.org/wiki/Wikipédia:Contact">Contact</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code de conduite</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Développeurs</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/fr.wikipedia.org">Statistiques</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Déclaration sur les témoins (cookies)</a></li> <li id="footer-places-mobileview"><a href="//fr.m.wikipedia.org/w/index.php?title=Algorithme_r%C3%A9cursif&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Version mobile</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></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"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-74cc59cb9d-mr97z","wgBackendResponseTime":687,"wgPageParseReport":{"limitreport":{"cputime":"0.319","walltime":"0.518","ppvisitednodes":{"value":2018,"limit":1000000},"postexpandincludesize":{"value":28683,"limit":2097152},"templateargumentsize":{"value":3281,"limit":2097152},"expansiondepth":{"value":12,"limit":100},"expensivefunctioncount":{"value":4,"limit":500},"unstrip-depth":{"value":0,"limit":20},"unstrip-size":{"value":18082,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 260.817 1 -total"," 35.39% 92.310 2 Modèle:Références"," 24.85% 64.806 4 Modèle:Ouvrage"," 16.17% 42.183 1 Modèle:Portail"," 12.14% 31.652 2 Modèle:Méta_bandeau_de_section"," 11.13% 29.018 1 Modèle:Source_de_la_section"," 9.57% 24.948 1 Modèle:Autres_projets"," 8.60% 22.437 1 Modèle:Suivi_des_biographies"," 4.16% 10.860 2 Modèle:Citation_étrangère_bloc"," 4.03% 10.498 1 Modèle:Refsou"]},"scribunto":{"limitreport-timeusage":{"value":"0.083","limit":"10.000"},"limitreport-memusage":{"value":4252736,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-74cc59cb9d-mr97z","timestamp":"20241128113511","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Algorithme r\u00e9cursif","url":"https:\/\/fr.wikipedia.org\/wiki\/Algorithme_r%C3%A9cursif","sameAs":"http:\/\/www.wikidata.org\/entity\/Q264164","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q264164","author":{"@type":"Organization","name":"Contributeurs aux projets Wikimedia"},"publisher":{"@type":"Organization","name":"Fondation Wikimedia, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2003-09-18T08:52:40Z","dateModified":"2024-11-21T16:23:29Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/f\/f7\/RecursiveTree.JPG","headline":"m\u00e9thode de programmation informatique"}</script> </body> </html>