Algorithme récursif
Un algorithme récursif est un algorithme qui résout un problème en calculant des solutions d'instances plus petites du même problème1. L'approche récursive est un des concepts de base en informatique.
Les premiers langages de programmation qui ont autorisé l'emploi de la récursivité sont LISP et Algol 60. Depuis, tous les langages de programmation généraux réalisent une implémentation de la récursivité.
On oppose généralement les algorithmes récursifs aux algorithmes dits itératifs qui s'exécutent sans appeler explicitement l'algorithme lui-même.
Sommaire [afficher]
Un exemple préliminaire[modifier | modifier le code]
Commençons par un exemple tiré du Bourgeois gentilhomme (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 permutations ? 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, 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.
Un exemple plus mathématique : la factorielle[modifier | modifier le code]
Prenons maintenant un exemple issu des mathématiques, celui de la factorielle. Celle-ci se définit intuitivement pour des entiers naturels de la fonction suivante :
n! = \prod_{i=1}^n i = 1\times 2\times 3\times \cdots \times (n-1) \times n
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:
n!=\begin{cases}
1&\text{si }n = 0\\
n \times (n-1)!&\text{sinon}
\end{cases}
Cette définition de la factorielle peut se traduire par le programme suivant en pseudo-code :
factorielle(n) =
si (n = 0) alors 1
sinon 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) =
si (n = 0) ou (n = 1) alors 1
sinon si (n mod 2 = 0) alors syracuse(n/2)
sinon 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 arbres, ou plus généralement sur des ensembles munis d'une relation bien fondée. On peut ainsi considérer deux notions plus ou moins distinctes de récursivité : la récursivité structurelle et la récursivité numérique (ou récursivité sur les entiers). Le tri, le problème des tours de Hanoï et la génération des permutations (c'est-à-dire la généralisation de l'exemple de Monsieur Jourdain) sont également 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[modifier | modifier le code]
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 d(5,3) le nombre de partitions de 5 en au plus 3 parties, on a d(5,3) = 5
et si on écrit d'(5,3) le nombre de partitions de 5 en exactement 3 parties, on a d'(5,3) = 2 , ces partitions sont 3+1+1 et 2+2+1.
Les cas aux limites :
d(0,q) = 1 , parce que la seule partition de 0 est celle constituée d'aucune partie.
d(p+1,0) = 0 parce que toute partition d'un entier strictement positif a au moins une partie.
d(p,q) = d(p,p) pour p
sinon d(p-q, q) + d(p, q-1)
D'autres fonctions récursives à plusieurs arguments[modifier | modifier le code]
Parmi les fonctions récursives à deux arguments on trouve la fonction d'Ackermann-Peter. Le 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 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).
Prouver la correction d'un algorithme récursif[modifier | modifier le code]
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.
Le problème de la terminaison[modifier | modifier le code]
Pour prouver la 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'un ordre. Cet ordre ne doit avoir que des chaînes descendantes finies (on dit qu'il est 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.
Le théorème de terminaison[modifier | modifier le code]
Soient f\, un algorithme récursif défini sur un ensemble A \, et <\, une relation d'ordre bien fondée sur \,A. x \in A étant donné, on note, A_x l'ensemble des y \, tels que f(x) \, appelle f(y) \,. Soit x \in A, si, \forall y \in A\ (y\in A_x \Rightarrow y < x)\,, alors f(x) \, se termine. La terminaison de la fonction d qui calcule le nombre de décompositions de p en au plus q sommants[modifier | modifier le code] L'ordre que l'on prend est l'ordre de lexicographique sur \mathbb{N}\times\mathbb{N}. On a (p,q) > (p',q') si
p>p'
ou p = p' et q > q'.
Cet ordre est bien fondé.
La terminaison de la fonction syracuse[modifier | modifier le code]
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.
Le problème de la correction partielle[modifier | modifier le code]
Il faut monter 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.
La correction partielle sur l'exemple du pgcd[modifier | modifier le code]
Prenons l'exemple du \mathsf{pgcd}, il s'agit de montrer que si \,p et \,q sont positifs alors
\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)),
ce qui est la caractérisation du plus grand diviseur commun de deux nombres où \,s|t signifie que \,s divise \,t (on a, en particulier, \,p|0 pour tout \,p). Appelons \mathcal{P}_{\mathsf{pgcd}}(p,q) cette propriété.
Pour montrer la correction de l'algorithme ci-dessus, on suppose \forall (p',q')\in \mathbf{N}\times \mathbf{N} . \mathcal{P}_{\mathsf{pgcd}}(p',q') et on essaie de montrer \mathcal{P}_{\mathsf{f}}(p,q) où \,\mathsf{f} est la fonction \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).
On procède par cas.
Si \,p=0 alors \mathsf{f}(p,q) = q et donc \mathsf{f}(p,q)| 0, mais aussi \mathsf{f}(p,q)| q. De plus, si \,r|0 et si \,r|q alors clairement r|\mathsf{f}(p,q), puisque précisément \mathsf{f}(p,q) = q.
Si \,q=0 on obtient le même résultat.
Si 0
\forall (p,q)\in \mathbf{N}\times \mathbf{N} . \mathcal{P}_{\mathsf{pgcd}}(p,q) et donc \mathsf{pgcd} calcule bien le plus grand commun diviseur.
La présentation récursive d'un algorithme conduit-elle à un programme moins efficace qu'une présentation itérative ?[modifier | modifier le code]
Simplicité de description versus efficacité[modifier | modifier le code]
La mise en œuvre des algorithmes récursifs nécessite le plus souvent2 une 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 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 efficaces3.
Des structures de données récursives, comme par exemple les quadtrees, ont été conçues pour leur efficacité. La manière la plus naturelle de les gérer est par des algorithmes récursifs.
Contributions[modifier | modifier le code]
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 écrit :
« 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 = Programs4.
« 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. »
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 19805 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 :
« I have regarded it as the highest goal of programming language design to enable good ideas to be elegantly expressed. »
— C. A. R. Hoare, The Emperor's Old Clothes5.
« 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. »
Récursion terminale[modifier | modifier le code]
Article détaillé : Récursion terminale.
Dans la définition d'une fonction récursive f, l'appel récursif est en position terminale si elle est de la forme :
f(x) = \begin{cases} s(x), & \mbox{si }R(x)\\f(r(x)), & \mbox{sinon} \\ \end{cases}
Dans cette écriture, r et s sont des fonctions indépendantes de f. La fonction R est la condition d'arrêt. L'important, dans cette définition, est que l'appel de f n'est pas englobé dans une autre expression. Un telle récursion est une récursion terminale. En programme, cela peut s'écrire
f(x) = si R(x) alors s(x) sinon f(r(x))
La définition récursive terminale se transcrit automatiquement en une définition itérative. C'est la fonction définie par
tantque non R(x) faire x = r(x) ;
retourner s(x)
La définition récursive de la factorielle donnée plus haut n'est pas terminale, mais on peut la transformer en récursion terminale par l'adjonction d'un argument additionnel appelé accumulateur6.
Autres situations[modifier | modifier le code]
La récursivité se retrouve dans d'autres situations, où elle prend parfois d'autres noms.
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.
Les fractales ont cette propriété d'autosimilarité. 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.
Une publicité récursive.
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 récursivité en mathématiques. Des publicités emploient ce procédé, dont la fameuse Vache qui rit.
Notes et références[modifier | modifier le code]
↑ Ronald L. Graham, Donald E. Knuth et Oren Patashnik (trad. Alain Denise), Mathématiques concrètes : Fondations pour l'informatique, Vuibert, coll. « Vuibert informatique », 2003, 2e éd., 687 p. (ISBN 978-2711748242), p. 1.
↑ Les fonctions récursives terminales par exemple ne requièrent pas de pile.
↑ Does Functional programming allow better runtime compiler optimizations? [archive] et Can a functional programming language compiler optimize as well as an imperative programming language compiler in practice? [archive].
↑ Niklaus Wirth, Algorithms + Data Structures = Programs, Englewood Cliffs, New Jersey, Prentice-Hall, Inc., 1976 (ISBN 0-13-022418-9), page 129.
↑ a et b (en) Charles Antony Richard Hoare, « The Emperor's Old Clothes », Communications of the ACM, vol. 24, no 2, février 1981, p. 75-83 (lire en ligne [archive]).
↑ Harold Abelson, Gerald Jay Sussman (auteurs) et Julie Sussman (collaboratrice), Structure and interpretation of computer programs, MIT Press et MGraw-Hill, 1996, 2e éd., XXIII+657 p. (ISBN 978-0-07-000484-9, lire en ligne [archive]), chap. 1.2.1 (« Linear Recursion and Iteration [archive] »).
Voir aussi[modifier | modifier le code]
Articles connexes[modifier | modifier le code]
Sur les autres projets Wikimedia :
Récursivité dans l'algorithmique et la programmation, sur Wikiversity
Récursivité
Fonction récursive
Fonction récursive primitive
Récursion terminale
Récursion mutuelle
Récursivité structurelle
Type récursif
Pile (informatique)
Imprédicativité
Évaluation paresseuse
Diviser pour régner (informatique)
Dichotomie
Paradigme de programmation
Programmation fonctionnelle
Fonction d'Ackermann
Fonction de Sudan
Fonction 91 de McCarthy
Fonction de Takeuchi
Mémoïsation
Tri rapide
Tri fusion
Algorithme de De Casteljau
Théorème de Masreliez
Algorithme X de Knuth
Problème des huit dames
Tours de Hanoï
Exponentiation rapide
Algorithme de Karatsuba
Fractale
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
Aucun commentaire:
Enregistrer un commentaire