Voir la source de Algorithme récursif

[[File:recursiveTree.JPG|thumb|Arbre dessiné par un algorithme récursif. On remarque que chaque branche est elle-même une version plus petite d'un arbre.|396x396px]]Un '''algorithme récursif''' est un [[algorithme]] qui résout un problème en calculant des solutions d'[[Instance (programmation)|instances]] plus petites du même problème<ref>{{Ouvrage|langue=fr|prénom1=Ronald L.|nom1=Graham|prénom2=Donald E.|nom2=Knuth|prénom3=Oren|nom3=Patashnik|traducteur=Alain Denise|titre=Mathématiques concrètes|sous-titre=fondations pour l'informatique|éditeur=Vuibert|collection=Vuibert informatique|année=2003|numéro d'édition=2|pages totales=687|isbn=978-2-7117-4824-2|passage=1}}.</ref>. L'approche [[récursivité|récursive]] est un des concepts de base en [[informatique]].

Les premiers [[langage de programmation|langages de programmation]] qui ont autorisé l'emploi de la récursivité sont [[Lisp (langage)|LISP]] et [[algol (langage)|Algol 60]]. Depuis, tous les langages de programmation généraux réalisent une [[Mise en œuvre|implémentation]] 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 ''pour'' et des boucles ''tant que'', pour répéter des opérations.

== Un exemple préliminaire : les permutations ==
{{Source de la section|de la source suivante : Haskell basic library [https://hackage.haskell.org/package/base-4.12.0.0/docs/Data-List.html Data.List]}}
[[File:Permutations de Belle Marquise.png|thumb|upright=1.5|Permutations de la phrase « Belle Marquise vos beaux yeux me font mourir d'amour »]]
Commençons par un exemple tiré du ''[[le Bourgeois gentilhomme|Bourgeois gentilhomme]]'' [[s:Le Bourgeois gentilhomme (Imprimerie nationale)#Scène IV|(Acte II Scène IV)]] de [[Molière]]. Le héros, Monsieur Jourdain, veut connaître toutes les manières « galantes » d'écrire un billet. De la phrase ''Belle Marquise, vos beaux yeux, me font mourir d'amour'', il pourrait tirer ''Vos beaux yeux, belle Marquise, d'amour me font mourir'', puis ''Vos beaux yeux, me font mourir, belle Marquise, d'amour'', puis ''Vos beaux yeux, me font mourir d'amour, belle Marquise'' et ainsi de suite.

Comment Monsieur Jourdain devrait-il procéder pour engendrer toutes ces [[permutation]]s ? 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<ref>{{Ouvrage|auteur=Donald E. Knuth|titre=The Art of Computer Programming (Generating All Tuples and Permutations)|volume=4.2|page=41<!--|section=7.2.1.2-->|éditeur=Addison Wesley}}</ref>{{,}}<ref>{{Article|url=http://doi.acm.org/10.1145/2951913.2951949|auteur1=Jan Christiansen |auteur2=Nikita Danilenko |auteur3 =Sandra Dylus | titre     = All sorts of permutations (functional pearl)|périodique= Proceedings of the 21st ACM-SIGPLAN International Conference on Functional Programming, (ICFP)|année= 2016 | mois= Septembre|pages=168--179}}</ref>, mais le lecteur peut en imaginer d'autres. Tout d'abord on construit toutes les permutations de la phrase ''vos beaux yeux -- me font mourir -- d'amour''; 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 ''belle Marquise''. L'algorithme est '''''récursif''''' parce qu'il s'invoque lui-même. En effet, pour construire toutes les permutations de ''belle Marquise -- vos beaux yeux -- me font mourir -- d'amour'', il
faut construire toutes les permutations de ''vos beaux yeux -- me font mourir -- d'amour''. 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 ''belle Marquise -- vos beaux yeux -- me font -- mourir -- d'amour'', 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 ''belle Marquise -- vos beaux yeux -- me font -- mourir -- d'amour -- pour vous'', qui a six constituants.

=== Les permutations courtes ===
Pour construire les permutations de ''Belle marquise -- vos beaux yeux -- me font mourir -- d'amour'', il faut auparavant construire toutes les permutations de la phrase ''vos beaux yeux -- me font mourir -- d'amour''.  Ces permutations sont au nombre de six et sont construites en insérant le morceau de phrase ''vos beaux yeux'' en première, deuxième et troisième position dans les deux permutations de la phrase ''me font mourir -- d'amour'' (à savoir ''me font mourir -- d'amour'' et ''d'amour -- me font mourir'').  Comment sont construites ces deux permutations ? En insérant en première position et en deuxième position le segment ''me font mourir'' dans les permutations de la phrase ''d'amour''.  L'aspect récursif<ref group="note">L'algorithme s'invoque lui-même de façon répétitive </ref> de l'algorithme apparaît clairement.

=== Bien démarrer ===
Combien y a-t-il de permutations de la phrase ''d'amour'' ?  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.

== Un exemple liminaire : la factorielle ==

Prenons l'exemple de la [[factorielle]]. Celle-ci se définit pour des [[Entier naturel|entiers naturels]] de la fonction suivante :

:<math>n! = 1\times 2\times 3\times \cdots \times (n-1) \times n</math>

autrement dit :

:<math>n! = (n-1)! \times n</math>

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.

On voit avec cet exemple deux points majeurs de la récursion :
* L'algorithme s'appelle lui-même, <math>n!</math> a besoin de <math>(n-1)!</math>
* 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.

=== Présentation plus mathématique ===

:<math>n! = \prod_{i=1}^n i = 1\times 2\times 3\times \cdots \times (n-1) \times n</math>

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 :

:<math>n!=\begin{cases}
1&\text{si }n = 0\\
n \times (n-1)!&\text{sinon}
\end{cases}</math>

Autrement dit, la factorielle d'un nombre qui n'est pas 0 est obtenue en multipliant par ''n'' la factorielle de ''n'' – 1. Cette définition de la ''factorielle'' peut se traduire par le programme suivant en [[pseudo-code]] :

 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)

Préciser que ''factorielle''(0) = 1 est fondamental : sans cela la fonction ne serait pas définie et l'algorithme s'invoquerait indéfiniment. Le cas ''n'' = 0 est appelé ''cas de base''. Sans sa présence, l'algorithme ne peut pas se terminer. L'autre cas est appelé ''cas de propagation'', c'est lui qui contient l'appel récursif.
On peut programmer ainsi d'autres suites telles que la [[suite de Fibonacci]], tandis que la fonction suivante :

 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)

définit la fonction identiquement égale à 1 si la [[conjecture de Syracuse]] est vraie.

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 [[arbre (informatique)|arbres]], ou plus généralement sur des ensembles munis d'une [[relation bien fondée]]. Parmi les relations bien fondées les plus connues, il y a l'ordre sur la structure des objets qui donne lieu à la [[récurrence structurelle]] et l'ordre naturel sur les entiers positifs qui donne lieu à la récursivité numérique (ou récursivité sur les entiers). Le [[Algorithme de tri|tri]], le problème des [[tours de Hanoï]] et la génération des [[permutation]]s (c'est-à-dire la généralisation de l'exemple de Monsieur Jourdain) sont des exemples paradigmatiques d'application d'algorithmes récursifs.

== Un autre exemple : le nombre de partitions d'un entier naturel en au plus q parties ==

Nous allons considérer un cas tiré des mathématiques où l'approche récursive s'impose (voir l'article [[Partition d'un entier]]) :

'''Un exemple :''' Une ''partie'' 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 <math>d(5,3)</math> le nombre de
partitions de 5 en ''au plus'' 3 parties, on a <math>d(5,3) = 5
</math> et si on écrit <math>d'(5,3)</math> le nombre de
partitions de 5 en ''exactement'' 3 parties, on a <math>d'(5,3) = 2 </math>, ces partitions sont 3+1+1 et 2+2+1.

'''Les cas aux limites :'''
* <math>d(0,q) = 1 </math>, parce que la seule partition de 0 est celle constituée d'aucune partie.
* <math>d(p+1,0) = 0 </math> parce que toute partition d'un entier strictement positif a au moins une partie.
* <math>d(p,q) = d(p,p) </math> pour <math>p<q</math>, parce que le nombre de parties d'un entier est au plus égal à sa valeur.

'''Le cas général :'''
On voit facilement que le nombre de
partitions de p en ''au plus'' q parties est le nombre de
partitions de p en ''exactement'' q parties plus le nombre de
partitions de p en ''au plus'' q-1 parties. Donc
: <math>d(p,q) = d'(p,q) + d(p,q-1)</math>.
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ù :
: <math>d'(p,q) = d(p-q,q)</math>
et finalement
* <math>d(p,q) = d(p-q,q) + d(p,q-1)</math>.

Autrement dit, ''si <math>p\ge q</math>, 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''.

On a bien un énoncé récursif.

'''Retour à l'exemple''' : 
on a donc (le lecteur est invité à faire
tous les calculs intermédiaires)
: <math>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.
</math>.

Voici la forme complète de la fonction récursive : 
 d(p, q) = '''si''' p = 0 '''alors''' 1
          '''sinon''' '''si''' q = 0 '''alors''' 0
          '''sinon''' '''si''' q > p '''alors''' d(p, p)
          '''sinon''' d(p-q, q) + d(p, q-1)

== D'autres fonctions récursives à plusieurs arguments ==

Parmi les fonctions récursives à deux arguments on trouve la [[fonction d'Ackermann|fonction d'Ackermann-Péter]]. Le [[Plus grand commun diviseur|pgcd]] peut aussi être présenté récursivement,

 pgcd(p, q) = '''si''' p = 0 '''alors''' q
          '''sinon''' '''si''' q = 0 '''alors''' p
          '''sinon''' '''si''' q ≤ p '''alors''' pgcd(p-q, q)
          '''sinon''' pgcd(p, q-p)

de même que les [[Coefficient binomial#Propriété récursive des coefficients binomiaux d'entiers|coefficients binomiaux]] quand ils sont définis par la formule de Pascal.

La [[fonction de Sudan]] est une fonction à trois arguments (l'indice ''n'' est le troisième argument).

== Algorithmes récursifs non numériques ==
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.

=== Algorithmes récursifs sur les [[Liste (informatique)|listes]] ===
==== ++ ====
L'opérateur '''++''' concatène deux listes, autrement dit, prolonge la première liste par la seconde liste.
:''[ ]'' '''++''' ℓ2 = ℓ2
:(x:ℓ1) '''++''' ℓ2 = x:(ℓ1 '''++''' ''ℓ2)''
Le cas de base est ''[ ]'' '''++''' ℓ2 = ℓ2.
==== map ====
É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 '''map''' (en français « applique »).  Si la liste donnée est vide, le résultat est la liste vide (qui se note ''[ ]'') ; c'est le cas de base.  Si la fonction s'appelle ''f'' et si la liste donnée est constituée de ''x'' suivi d'une liste ''ℓ'' alors le résultat est la liste constituée de '' f x''<ref group="note">On remarquera que l'on note l'application d'une fonction ''f x'' ce qui est traditionnel dans les langages de programmation fondés sur la récursivité.</ref> suivi de la liste '''map''' ''f ℓ''.
:'''map''' ''f [ ] = [ ]''
:'''map''' ''f (x:ℓ) = f x : ('''''map''' ''f ℓ)''

==== ins ====
La fonction '''ins''' insère un élément dans une liste à toutes les positions, produisant une liste de listes.
: '''ins''' ''x [ ] = [[X (mathématique)|x]]
: '''ins''' ''x (y:ℓ)  =  (x:y:ℓ) :'' '''map''' ''((:) y) ('''''ins''' ''x ℓ)''
==== concat ====
La fonction '''concat''' prend une liste de listes et concatène ces listes en une seule liste.
: '''concat''' ''[ ] = [ ]''
: '''concat''' ''(ℓ:ℓℓ) = ℓ ++ (concat ℓℓ)''
==== permutations ====
'''permutations''' est l'algorithme présenté dans le premier exemple.  Il prend une liste et retourne la liste de toutes les permutations de cette liste.
:'''permutations''' ''[x] = [[X (mathématique)|x]]''
: '''permutations''' ''x:ℓ ='' '''concat''' ''('''''map''' ''('''''ins''' ''x) ('''''permutations''' ''ℓ))''

[[File:Arbre binaire bravo.png|thumb|Arbre binaire portant les étiquettes B, R, A, V, O]]

=== Algorithmes récursifs sur les [[Arbre binaire|arbres binaires]] ===
==== taille ====
La taille d'un arbre binaire est le nombre de ses nœuds internes
: '''taille''' ''(Feuille x) = 0''
: '''taille''' ''(t1 • t2) = ('' '''taille''' ''t1) + ('' '''taille''' ''t2)''

==== motDesFeuilles ====
Étant donné un arbre binaire, on peut construire son ''mot des feuilles''.  Ainsi le mot des feuilles de l'arbre de la figure ci-contre est ''BRAVO'' ou, plus précisément, la liste ''[`B`,`R`,`A`,`V`,`O`]''.  L'algorithme récursif '''motDesFeuilles''' prend un arbre binaire et retourne une liste.
: '''motDesFeuilles''' ''(Feuille x) = [x]''
: '''motDesFeuilles''' ''(t1 • t2) = ('' '''motDesFeuilles''' ''t1) ++ ('' '''motDesFeuilles''' ''t2)''

== Prouver la correction d'un algorithme récursif ==

Prouver le bon fonctionnement d'un algorithme récursif nécessite de vérifier deux propriétés : premièrement ''l'algorithme se termine'' et deuxièmement ''si l'algorithme se termine, il fait bien ce qu'on attend de lui'' (correction partielle). Dans le cas des algorithmes récursifs, ces méthodes sont spécifiques.

=== Problème de la terminaison ===
Pour prouver la [[terminaison d'un algorithme|terminaison]] 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 [[relation d'ordre]]. Cet ordre ne doit avoir que des ''chaînes descendantes finies'' (on dit qu'il est [[Relation bien fondée|bien fondé]]) 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.

=== Théorème de terminaison ===

Soient <math>f\,</math> un algorithme récursif défini sur un ensemble <math>A \,</math> et <math><\,</math> un [[ordre bien fondé]] sur <math>\,A</math>.

<math>x \in A</math> étant donné, on note, <math> A_x </math> l'ensemble des <math>y \,</math> tels que <math>f(x) \,</math> appelle <math>f(y) \,</math>.

Soit <math>x \in A</math>, '''si''', <math>\forall y \in A\ (y\in A_x \Rightarrow y < x)\,</math>,
'''alors''' <math>f(x) \,</math> se termine.

==== Terminaison de la fonction d qui calcule le nombre de décompositions de p en au plus q sommants ====

L'ordre que l'on prend est l'[[ordre lexicographique]] sur <math>\N\times\N</math>. On a
* <math>(p,q) > (p',q')</math> si et seulement si
** <math>p>p'</math>
** ou <math>p = p'</math> et <math>q > q'</math>.
Cet ordre est bien fondé.

==== Terminaison de la fonction Syracuse ====

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 ''n''. Si c'était le cas, elle définirait effectivement la fonction identiquement égale à 1.

=== Problème de la correction partielle ===

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 ''n-1'' éléments, on aboutira à une suite de toutes les permutations de ''n'' éléments.

==== Correction partielle sur l'exemple du pgcd ====
Prenons l'exemple du <math>\mathsf{pgcd}</math>, il s'agit de montrer que si <math>\,p</math> et <math>\,q</math> sont positifs alors
* <math>\mathsf{pgcd}(p,q) | p \wedge \mathsf{pgcd}(p,q) | q \wedge (\forall r\ge 0 . (r|p \wedge r|q) \Rightarrow r|\mathsf{pgcd}(p,q))</math>,
ce qui est la caractérisation du plus grand diviseur commun de deux nombres où <math>\,s|t</math> signifie que <math>\,s</math> divise <math>\,t</math> (on a, en particulier, <math>\,p|0</math> pour tout <math>\,p</math>). Notons <math>\mathcal{P}_{\mathsf{pgcd}}(p,q)</math> cette propriété.

Pour montrer la correction de l'algorithme ci-dessus, on suppose <math>\forall (p',q')\in \mathbf{N}\times \mathbf{N} . \mathcal{P}_{\mathsf{pgcd}}(p',q')</math> et on essaie de montrer <math>\mathcal{P}_{\mathsf{f}}(p,q)</math> où <math>\,\mathsf{f}</math> est la fonction <math>\mathbf{si}\ p = 0\ \mathbf{alors}\ q\ \mathbf{sinon}\ \mathbf{si}\ q = 0\ \mathbf{alors}\ p\ \mathbf{sinon}\ \mathbf{si}\ q \le p \ \mathbf{alors}\ \mathsf{pgcd}(p-q,q)\ \mathbf{sinon} \ \mathsf{pgcd}(p,q-p)</math>.

:On procède par cas.
** Si <math>\,p=0</math> alors <math>\mathsf{f}(p,q) = q</math> et donc <math>\mathsf{f}(p,q)| 0</math>, mais aussi <math>\mathsf{f}(p,q)| q</math>. De plus, si <math>\,r|0</math> et si <math>\,r|q</math> alors clairement <math>r|\mathsf{f}(p,q)</math>, puisque précisément <math>\mathsf{f}(p,q) = q</math>.
** Si <math>\,q=0</math> on obtient le même résultat.
** Si <math>0<q\le p</math>, on a <math>\mathsf{f}(p,q)=\mathsf{pgcd}(p-q,q)</math>, d'autre part si on a <math>\mathsf{pgcd}(p-q,q) | p-q \wedge \mathsf{pgcd}(p-q,q) | q</math> alors <math>\mathsf{pgcd}(p-q,q)</math> divise la somme donc <math>\mathsf{f}(p,q) | p \wedge \mathsf{f}(p,q) | q</math>. D'autre part, si <math>\,r|p</math> et <math>\,r|q</math> alors par hypothèse <math>\,r|(p-q)</math> et donc <math>r|\mathsf{pgcd}(p-q,q))</math> et donc <math>r|\mathsf{f}(p,q))</math>, c.q.f.d.
** Si <math>\,0<q< p</math>, on raisonne comme ci-dessus en inversant les rôles de <math>\,p</math> et <math>\,q</math>.

De la démonstration ci-dessus, on déduit que si l'algorithme de <math>\mathsf{pgcd}</math> se termine alors il satisfait :
:<math>\forall (p,q)\in \mathbf{N}\times \mathbf{N} . \mathcal{P}_{\mathsf{pgcd}}(p,q)</math> et donc <math>\mathsf{pgcd}</math> calcule bien le ''plus grand commun diviseur''.

== Efficacité ==

=== Simplicité de description versus efficacité ===
La mise en œuvre des algorithmes récursifs nécessite le plus souvent<ref group="note">Les fonctions [[Récursion terminale|récursives terminales]] par exemple ne requièrent pas de pile.</ref> une [[Pile (informatique)|pile]]. 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 [[Compilateur|compilation]] des langages de programmation réduit encore la différence d'efficacité. Voici quelques arguments en faveur de la présentation récursive :
* La présentation récursive permet d'expliquer simplement des algorithmes beaucoup plus astucieux et efficaces, comme cela a été montré par [[Tony Hoare]] avec son algorithme de [[tri rapide]].
* 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{{refsou}}.
* Des structures de données récursives, comme les [[quadtree]]s, ont été conçues pour leur efficacité. La manière la plus naturelle de les gérer est par des algorithmes récursifs.

=== Contributions ===
* La contribution la plus percutante dans ce débat a été celle de [[John Backus]], l'inventeur du [[Fortran]], qui a pris clairement le parti de la programmation fonctionnelle, donc de la programmation récursive, lors de la remise de son [[prix Turing]] en [[1977]].
* [[Niklaus Wirth]], l'inventeur du langage de programmation [[Pascal (langage)|Pascal]] écrit :
{{Citation étrangère bloc|lang=en|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.|Niklaus Wirth|''Algorithms + Data Structures {{=}} Programs''<ref>{{Ouvrage|langue=en|auteur1=Niklaus Wirth|titre=Algorithms + Data Structures = Programs|lieu=Englewood Cliffs, New Jersey|éditeur=Prentice-Hall, Inc.|année=1976|pages totales=366|isbn=978-0-13-022418-7|isbn10=0-13-022418-9|passage=129}}.</ref>.}}
{{début citation}} 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.{{fin citation}}
* [[C. A. R. Hoare]] qui a écrit le premier compilateur (du langage [[Algol 60]]) implémentant la récursivité, note dans son discours lors de la remise du [[prix Turing]] en [[1980]]<ref name="Hoare">{{Article|langue=en
|prénom1=Charles Antony Richard|nom1=Hoare
|lien auteur1=Charles Antony Richard Hoare|titre=The Emperor's Old Clothes
|périodique=Communications of the ACM|lien périodique=Communications of the ACM
|mois=février|année=1981|volume=24|numéro=2|pages=75-83
|url texte=https://www.cs.fsu.edu/~engelen/courses/COP4610/hoare.pdf}}.</ref> que son algorithme de [[tri rapide]] 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 :
{{Citation étrangère bloc|lang=en|I have regarded it as the highest goal of programming langage design to enable good ideas to be elegantly expressed.|C. A. R. Hoare|''The Emperor's Old Clothes''<ref name="Hoare" />.}}
{{début citation}} 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. {{fin citation}}

== Récursion terminale ==
{{article détaillé|Récursion terminale}}
Dans la définition d'une fonction récursive <math>f</math>, l'appel récursif est en ''position terminale'' si elle est de la forme

: <math>
f(x) = \begin{cases}g(x)& \text{si }p(x)\text{,}\\f(h(x))& \text{sinon.}\end{cases}
</math>

Dans cette écriture, <math>g</math> et <math>h</math> sont des fonctions indépendantes de <math>f</math>. La fonction <math>p</math> est la condition d'arrêt. L'important, dans cette définition, est que l'appel de <math>f</math> ne soit pas englobé dans une autre expression. Une telle récursion est dite [[récursion terminale]]. En pseudo-code, la définition récursive terminale peut s'écrire

 '''fonction''' f(x)
     '''si''' p(x)
         '''retourner''' g(x)
     '''sinon'''
         '''retourner''' f(h(x))

où ''x'' peut être un ''n''-uplet contenant plusieurs variables.

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

 '''fonction''' f(x)
     '''tant que''' '''vrai'''
         '''si''' p(x)
             '''retourner''' g(x)
         '''sinon'''
             x ← h(x)

Par exemple, ce programme Python donne une définition récursive non terminale <code>fact</code> de la factorielle :

<syntaxhighlight lang="python">
def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n - 1)
</syntaxhighlight>

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é ''accumulateur''<ref>{{ouvrage|id=Abel|prénom1=Harold
|nom1=Abelson|responsabilité2=auteurs|prénom2=Gerald Jay
|nom2=Sussman|prénom3=Julie
|nom3=Sussman|responsabilité3=collaboratrice
|titre=[[Structure and interpretation of computer programs]]|numéro édition =2
|année=1996
|numéro=1.2.1
|chapitre = [https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1 Linear Recursion and Iteration]
|éditeur=[[MIT Press]] et [[McGraw-Hill Education|McGraw-Hill]]
<!-- |lieu=Cambridge (Mass.) et New York -->
|pages totales = XXIII+657
<!-- |collection=The MIT electrical and computer science series -->
|isbn=978-0-07-000484-9
|url texte=http://mitpress.mit.edu/sicp/full-text/book/book.html}}.</ref>.

Ce programme Python donne une définition récursive terminale <code>fact_iter</code> de la factorielle :

<syntaxhighlight lang="python">
def fact_iter(n, a):
    if n == 0:
        return a
    else:
        return fact_iter(n - 1, n * a)

def fact(n):
    return fact_iter(n, 1)
</syntaxhighlight>

tandis que ce programme Python donne une définition itérative <code>fact_iter</code> de la factorielle :

<syntaxhighlight lang="python">
def fact_iter(n, a):
    while True:
        if n == 0:
            return a
        else:
            n, a = n - 1, n * a

def fact(n):
    return fact_iter(n, 1)
</syntaxhighlight>

== Autres situations et corécursivité ==
La [[récursivité]] (et sa duale la {{lien|trad=corecursion|lang=en|fr=corécursivité}}) se retrouvent dans d'autres situations, où elle prend parfois d'autres noms.
[[Fichier:Sierpinski carpet 6, white on black.svg|thumb|Tapis de Sierpiński.]]
* L'[[autosimilarité]] 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é.
* Les [[fractale]]s ont cette propriété d'autosimilarité, mais elles ont plutôt à voir avec le concept un peu différent qui s'appelle la {{lien|trad=corecursion|lang=en|fr=corécursivité}} (ou corécursion). Le [[tapis de Sierpiński]], du nom de [[Wacław Sierpiński]], 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.
[[Fichier:Van Eyck - Arnolfini Portrait.jpg|vignette|redresse=1|''[[Les Époux Arnolfini]]'' par [[Jan van Eyck]], [[National Gallery]], 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.]]
* La [[mise en abyme]] 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 ''[[La vache qui rit|Vache qui rit]]'' de [[Benjamin Rabier]].
* Quand on écrit
 fibs :: [Integer]
 fibs = 0:1:zipWith (+) (fibs) (tail fibs)
:en [[Haskell]], il s'agit de corécursivité.  On définit ainsi une suite infinie (un stream) de toutes les valeurs de la [[suite de Fibonacci]]. On pourra récupérer la ''n''-ième valeur de '''fibs''', que l'on ne calcule qu'une fois, et obtenir ainsi le ''n''-ième nombre de Fibonacci.  Cette suite infinie est décrite en langue naturelle ainsi, c'est la suite ''fibs'' qui commence par 0, suivi de 1, puis des éléments obtenus en ajoutant le premier élément de la suite ''fibs'' au deuxième de la suite ''fibs'' pour former le troisième élément de la suite ''fibs'', puis le deuxième de la suite ''fibs'' au troisième de la suite ''fibs'' pour former le quatrième élément de la suite ''fibs'', puis ainsi de suite, le i-ème élément de la suite ''fibs'' au i+1-ème de la suite ''fibs'' pour former le i+2-ème élément de la suite ''fibs'', etc.

== Notes et références ==
=== Références ===
{{Références}}
=== Notes ===
{{Notes}}

== Voir aussi ==
=== Articles connexes ===
{{autres projets
  | wikiversity = Récursivité dans l'algorithmique et la programmation
  | wikiversity titre = Récursivité dans l'algorithmique et la programmation
}}
{{colonnes|nombre=3|
* [[Fonction récursive]]
* [[Fonction récursive primitive]]
* [[Récursion mutuelle]]
* [[Type récursif]]
* [[Pile (informatique)]]
* [[Imprédicativité]]
* [[Évaluation paresseuse]]
* [[Diviser pour régner (informatique)]]
* [[Paradigme (programmation)|Paradigme de programmation]]
* [[Programmation fonctionnelle]]
* [[Fonction de Sudan]]
* [[Fonction 91 de McCarthy]]
* [[Fonction de Takeuchi]]
* [[Mémoïsation]]
* [[Tri fusion]]
* [[Algorithme de Casteljau]]
* [[Théorème de Masreliez]]
* [[Algorithme X de Knuth]]
* [[Problème des huit dames]]
* [[Exponentiation rapide]]
* [[Algorithme de Karatsuba]]
* [[Algorithme des moindres carrés récursifs]]
* [[Algorithme de Douglas-Peucker]]
* [[Algorithme de Cooley-Tukey]]
* [[Algorithme de Lehmer-Schur]]
* [[Algorithme de Clenshaw]]
* [[Acronymie récursive]]
* [[Algorithme de Havel-Lakimi]]
}}

=== Bibliographie ===
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.

==== En français ====
* Anne Brygoo, Titou Durand, Maryse Pelletier, Christian Queinnec {{et al.}} ''Programmation récursive (en Scheme)'' Cours et exercices corrigés Collection: Sciences Sup, Dunod, 2004
* Emmanuel Chailloux, Pascal Manoury et Bruno Pagano, ''Développement d'applications avec Objective Caml'', Éditions O'Reilly, Paris, 2000
* Sylvain Conchon et Jean-Christophe Filliâtre, ''Apprendre à programmer avec OCaml''. Algorithmes et structures de données. Éditions Eyrolles, 2014
* C. Livercy, [http://denif.ens-lyon.fr/data/programmation_enslyon/2007_sem2/biblio/Livercy.pdf ''Theorie des programmes / schemas, preuves, sémantique''], Dunod, 1978
* Niklaus Wirth, ''Algorithmes et structures de données'', 1987, trad. par J.A. Hernandez et P. Kruchten / {{2e|édition}} / Paris : Eyrolles , rééd. 1989
* Laurent Arditi et Stéphane Ducasse, [http://sdmeta.gforge.inria.fr/Books/Scheme/book.html ''La programmation : une approche fonctionnelle et récursive avec Scheme'']

==== En anglais ====
* [http://mitpress.mit.edu/sicp/full-text/book/book.html Harold Abelson and Gerald Sussman: "Structure and Interpretation Of Computer Programs"]
* [http://www.ibm.com/developerworks/linux/library/l-recurs/index.html Jonathan Bartlett: "Mastering Recursive Programming"]
* [http://www.cs.cmu.edu/~dst/LispBook/ David S. Touretzky: "Common Lisp: A Gentle Introduction to Symbolic Computation"]
* [http://www.htdp.org/2003-09-26/Book/ Matthias Felleisen: "How To Design Programs: An Introduction to Computing and Programming"]
* [http://www.cs.duke.edu/~ola/ap/recurrence.html Owen L. Astrachan: "Big-Oh for Recursive Functions: Recurrence Relations" ]
* Richard Bird et Philip Wadler, ''Introduction to Functional Programming'', Prentice Hall International Series in Computing Science, 1988
* Richard Bird, ''Introduction to Functional Programming using Haskell'', {{2e}} éd., Prentice Hall International Series in Computing Science, 1998
* Guy Cousineau et Michel Mauny, ''The Functional Approach to Programming'', [[Cambridge University Press]], Cambridge, 1998
* Edsger Dijkstra, ''A Discipline of Programming'', 1976
* [[Anatoli Maltsev]], ''Algorithms and Recursive Functions'' , Wolters-Noordhof Publishing Co. "Groningen", 1970
* John McCarthy, « Recursive Functions of Symbolic Expressions », ''Comm. of the ACM'', 1960, 3 (4), {{p.|184–195}}
* John C. Mitchell, ''Concepts in Programming Languages'', Cambridge University Press, 2002
* Graham Hutton, ''Programming in Haskell,'' Cambridge University Press, 2007
* Chris Okasaki, ''Purely functional data structures'', Cambridge University Press, 1998
* Rózsa Péter, ''Recursive Functions'', traduit par István Földes, New York, Academic Press, 1967
* Benjamin C. Pierce, ''Types and Programming Languages'', The MIT Press 2002
* Jeffrey Soden Rohl, ''Recursion Via Pascal'', Cambridge University Press, 1984

{{Portail|informatique théorique|logique}}

[[Catégorie:Méthode algorithmique|récursif]]
[[Catégorie:Langage fonctionnel]]