Algorithme Récursif

Algorithme récursif

Les algorithmes récursifs et les fonctions récursives sont fondamentaux en informatique. Un algorithme est dit récursif s'il s'appelle lui-même.

Les premiers langages de programmation qui ont introduit la récursivité sont LISP et Algol 60 et maintenant tous les langages de programmation modernes proposent une implémentation de la récursivité.

On oppose généralement les algorithmes récursifs aux algorithmes dits impératifs ou itératifs qui s'exécutent sans invoquer ou appeler explicitement l'algorithme lui-même.

Sommaire

1 Un exemple préliminaire
2 Un exemple plus mathématique : la factorielle
3 Un autre exemple : le nombre de décompositions d'un entier naturel en au plus q sommants
4 D'autres fonctions récursives à plusieurs arguments
5 Prouver la correction d'un algorithme récursif
6 La présentation récursive d'un algorithme conduit-elle à un programme moins efficace qu'une présentation itérative ?
7 Voir aussi

Un exemple préliminaire

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

Prenons maintenant un exemple issu des mathématiques, celui de la factorielle. Celle-ci se définit intuitivement pour des entiers positifs par 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 suite récurrente:

$n!=\begin{cases} 1 \mbox{ si }n=0\\ n \times (n-1)! \mbox{ sinon} \end{cases}$

Ceci peut alors se traduire par le programme suivant en pseudo-code :

factorielle(entier k) :
si k=0
 alors renvoyer 1
 sinon renvoyer k * factorielle(k-1)
finsi

qui donnerait en Caml :

let rec factorielle = function
  0 → 1
| n → n * factorielle (n-1);;

et en Pascal :

function factorielle(n : integer):integer;
begin
   if n = 0 then factorielle := 1
   else factorielle := n * factorielle(n - 1);
end;

et en Java de façon naïve :

public int factorial(int n) {
  if (n == 0) 
    return 1;
  else 
    return n * factorial(n - 1);
}

Notons que les algorithmes ci-dessus, écrits dans des langages de programmation comme Java, ne prennent pas en compte le fait que le factoriel croit de manière exponentielle et dépasse rapidement la capacité de stockage des "int". Utiliser un type "long" à la place ne sert qu’à reculer pour mieux sauter : il faut trouver une vraie solution alternative.

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. On peut programmer ainsi d'autres suites telles que la suite de Fibonacci, tandis que la fonction suivante :

let rec syracuse n =
   if (n = 0) or (n = 1) then 1
   else if (n mod 2 = 0) then syracuse(n/2)
   else 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 ou les arbres, ou plus généralement sur des ensembles munis d'une relation bien fondée. 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 célèbres d'application d'algorithmes récursifs.

Un autre exemple : le nombre de décompositions d'un entier naturel en au plus q sommants

Nous allons considérer un cas tiré des mathématiques où l'approche récursive s'impose (voir l'article Fonction partage d'un entier).

Un exemple:

Un sommant est un naturel positif qui entre dans une somme quand on décompose un nombre en somme de naturels. Ainsi, les décompositions de 5 en au plus 3 sommants sont 5, 4+1, 3+2, 3+1+1, 2+2+1, si on écrit $d (5,3)$ le nombre de décomposition de 5 en au plus 3 sommants, on a $d (5,3) = 5$ et si on écrit $d'(5,3)$ le nombre de décomposition de 5 en exactement 3 sommants, on a $d'(5,3) = 2$ , car ces décompositions sont 3+1+1 et 2+2+1.

Les cas dégénérés:

Si $p = 0$ alors 0 n'a qu'une décomposition en au plus q sommants, à savoir celle constituée d'aucun sommant. On a donc $d (0, q) = 1$ . Il n'y pas de décomposition de p strictement positif en au plus zéro sommants, donc $d (p + 1,0) = 0$ . Si $p < q$ , il n'y a pas de décomposition de p en exactement q sommants, donc le nombre de décompositions de p en au plus q sommants est le nombre de décompositions de p en au plus p sommants, ce qui s'écrit: si $p < q$ alors $d (p, q) = d (p, p)$ .

Le cas général:

On voit facilement que le nombre de décompositions de p en au plus q sommants est le nombre de décompositions de p en exactement q sommants plus le nombre de décompositions de p en au plus q-1 sommants. Donc

$d (p, q) = d'(p, q) + d (p, q - 1)$ .

Or si p a exactement q sommants cela veut dire que tous ces sommants sont strictement positifs, on peut donc leur retirer 1. Or si on retire 1 à chacun de ces sommants on obtient une décomposition de p - q en au plus q sommants, d'où:

$d'(p, q) = d (p - q, q)$

et finalement

$d (p, q) = d (p - q, q) + d (p, q - 1)$ .

Autrement dit, si $p\ge q$ , le nombre de décompositions de p en au plus q sommants est le nombre de décompositions de p-q en au plus q sommants plus le nombre de décompositions de p en au plus q-1 sommants.

On a bien un énoncé récursif.

Retour à l'exemple:

on a donc (le lecteur est invité à faire tous les calculs intermédiaires)

$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.$ .

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-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

