vignette|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'instances plus petites du même problème.. 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é. 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
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.
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écursifL'algorithme s'invoque lui-même de façon répétitive 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 entiers naturels de la fonction suivante :
autrement dit :
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, a besoin de 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
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 :
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) = 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. 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 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 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 le nombre de partitions de 5 en au plus 3 parties, on a et si on écrit le nombre de partitions de 5 en exactement 3 parties, on a , ces partitions sont 3+1+1 et 2+2+1.
Les cas aux limites : , parce que la seule partition de 0 est celle constituée d'aucune partie. parce que toute partition d'un entier strictement positif a au moins une partie. pour , 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 . 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ù :
et finalement .
Autrement dit, si , 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) .
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-Péter. 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).
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 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 xOn 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é. 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 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 permutations x:ℓ = concat (map (ins x) (permutations ℓ)) Algorithmes récursifs sur les 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