Un article de Wikipedia.y-project.com.

Les algorithmes récursifs ou fonctions récursives sont fondamentaux en informatique et correspondent à l'idée d'une fonction qui s'appelle elle même.

Ils complètent les algorithmes dits impératifs ou itératifs qui s'exécutent de manière linéaire.

Sommaire 1 Approche intuitive 2 Prouver un algorithme récursif 2.1 Cadre 2.1.1 Théorème de terminaison 2.1.2 Théorème de correction 2.2 Remarques 3 Voir aussi

[] Approche intuitive

Prenons l'exemple de la factorielle. Celle-ci se définit intuivivement pour des entiers positifs par la fonction suivante:

<math>n! = \prod_^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 par une suite récurrente:

<math>n!=\begin 1 \mbox{ si }n=0\\ n \times fact(n-1) \mbox{ sinon} \end</math>

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

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

Tous les langages de programmation modernes proposent une implémentation de la récursivité. Nous en donnons ici un exemple en Caml:

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

Ici, on note que préciser que factorielle(0)=1 est fondamental: sans lui l'algorithme s'appelle indéfiniment. Le cas n=0 est aussi appelé cas de base, sans lui l'algorithme ne peut terminer. On peut programmer ainsi d'autres suites telles que la suite de Fibonacci ou la suite de Syracuse. Cependant il convient de noter qu'un programme itératif sera plus efficace dans ce domaine car il ne demande pas de stocker tous les résultats intermédiaires (ici le programme factorielle(n) doit garder en mémoire n calculs intermédiaires).

Mais les algorithmes récursifs ne se limitent évidemment pas au calcul de suites récurrentes et permettent de travailler sur des structures de données définies récursivement comme les arbres, ou plus généralement sur des ensembles munis d'une relation bien fondée. Le tri fusion et le problème des tours de Hanoï sont également des exemples célèbres d'application d'algorithme récursifs.

Voyons maintenant comment prouver rigoureusement qu'un algorithme récursif répond bien à un problème posé.

[] Prouver un algorithme récursif

Les théorèmes suivants permettent de prouver rigoureusement qu'une fonction récursive termine (ie qu'elle ne s'appelle pas indéfiniment) et qu'elle renvoie la bonne réponse, autrement dit de prouver l'algorithme en question. Leur structure est similaire: ils sont en fait basés sur la preuve par induction, généralisation de la preuve par récurrence. Enfin, ils sont à mettre en parallèle avec les invariants de boucle utilisés pour prouver un algorithme itératif.

[] Cadre

Soit <math>f\,</math> une fonction récursive définie sur un ensemble <math>A \,</math>.

Soit <math>E \,</math> un ensemble sur lequel est définie une relation d'ordre <math>\le</math> bien fondée, <math>\phi \,</math> une application de <math>A \,</math> dans <math>E \,</math> et enfin soit <math>B \,</math> l'ensemble des minimaux de <math>\phi (A) \,</math> (aussi appelé ensemble des cas de base).

On note, pour <math>x \in A</math> donné, <math> A_x \,</math> l'ensemble des <math>y \,</math> tels que <math>f(x) \,</math> appelle <math>f(y) \,</math>. Cet ensemble doit être fini.

[] Théorème de terminaison

Si:

• <math>\forall x \in B </math>, <math>f(x) \,</math> termine
• <math>\forall x \in A</math>, <math>\forall y \in A_x </math>, <math>\phi (x) < \phi (y) \,</math>

Alors <math>\forall x \in A</math>, <math>f(x) \,</math> termine.

[] Théorème de correction

Au cadre précédent, on ajoute une propriété <math>\mathcal _f (x)</math> que l'on veut vérifier sur <math>A \,</math>.

Si:

• <math>\forall x \in B \mbox{, } \mathcal _f (x) \,</math>
• <math>\forall x \in A ,</math>
  • <math>\forall y \in A_x\mbox{, }\phi (x) < \phi (y) \,</math>
  • <math>(\forall y \in A_x , \mathcal _f (x))\Rightarrow \mathcal _f (y)</math>

Alors <math>\forall x \in A \mbox{, } \mathcal _f (x)</math>.

[] Remarques

Ces deux théorèmes s'utilisent souvent sans avoir besoin d'une application <math>\phi \,</math>: en effet f est souvent définie sur un ensemble déjà muni d'une structure bien fondée, par exemple <math>\mathbb</math>. On peut considérer qu'alors <math>\phi = Id \,</math>.

Ces théorèmes s'appliquent naturellement sur des structures de données récursives (par exemple les arbres) où la relation d'ordre est "est construit à partir de" (pour les arbres: "est sous-arbre de").

[] Voir aussi

• Fonction récursive primitive
• Récursion terminale
• Récursivité

DernierMirror  

Réagissez

Commentez l'encyclopédie:
Attention! tous les commentaites inaproprié seront supprimés

Titre:
Video YouTube ou google:	(doit être en rapport avec le sujet)
Votre mail:	(ne sera pas affiché sur le site)
Un pseudo:
Votre site:
Commentaire	(le html n'est pas autorisé, nombre de caractère maximum = 400)
	(Comment eBabylone 1.0 beta)

Le Texte ci-dessus est disponible sous GNU Free Documentation License.
La source est wikipedia http://fr.wikipedia.org/wiki/algorithme récursif