Puisqu'un algorithme (récursif ou non) est supposé résoudre un problème précis, il faut s'assurer qu'il fait bien la tâche qu'on lui assigne. Cela peut se faire rigoureusement et c'est pour cela que l'on parle de preuve. En fait, il faut 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

Il s'agit de fournir un ordre sur les paramètres de l'algorithme. Cet ordre doit d'abord ne pas avoir de chaînes infinies descendantes (on dit qu'il doit être bien fondé) et ensuite il doit être tel que si on invoque l'algorithme avec des paramètres, les invocations suivantes plus internes doivent se faire avec des paramètres plus petits pour l'ordre.

Le théorème de terminaison

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

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

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

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

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<q\le p$ , on a $\mathsf{f}(p,q)=\mathsf{pgcd}(p-q,q)$ , d'autre part si on a $\mathsf{pgcd}(p-q,q) | p-q \wedge \mathsf{pgcd}(p-q,q) | q$ alors $\mathsf{pgcd}(p-q,q)$ divise la somme donc $\mathsf{f}(p,q) | p \wedge \mathsf{f}(p,q) | q$ . D'autre part, si $\,r|p$ et $\,r|q$ alors par hypothèse $\,r|(p-q)$ et donc $r|\mathsf{pgcd}(p-q,q))$ et donc $r|\mathsf{f}(p,q))$ , c.q.f.d.
Si $\,0<q< p$ , on raisonne comme ci-dessus en inversant les rôle de $\,p$ et $\,q$ .

De la démonstration ci-dessus, on déduit que si l'algorithme de $\mathsf{pgcd}$ se termine alors il satisfait:

$\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 ?

La mise en œuvre des algorithmes récursifs nécessite une pile. C'est la difficulté d'implanter cette pile 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 l'opposition récursif et itératif est aussi vieux que l'informatique et les progrès récents de la compilation des langages de programmation fonctionnelle permet moins encore de le trancher qu'autrefois. Voici quelques arguments en faveur de la présentation récursive.

La présentation récursive permet de présenter simplement des algorithmes beaucoup plus astucieux (et donc plus efficaces) et cela a été admirablement 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.

La contribution la plus percutante dans ce débat a été celle de John Backus, l'inventeur de Fortran, qui dans de sa conférence invitée lors de la remise de son prix Turing en 1977 a pris clairement le parti de la programmation fonctionnelle, donc de la programmation récursive.

Voir aussi

Portail de l’informatique
Portail de la logique

Ce document provient de « Algorithme r%C3%A9cursif ».

Catégorie : Algorithmique

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme Récursif de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

Algorithme recursif — Algorithme récursif Les algorithmes récursifs et les fonctions récursives sont fondamentaux en informatique. Un algorithme est dit récursif s il s appelle lui même. Les premiers langages de programmation qui ont introduit la récursivité sont LISP … Wikipédia en Français
Algorithme récursif — Les algorithmes récursifs et les fonctions récursives sont fondamentaux en informatique. Un algorithme est dit récursif s il s appelle lui même. Les premiers langages de programmation qui ont introduit la récursivité sont LISP et Algol 60 et… … Wikipédia en Français
algorithme récursif — rekursyvusis algoritmas statusas T sritis automatika atitikmenys: angl. recursive algorithm vok. rekursiver Algorithmus, m rus. рекурсивный алгоритм, m pranc. algorithme récursif, m … Automatikos terminų žodynas
Algorithme De De Casteljau — L algorithme de De Casteljau est un algorithme récursif trouvé par Paul de Casteljau pour approximer efficacement les polynômes écrit dans la base de Bernstein. Cet algorithme peut être utilisé pour dessiner des courbes et des surfaces de Bézier … Wikipédia en Français
Algorithme de de Casteljau — L algorithme de De Casteljau est un algorithme récursif trouvé par Paul de Casteljau pour approximer efficacement les polynômes écrit dans la base de Bernstein. Cet algorithme peut être utilisé pour dessiner des courbes et des surfaces de Bézier … Wikipédia en Français
Algorithme de de casteljau — L algorithme de De Casteljau est un algorithme récursif trouvé par Paul de Casteljau pour approximer efficacement les polynômes écrit dans la base de Bernstein. Cet algorithme peut être utilisé pour dessiner des courbes et des surfaces de Bézier … Wikipédia en Français
Recursif — Récursif Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom … Wikipédia en Français
Algorithme De Décomposition En Produit De Facteurs Premiers — En mathématiques, dans la branche de l arithmétique modulaire, un algorithme de décomposition en produit de facteurs premiers est un algorithme (un processus pas à pas) par lequel un entier est « décomposé » en un produit de facteurs… … Wikipédia en Français
Algorithme de decomposition en produit de facteurs premiers — Algorithme de décomposition en produit de facteurs premiers En mathématiques, dans la branche de l arithmétique modulaire, un algorithme de décomposition en produit de facteurs premiers est un algorithme (un processus pas à pas) par lequel un… … Wikipédia en Français
Algorithme de factorisation en nombre premier — Algorithme de décomposition en produit de facteurs premiers En mathématiques, dans la branche de l arithmétique modulaire, un algorithme de décomposition en produit de facteurs premiers est un algorithme (un processus pas à pas) par lequel un… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Algorithme Récursif