Chapitre 3
Récursion et itération

3.1 Itération

3.1.1 Boucles

L’informatique : l’exécution de tâches répétitives, voilà une opinion couramment admise ; même si cette vision est un peu simpliste, elle contient certainement une part de vérité. Il est certain que les tâches répétitives sont celles que les machines sont les plus aptes à accomplir, tout en étant les moins gratifiantes pour l’homme.

Il arrive donc souvent qu’on écrive un programme juste pour répéter un certain nombre de fois une même tâche : calculer 500 valeurs d’une fonction pour tracer un graphe, parcourir un dictionnaire de 100 000 mots non triés pour rechercher le mot anachorète, etc.

La structure fondamentale de répétition des langages de programmation est la boucle. Nous pouvons symboliser une boucle sous la forme suivante

PICT

Une boucle possède donc une entrée, un corps qui accomplit une action, un circuit de répétition qui répète l’exécution du corps de la boucle, et une sortie.

Nous discuterons par la suite deux types de boucles

3.1.2 Boucles indexées

Il s’agit d’actions répétitives qui doivent être effectuées un nombre fini de fois, variable, mais fixé dès l’entrée dans la boucle. En général, le corps de la boucle dépend d’un entier i qui varie entre une valeur initiale iDeb et une valeur finale iFin, en augmentant de 1 à chaque nouvelle exécution de la boucle ou au contraire en diminuant de 1 à chaque exécution de la boucle.

Pour cela, la plupart des langages de programmation disposent de deux instructions du type

for i from iDeb to iFin do corps de la boucle done

lorsque l’indice i augmente de 1, et

for i from iDeb downto iFin do corps de la boucle done

lorsque l’indice i diminue de 1. Dans certain langages (comme Caml ou Pascal), le mot clé from est remplacé par une affectation (ou une liaison) du type

for i =iDeb (down)to iFin do corps de la boucle done

Dans une boucle croissante, le corps de la boucle n’est jamais exécuté lorsque iFin <iDeb ; par contre dans une boucle décroissante, le corps de la boucle n’est jamais exécuté lorsque iDeb <iFin

Les boucles indexées sont particulièrement adaptées aux objets dont la longueur est connue à l’avance comme les tableaux. Nous allons illustrer leur utilisation à travers trois exemples très simples en Caml, sans aucune exigence d’efficacité maximale : la recherche d’un élément dans un tableau, la somme des éléments d’un tableau d’entiers et la multiplication des polynômes.

Recherche dans un tableau

Commençons par la recherche d’un élément dans un tableau donné. Nous allons tout simplement parcourir toute la longueur du tableau en maintenant un indicateur qui nous dit si l’élément en question a été trouvé. L’indicateur en question sera une référence sur un booléen. Avant le début de l’exécution de la boucle, l’élément n’a pas encore été trouvé, donc la référence est initialisée à false. Ensuite, cette référence est actualisée au fur et à mesure du parcours du tableau ; cette actualisation n’a pas lieu d’être si l’élément a déjà été trouvé précédemment (d’où le test if not !trouve then). A la fin, la valeur de la référence est renvoyée comme valeur de la fonction1.


#let cherche tableau x =  
     let trouve = ref false and n = vect_length tableau in  
       begin  
         for i = 0 to n-1 do  
            if not !trouve then trouve := (x = tableau.(i))  
         done;  
         !trouve  
       end;;  
cherche : ’a vect -> ’a -> bool = <fun>  
#cherche [| 1;3;8;98;54;65;58;47 |]  7;;  
- : bool = false  
#cherche [| 1;3;8;98;54;65;58;47 |]  54;;  
- : bool = true


Programme 3.1: recherche linéaire dans un tableau

L’erreur à ne pas faire est d’actualiser systématiquement la valeur de la référence sous la forme


#let mauvais_cherche tableau x =  
     let trouve = ref false and n = vect_length tableau in  
       begin  
         for i = 0 to n-1 do  
            trouve := (x = tableau.(i))  
         done;  
         !trouve  
       end;;  
mauvais_cherche : ’a vect -> ’a -> bool = <fun>  
#mauvais_cherche [| 1;3;8;98;54;65;58;47 |]  54;;  
- : bool = false


Programme 3.2: recherche erronée

Cette procédure ne teste en effet réellement que le dernier élément du tableau, puisque tous les résultats précédents sont perdus au fur et à mesure. Si l’on cherche à démontrer la validité de la boucle, on détecte facilement ce type d’erreur. Les deux boucles (la bonne et la mauvaise) ont la même condition d’entrée (la précondition) : l’indicateur est à false. Elles ont la même condition de sortie (la postcondition) : tout le tableau a été parcouru et (théoriquement) l’indicateur indique si l’élément figure dans le tableau. Recherchons donc un invariant de la boucle, c’est à dire un prédicat qui ne change pas au cours de la boucle.

Dans la boucle correcte, nous pouvons associer à chaque i ∈{0,,n - 1} le prédicat P(i) défini par

P(i) : à l’entrée dans la i-ième exécution du corps de la boucle (nous parlerons plutôt de la i-ième itération) la valeur pointée par trouve indique si l’élément x figure dans tableau[0],,tableau[i - 1]

Il est clair que P(0) est vrai. Supposons maintenant que P(i) est vrai ; deux cas sont alors possibles :

Dans tous les cas, à la fin de l’itération, la valeur pointée par la référence trouve indique si l’élément x figure dans tableau[0],,tableau[i]. A ce moment là, i est augmenté de 1 et à l’exécution suivante (ou après la sortie) P(i + 1) est vrai. Par une récurrence évidente, P(i) est vrai pour tout i. A la sortie, i vaut n (car il a été augmenté de 1) et donc P(n) est vrai ; autrement dit la valeur pointée par la référence trouve indique si l’élément x figure dans tableau[0],,tableau[n - 1], ce que l’on voulait.

Par contre, dans la boucle incorrecte, P(i) n’est plus invariant dans l’exécution de la boucle puisque toute l’information précédente est perdue.

Somme des éléments d’un tableau

Suivant le même principe que pour la recherche d’un élément dans un tableau, pour faire la somme des éléments d’un tableau d’entiers, il suffit d’initialiser une référence à 0 puis d’y ajouter au fur et à mesure les éléments du tableau. On obtient


#let somme tableau =  
   let s = ref 0 in  
     for i = 0 to (vect_length tableau) -1 do  
         s := !s+tableau.(i)  
     done;  
     !s;;  
somme : int vect -> int = <fun>  
#somme [| 1; 2; 3; 4 |];;  
- : int = 10


Programme 3.3: somme des nombres d’un tableau

La preuve de la correction est claire : la précondition est que somme vaut 0 ; l’invariant de boucle est

P(i) : à l’entrée dans l’itération d’indice i, somme contient k=0i-1tableau[k]

la postcondition est : somme contient k=0n-1tableau[k], c’est à dire la somme de tous les éléments du tableau.

Multiplication des polynômes

Pour simplifier, nous travaillerons avec des polynômes à coefficients entiers. Si P(X) = i=0naiXi ∈ Z[X], nous stockerons les coefficients dans un tableau de taille n + 1, la valeur de ai étant stockée dans l’élément de numéro i du tableau. Pour des raisons de commodité, nous définirons une fonction qui renvoie le degré d’un polynôme (égal à la longueur du tableau diminué de 1) et une autre fonction qui initialise un polynôme P(X) = i=0naiXi avec tous les ai égaux à 0. Pour cela nous utiliserons les deux fonctions prédéfinies de Caml : la fonction vect_length qui renvoie la longueur d’un tableau et la fonction make_vect qui renvoie un tableau de longueur donné avec tous les éléments initialisés à une valeur donnée


#let deg p = (vect_length p)-1;;  
deg : ’a vect -> int = <fun>  
#let init_poly n = make_vect (n+1) 0;;  
init_poly : int -> int vect = <fun>


Programme 3.4: initialisation de polynôme

En ce qui concerne le produit de deux polynômes nous utiliserons le schéma de calcul suivant

           (       )       (           )
( m∑      )  ∑n          m∑   ∑n
     aiXi   (   bjXj)  =    (   aibjXi+j)
  i=0        j=0         i=0  j=0

qui est le plus facile à programmer. Il suffit donc de faire parcourir à i l’intervalle [0,m], puis de faire parcourir à j l’intervalle [0,n] en ajoutant le produit aibj au terme de degré i + j du polynôme produit. Ce polynôme produit aura été préalablement initialisé à 0.


#let mult_poly p q =  
     let m = deg p and n = deg q in  
     let prod = init_poly (m+n) in  
             for i = 0 to m do  
               for j = 0 to n do  
                  prod.(i+j)<-prod.(i+j)+p.(i)*q.(j)  
               done  
             done;  
             prod;;  
 
#mult_poly [| 1;2;3;4 |] [| 1;2;1 |];;  
- : int vect = [|1; 4; 8; 12; 11; 4|]


Programme 3.5: multiplication de polynômes

A titre d’application, on peut construire ainsi, en élevant le polynôme 1 + X à la puissance n, la famille des coefficients du binôme Cnk pour 0 k n ; pour cela il suffit de stocker dans une référence sur un polynôme les puissances successives de 1 + X en effectuant au fur et à mesure les multiplications par 1 + X.


#let binome n =  
       let p = [| 1;1 |] and puiss = ref [| 1; 1|] in  
         for i = 2 to n do  
            puiss := mult_poly p !puiss  
         done;  
         puiss;;  
binome : int -> int vect ref = <fun>  
#binome 3;;  
- : int vect ref = ref [|1; 3; 3; 1|]  
#binome 6;;  
- : int vect ref = ref [|1; 6; 15; 20; 15; 6; 1|]  
#binome 10;;  
- : int vect ref = ref [|1; 10; 45;  
           120; 210; 252; 210; 120; 45; 10; 1|]


Programme 3.6: coefficients du binôme

3.1.3 Boucles conditionnelles

La technique que nous avons utilisée pour rechercher la présence d’un élément dans un tableau est très inefficace puisqu’elle parcourt systématiquement tout le tableau, même si l’élément a été trouvé dès la première exécution de la boucle. Il semble beaucoup plus judicieux de parcourir le tableau, mais de s’arrêter dès que l’élément recherché a été trouvé (à condition qu’il y figure). On tombe sur un cas typique de boucle conditionnelle où la sortie (éventuelle) de la boucle s’effectue après un nombre d’exécutions non prédéterminé et dépend en fait de l’exécution même du corps de la boucle.

On distingue en général quatre types de boucles conditionnelles que l’on peut résumer de la façon suivante

Les boucles tant que et les boucles jusqu’à ce que sont équivalentes ; en effet l’instruction tant que condition est vraie signifie

alors que l’instruction jusqu’à ce que condition soit vraie signifie

On voit donc que l’instruction tant que condition est vraie est équivalente à jusqu’à ce que (non condition) soit vraie, où non condition désigne la négation de la valeur de condition. Comme tous les langages de programmation disposent d’un opérateur de négation, il leur suffit d’implémenter les boucles tant que ou les boucles jusqu’à ce que.

Il ne nous reste donc qu’à examiner par exemple les deux types de boucles

La différence entre ces deux boucles concerne le moment où le test de condition est effectué. Dans une boucle faire tant que le test est effectué après l’exécution du corps de la boucle, alors que dans une boucle tant que faire le test est effectué avant l’exécution du corps de la boucle. La différence peut sembler minime puisqu’en général, la fin de l’exécution du corps de la boucle n’est autre que le début de l’exécution suivante du corps de la boucle ; c’est presque vrai, sauf qu’échappent à cette règle la première itération ainsi que la dernière. Dans une boucle faire tant que , le test suit l’exécution du corps et donc celui-ci est exécuté au moins une fois, la première. Par contre, dans une boucle tant que faire , le test précédant l’exécution de la boucle, celle-ci n’est jamais exécutée si au départ la condition n’est pas vérifiée.

Pour résumer sur un graphique, on a les deux types de boucles

PICT PICT

La plupart des langages possèdent une structure de boucle avec test initial (en général indispensable pour éviter des incohérences graves comme des vecteurs à 0 éléments). Par contre tous ne disposent pas d’une structure de boucle avec test final (en particulier Caml). Celle-ci est fort heureusement facile à simuler à l’aide d’une boucle avec test initial en introduisant une variable booléenne provisoire test (dont on suppose qu’elle n’intervient ni dans le corps de la boucle, ni dans la condition). La variable test est mise à la valeur true avant l’entrée dans la boucle et c’est cette variable qui sert ensuite de test de boucle. A la fin du corps de la boucle on écrit simplement test := condition. Ceci conduit en pseudo-langage à une structure du type :


   test := true;  
   tant_que test faire  
       corps_de_la_boucle;  
       test := condition  
   fait


Programme 3.7: simulation de boucle avec test final

et en Caml à :


   let test = ref true in  
   while test do  
       corps_de_la_boucle;  
       test := condition  
   done


Programme 3.8: simulation de boucle avec test final

Recherche dans un tableau

Revenons à notre problème de recherche d’un élément dans un tableau en parcourant les éléments du tableau à partir du premier. En utilisant une boucle conditionnelle avec test final, il est possible de stopper la recherche dès que l’élément recherché a été trouvé. Encore faut-il ne pas sortir du tableau et savoir si la sortie de la boucle a été provoquée par le fait que l’élément a été trouvé ou par le fait que le tableau a été épuisé (auquel cas l’élément ne figurait pas dans la tableau). Le corps de la boucle doit tester si l’élément a été trouvé, mais aussi actualiser la valeur du compteur. Quant au test, il doit à la fois vérifier que l’élément n’a pas été trouvé lors de l’exécution précédente du corps de la boucle, mais aussi que l’on ne sort pas des limites du tableau (dans ce dernier cas c’est que l’élément n’a pas été trouvé). Ces considérations conduisent à un premier jet


#let cherche tableau x =  
     let non_trouve = ref true and i = ref 0 in  
         while !non_trouve & !i<vect_length tableau do  
           non_trouve := (tableau.(!i)<>x);  
           i := !i + 1  
         done;  
      not !non_trouve;;  
cherche : ’a vect -> ’a -> bool = <fun>  
#cherche [| 1 ; 3; 5; 8|] 4;;  
- : bool = false  
#cherche [| 1 ; 3; 5; 8|] 8;;  
- : bool = true


Programme 3.9: recherche linéaire dans un tableau

En fait on s’aperçoit qu’à chaque fois que le test est effectué, on recalcule la longueur du tableau et qu’il vaut donc mieux la stocker une bonne fois pour toutes grâce à un nouvel identificateur n et on aboutit à une forme raisonnable :


#let cherche tableau x =  
     let non_trouve = ref true and i = ref 0 and n = vect_length tableau in  
         while !non_trouve & !i<n do  
           non_trouve := (tableau.(!i)<>x);  
           i := !i + 1  
         done;  
      not !non_trouve;;  
cherche : ’a vect -> ’a -> bool = <fun>  
#cherche [| 1 ; 3; 5; 8|] 4;;  
- : bool = false  
#cherche [| 1 ; 3; 5; 8|] 8;;  
- : bool = true


Programme 3.10: recherche linéaire dans un tableau

Pour démontrer que ce programme fournit bien le résultat voulu, il nous faut donner les préconditions, postconditions et invariant de la boucle. Les préconditions sont claires : non_trouve vaut true (l’élément est ”non trouvé”), i = 0 et n est la longueur du tableau. La postcondition est que la variable non_trouve vaut true si l’élément n’a pas été trouvé, false sinon. Quant à l’invariant de boucle, on peut par exemple prendre le prédicat

non_trouve indique si l’élément x ne figure pas dans tableau[0],,tableau[i - 1]

Avant l’exécution de la boucle, i a la valeur 0 et x n’appartenant pas à l’ensemble vide, ce prédicat est vrai. Supposons maintenant que ce prédicat est vrai à l’entrée dans le corps de la boucle ; comme ce corps est exécuté, c’est que non_trouve vaut false et i < n ; le corps de la boucle teste alors si tableau[i] est égal à x puis augmente i de 1 ; donc à la fin de l’itération non_trouve indique de nouveau si l’élément x ne figure pas dans tableau[0],, tableau[i - 1]. Lorsque se produit une sortie de la boucle, ce peut être pour deux raisons

Dans ces deux cas, non_trouve contient la valeur du prédicat x ne figure pas dans tableau et il faut donc renvoyer la valeur contraire.

3.2 Le principe de récurrence

3.2.1 Les axiomes de Peano

On montre en théorie des ensembles qu’il existe un ensemble ordonné (N,) vérifiant les propriétés suivantes

et que cet ensemble ordonné est unique à une bijection croissante près (isomorphisme d’ensemble ordonné). Considérons un tel ensemble dont nous allons voir un certain nombre de propriétés

Proposition 3.2.1 L’ensemble (N,) est totalement ordonné.

Démonstration: Si a,b ∈ N, la partie {a,b} doit avoir un plus petit élément, et donc on a soit a b, soit b a.

Proposition 3.2.2 L’ensemble (N,) a un plus petit élément noté 0.

Démonstration: Comme toute partie de N, N lui même a un plus petit élément.

Proposition 3.2.3 Tout élément a de N a un unique successeur, c’est à dire un élément b de N tel que b > a et l’intervalle ouvert ]a,b[ est vide.

Démonstration: Comme a n’est pas plus grand élément de N, il existe des éléments x de N tels que a < x. Soit donc X = {x ∈ N | x > a} ; X est une partie non vide de N, donc elle a un plus petit élément b. Si ]a,b[ n’était pas vide, il existerait un élément x dans ]a,b[ qui vérifierait à la fois x > a, donc x ∈ X et x < b = min X ce qui est absurde. L’unicité résulte bien évidemment de l’unicité du plus petit élément.

Proposition 3.2.4 Tout élément a de N différent de 0 a un unique prédécesseur, c’est à dire un élément b de N tel que b < a et l’intervalle ouvert ]b,a[ est vide.

Démonstration: Comme a n’est pas le plus petit élément de N, il existe des éléments x de N tels que x < a. Soit donc X = {x ∈ N | x < a} ; X est une partie non vide de N, majorée par a, donc elle a un plus grand élément b. Si ]b,a[ n’était pas vide, il existerait un élément x dans ]a,b[ qui vérifierait à la fois x < a, donc x ∈ X et x > b = maxX ce qui est absurde. L’unicité résulte bien évidemment de l’unicité du plus grand élément.

Remarque  Nous noterons n + 1 le successeur de n et n - 1 le prédécesseur de n (si n > 0). La définition même du prédécesseur et du successeur montre que

 ∀n ∈ N, (n + 1)- 1  = n                      (3.1)
∀n ∈ N*, (n - 1)+ 1  = n                      (3.2)

3.2.2 Principe de récurrence simple

Définition 3.2.1 Soit E un ensemble ; on appelle prédicat sur E toute propriété P(x) dépendant de x ∈ E et dont on peut dire pour tout x ∈ E si elle est vraie ou fausse, autrement dit une application P de E dans l’ensemble à deux éléments {vrai,faux}.

Dans la pratique, si P est un tel prédicat, on écrira souvent P(x) à la place de P(x) = vrai.

Théorème 3.2.1 (Principe de récurrence simple) Soit P un prédicat sur N. On suppose que

Alors, pour tout n ∈ N, P(n) est vrai.

Démonstration: Soit X l’ensemble des n ∈ N tel que P(n) soit fausse. Si X est non vide, il a un plus petit élément a ∈ X. Comme P(0) est vraie, on a a0. Donc a a un prédécesseur a - 1. Comme a - 1 < a = min X, on a a - 1∕∈X, donc P(a - 1) est vraie. Mais a = (a - 1) + 1 et comme P(a - 1) est vraie, P(a) = P((a - 1)+ 1) est vraie, ce qui contredit a ∈ X. Donc X est vide, et donc pour tout n ∈ N, P(n) est vrai.

Remarque  De la même façon on montre que, pour n0 ∈ N, si

alors, pour tout n n0, P(n) est vrai.

Exemple  On montre ainsi que n ∈ N, 02 + 12 + + n2 = n(n+ 1)(2n+ 1)∕6. Soit Sn = 02 + 12 + + n2 et soit P(n) le prédicat

Sn = n(n+-1)(2n-+1)
           6

Alors P(0) est vrai et si P(n) est vrai, alors

Sn+1 =   Sn+ (n+ 1)2 = n(n-+-1)(2n+-1)+ (n+ 1)2
                            6
     =   n+-1-(n(2n+ 1)+ 6(n + 1))= n-+-1(2n2 +7n +6)
         (n6+ 1)(n +2)(2n + 3)        6
     =   --------6---------
donc P(n + 1) est vrai. Ceci montre que P(n) est vrai pour tout n ∈ N.

3.2.3 Principe de récurrence étendu

Théorème 3.2.2 (Principe de récurrence étendu) Soit P un prédicat sur N. On suppose que

Alors, pour tout n ∈ N, P(n) est vrai.

Démonstration: Soit X l’ensemble des n ∈ N tel que P(n) soit faux. Si X est non vide, il a un plus petit élément a ∈ X. Comme P(0) est vrai, on a a0. Pour tout k < a, on a k∕∈X, donc P(k) est vrai. On en déduit que P(a) est vrai, ce qui contredit a ∈ X. Donc X est vide, et donc pour tout n ∈ N, P(n) est vrai2.

Exemple  On peut ainsi montrer que tout nombre entier supérieur ou égal à 2 est produit de nombres premiers. C’est clair si n = 2. Si maintenant la propriété est vraie pour tous les nombres 2,,n- 1 alors deux cas sont possibles. Soit n est premier et alors il est produit d’un nombre premier. Soit n n’est pas premier et il est produit de deux nombres entiers p et q avec 2 p n - 1 et 2 q n- 1 ; d’après l’hypothèse de récurrence, p et q sont produits de nombres premiers et donc n aussi, ce qui achève la récurrence.

3.2.4 Ensembles bien ordonnés, bien fondés

Le principe de récurrence simple est très intimement lié à la structure de l’ensemble des entiers naturels et à l’existence des fonctions réciproques prédécesseur et successeur. Par contre, le principe de récurrence étendu se généralise facilement à d’autres ensembles ordonnés. La propriété essentielle de l’ensemble N que nous avons utilisée pour la démonstration de ce principe est le fait qu’une partie non vide a un plus petit élément. Cette propriété s’étend à d’autres ensembles ordonnés.

Définition 3.2.2 On dit qu’un ensemble ordonné (E,) est bien ordonné si toute partie non vide a un plus petit élément.

Remarque  Dans un ensemble bien ordonné, une partie à deux éléments doit nécessairement avoir un plus petit élément, ce qui montre que l’ordre est total. Par contre, il existe des ensembles totalement ordonnés qui ne sont pas bien ordonnés, comme par exemple l’ensemble Z des entiers relatifs et l’ensemble R des nombres réels (munis de leurs ordres naturels).

Exemple  Sur N2 = N × N, on pose

              (                      )
(n,p)≼ (n′,p′) si n < n′ ou (n = n′ et p≤ p′)

Soit A une partie non vide de N2. Alors A a un plus petit élément (n 0,p0), où n0 = min{n |∃p ∈ N, (n,p) ∈ A} et p0 = min{p | (n0,p) ∈ A}. L’ordre en question sur N2 est un bon ordre appelé l’ordre lexicographique ; il sera largement utilisé par la suite.

Théorème 3.2.3 (Principe d’induction) Soit P un prédicat sur l’ensemble bien ordonné (E,). On suppose que

Alors, pour tout x ∈ E, P(x) est vrai.

Démonstration: Exactement la même que pour le principe de récurrence étendu.

En fait, il est possible de généraliser encore ce principe à l’aide de la notion d’ordre bien fondé qui généralise celle de bon ordre.

Définition 3.2.3 On dit qu’un ordre sur E est bien fondé si toute partie non vide a un élément minimal.

Exemple  Sur l’ensemble N* des entiers naturels non nuls la relation x y si x divise y est un ordre bien fondé : tout plus petit élément d’une partie au sens de l’ordre ordinaire est un élément minimal pour la relation de divisibilité. Les éléments minimaux de N \{0, 1} sont les nombres premiers.

La proposition suivante est intéressante en programmation car elle constitue en général un argument décisif pour montrer qu’une boucle se termine.

Proposition 3.2.5 L’ordre sur E est bien fondé si et seulement si il n’existe pas de suite strictement décroissante d’éléments de E.

Démonstration: Supposons tout d’abord qu’il existe dans E une suite (an)n∈N strictement décroissante et soit A = {an | n ∈ N} ; tout élément de A est de la forme ap avec ap+1 ap, donc A n’admet pas d’élément minimal. Inversement, supposons qu’il existe une partie non vide A n’admettant pas d’élément minimal et soit a0 ∈ A. L’élément a0 n’est pas minimal dans A et donc il existe a1 ∈ A tel que a1 a0. Supposons a0,,an construits tels que an an-1 a0. Puisque an n’est pas élément minimal de A, il existe an+1 ∈ A tel que an+1 an. On construit ainsi par récurrence une suite strictement décroissante d’éléments de A. On a donc montré l’équivalence entre l’ordre n’est pas bien fondé et il existe une suite strictement décroissante d’éléments de E, ce qui est le résultat cherché.

On a alors

Théorème 3.2.4 (Principe d’induction généralisé) Soit P un prédicat sur l’ensemble ordonné (E,), où est un ordre bien fondé. On suppose que

Alors, pour tout x ∈ E, P(x) est vrai.

Démonstration: Soit X l’ensemble des x ∈ E tel que P(x) soit faux. Si X est non vide, il a un élément minimal a ∈ X. Comme P(x) est vrai pour les éléments minimaux de E, a n’est pas un élément minimal de E. Pour tout x a, on a x∕∈X, donc P(x) est vrai. On en déduit que P(a) est vrai, ce qui contredit a ∈ X. Donc X est vide, et pour tout x ∈ E, P(x) est vrai.

3.3 Récursivité

3.3.1 Procédures et fonctions récursives simples

Nous allons tout d’abord étudier le cas de la récursivité simple indexée par N. Supposons que nous ayons un problème à résoudre dépendant d’un entier n et considérons le prédicat (un peu informel)

P(n) : je sais résoudre le problème pour n

Le principe de récurrence simple nous dit que si nous savons résoudre le problème pour n = 0 et si nous savons comment passer d’une solution pour n à une solution pour n + 1, autrement dit si

alors pour tout n ∈ N, P(n) est vrai ; nous savons donc résoudre notre problème pour tout n ∈ N. Nous allons traiter quelques exemples de cette démarche dans la suite de ce paragraphe.

Calcul des puissances La définition même de la puissance n-ième en mathématiques est récursive, puisque l’on pose a0 = 1 (on sait calculer la puissance n-ième pour n = 0) et an+1 = aan (si on sait calculer la puissance n-ième, on sait calculer la puissance n + 1-ième). Nous pouvons donc essayer de définir une fonction puissance en Caml de la façon suivante :


#let puiss x n = if n = 0 then 1 else x * (puiss x (n-1));;  
> Toplevel input:  
>let puiss x n = if n = 0 then 1 else x * (puiss x (n-1));;  
>                                          ^^^^^  
> Variable puiss is unbound.


Programme 3.11: calcul erroné des puissances

Nous voyons que Caml provoque une erreur, qui en fait à bien y réfléchir est tout à fait compréhensible. Rappelons nous en effet que lors de l’évaluation de l’expression let qui aboutira à la liaison du symbole puiss avec la fonction Caml (x,n)↦→puiss(x,n), l’interpréteur Caml commence par évaluer l’expression qui est à droite du symbole = ; or cette expression contient le symbole puiss qui à cet instant n’est pas encore défini, puisqu’on est précisément en train de le définir.

Heureusement, il y a un moyen simple de sortir de ce cercle vicieux. On utilise à cet effet une version étendue de l’instruction let, la construction let rec (un soit récursif ). Lorsque Caml rencontre une telle instruction, lors de l’évaluation de l’expression qui se trouve à droite du signe = il fait comme si la liaison qui se trouve à gauche du signe = était déjà effectuée, autrement dit comme si le symbole puiss était déjà défini. Dans cas, il n’y a pas de problème et on obtient :


#let rec puiss x n = if n = 0 then 1 else x * (puiss x (n-1));;  
puiss : int -> int -> int = <fun>  
#puiss 2 12;;  
- : int = 4096  
#puiss 2 18;;  
- : int = 262144


Programme 3.12: calcul récursif des puissances

Cette construction let rec récursive s’étend bien entendu à la construction locale let rec ... in ; de la même façon, Caml 0.7 dispose d’une construction where rec.

Calcul de la factorielle La définition même de la factorielle de n en mathématiques est récursive, puisque l’on pose 0! = 1 (on sait calculer la factorielle de 0) et (n + 1)! = (n + 1)n! (si on sait calculer la factorielle de n, on sait calculer la factorielle de n + 1). On posera donc :


#let rec fact n = if n = 0 then 1 else n* fact (n-1);;  
                  fact : int -> int = <fun>  
#fact 10;;  
- : int = 3628800


Programme 3.13: calcul récursif de la factorielle

Un moyen encore plus élégant et plus lisible de présenter cette fonction est d’utiliser une reconnaissance de motif à la place de l’instruction conditionnelle en posant :


#let rec fact = function  
            0 -> 1  
         |  n -> n*fact(n-1);;  
fact : int -> int = <fun>  
#fact 10;;  
- : int = 3628800


Programme 3.14: calcul récursif de la factorielle avec motifs

Un bon moyen d’observer ce qui se passe, est de demander à Caml de tracer (au sens de suivre à la trace) la fonction fact. Cela se fait très simplement en évaluant l’expression Caml trace "nom_de_fonction", soit ici trace "fact". A partir de là, chaque fois que la fonction Caml fact est appelée, Caml affiche les valeurs des paramètres qu’elle reçoit en entrée sous la forme fact <--, et chaque fois qu’elle retourne un résultat, est affichée la valeur de ce résultat sous la forme fact -->. Voici un exemple


#trace "fact";;  
>> fact is now traced.  
- : unit = ()  
#fact 3;;  
fact <-- 3  
fact <-- 2  
fact <-- 1  
fact <-- 0  
fact --> 1  
fact --> 1  
fact --> 2  
fact --> 6  
- : int = 6


Programme 3.15: trace d’une fonction récursive

On voit que fact reçoit en entrée le paramètre 3, puis qu’elle est de nouveau appelée avec en entrée le paramètre 2, puis qu’elle est de nouveau appelée avec en entrée le paramètre 1, puis qu’elle est de nouveau appelée avec en entrée le paramètre 0 ; à ce moment là, la fonction fact retourne comme valeur 0! = 1, puis l’appel précédent renvoie 1 * 0! = 1, puis l’appel précédent renvoie 2 * 1! = 2 et enfin le premier appel effectué renvoie 3 * 2! = 6, ce qui achève le calcul.

Miroir d’un mot Prenons maintenant le problème de l’image miroir d’un mot, l’image du mot abcdef devant être fedcba. Le retournement d’un mot d’un seul caractère est trivial : il suffit de ne rien faire. Pour retourner un mot à n caractères, il suffit de retourner le mot formé par les n - 1 premiers caractères et de le concaténer avec le dernier caractère mis en première position. En utilisant les fonctions suivantes de la bibliothèque Caml de base

on obtient une version possible (dont l’efficacité sera discutée plus loin)


#let rec retourne s =  
      let n = string_length s in  
      if n = 1 then s  
             else  
               (sub_string s (n-1) 1) ^ retourne (sub_string s 0 (n-1));;  
retourne : string -> string = <fun>  
#retourne "abcdefghijkl";;  
- : string = "lkjihgfedcba"


Programme 3.16: miroir récursif d’un tableau

Les tours de Hanoi Il s’agit d’un exemple classique qui montre la puissance de la récursivité (même simple) pour résoudre un problème. Une ancienne légende raconterait (d’après certains informaticiens) que des moines de Hanoi se livrent depuis la nuit des temps à une curieuse occupation. Dans la cour de leur temple se trouvent trois piquets, les fameuses tours. Ces moines disposent de disques en or de diamètres décroissants percés en leurs centres de manière à pouvoir les enfiler sur les piquets. La règle à respecter est que le diamètre d’un disque placé au dessus doit toujours être plus petit que le diamètre du disque placé en dessous.

A l’origine du jeu, tous les disques étaient empilés sur le piquet de gauche (le plus à l’ouest). Les moines ne peuvent déplacer qu’un disque à la fois de l’un des piquets vers l’un des deux autres piquets, à condition de toujours respecter la règle de décroissance des diamètres. Le but que poursuivent les moines est de transférer tous les disques sur le piquet de droite (le plus à l’est) : la légende assure que cela sonnera la fin de notre monde.

PICT

Le problème semble difficilement résoluble. Pourtant une solution récursive est immédiate. Appelons n le nombre de disques à transférer. Si n = 1, la solution est triviale, il suffit de transférer le seul et unique disque. Supposons que nous sachions transférer n- 1 disques et que nous voulions en transférer n d’un piquet a vers le piquet c en utilisant comme piquet intermédiaire b. Il nous suffit de transférer les n - 1 disques supérieurs du piquet a vers le piquet b (le disque inférieur étant le plus grand de tous et ne bougeant pas, il n’impose aucune contrainte aux mouvements des autres et tout se déroule comme s’il n’existait pas), puis de transférer le dernier disque de a vers c (qui est libre) et enfin de transférer les n - 1 disques de b vers c en utilisant comme piquet intermédiaire a : de nouveau le plus grand des disques ne bouge pas et donc n’impose aucune contrainte aux mouvements des autres. Autrement dit, si on appelle transfert n a b c le transfert de n disques du piquet a vers le piquet c en utilisant l’intermédiaire b, on peut le réaliser par

En Caml, nous appellerons les piquets gauche, milieu et droite et le transfert du disque supérieur du piquet a vers le piquet c sera noté a-->c. On obtient alors la procédure suivante :


#let rec hanoi n a b c =  
   if n = 1 then  
       begin  
         print_string (a ^ " --> "^ c);  
         print_newline()  
       end  
    else  
      begin  
        hanoi (n-1) a c b;  
        hanoi 1 a b c;  
        hanoi (n-1) b a c  
    end;;  
hanoi : int -> string -> string -> string -> unit = <fun>  
#hanoi 1 "gauche" "milieu" "droite";;  
gauche --> droite  
- : unit = ()  
#hanoi 2 "gauche" "milieu" "droite";;  
gauche --> milieu  
gauche --> droite  
milieu --> droite  
- : unit = ()  
#hanoi 3 "gauche" "milieu" "droite";;  
gauche --> droite  
gauche --> milieu  
droite --> milieu  
gauche --> droite  
milieu --> gauche  
milieu --> droite  
gauche --> droite  
- : unit = ()


Programme 3.17: tours de Hanoi

La méthodologie récursive nous a permis de résoudre très simplement un problème d’apparence bien complexe. Faisons une petite étude du temps nécessaire à l’exécution de cet algorithme récursif. Si nous notons an le nombre d’opérations de transfert d’un disque d’un piquet à un autre, la suite an est définie par récurrence par a1 = 1 et an = 2an-1 + 1. Le lecteur vérifiera immédiatement que l’unique solution de cette récurrence est an = 2n - 1. Dans la légende originale, il y avait 64 disques à transférer. Un petit calcul rapide montrera que même en déplaçant un disque par seconde (ce qui est quand même un bon rythme pour un moine), la fin du monde ne devrait pas intervenir avant quelques centaines de milliards d’années : on obtient comme temps nécessaire quelques 18446744073709551615 secondes, soit environ 6 1011 années. Ceci laisse du temps devant nous. On peut en effet montrer qu’il n’existe pas de solution plus efficace (en nombre d’opérations) que celle que nous avons donnée.

3.3.2 Procédures et fonctions récursives multiples

Pour le moment nous ne nous sommes intéressés qu’à des récursivités simples, où l’on passe d’une solution pour n à une solution pour n + 1. On rencontre fréquemment des types de problèmes dépendant d’un entier n pour lesquels la solution pour n dépend de la solution du même problème pour plusieurs entiers strictement inférieurs à n, ce que nous appellerons une récursivité multiple.

Un exemple classique est celui de la suite de Fibonacci (Fn)n∈N définie par F0 = F1 = 1 et n 2, Fn = Fn-1 + Fn-2. Ces récurrences multiples peuvent se résoudre de la même façon que les récurrences simples. C’est ainsi que l’on peut définir en Caml :


#let rec fibo = function  
             0 -> 1  
          |  1 -> 1  
          |  n -> (fibo (n-1))+(fibo (n-2));;  
fibo : int -> int = <fun>  
#fibo 4;;  
- : int = 5  
#fibo 10;;  
- : int = 89


Programme 3.18: récursivité double

Faisons une étude du temps de calcul de Fn pour un n donné ; ce temps de calcul est en gros proportionnel au nombre d’appels Tn de la fonction fibo. Or il est clair que T0 = 1, T1 = 1 et que Tn = Tn-1 + Tn-2 pour n 2 si bien que Tn = Fn. Mais il est facile de montrer par récurrence que

        (                            )
      1   ( 1+ √5 )n+1   (1 - √5)n+1
Fn = √--(   ------     -  ------     )
       5      2              2

si bien que Fn est équivalent, quand n tend vers + à   √ -
1∕  5ωn+1 avec ω =     √-
1 +  5∕2 1.6. A titre d’exemples, à supposer que notre ordinateur soit capable d’effectuer 106 appels de la fonction fibo par seconde, le calcul de F64 par cette méthode demanderait environ 200 jours, quant au calcul de F100 il demanderait environ 18 millions d’années3 !

Il faut dire que notre méthode est plutôt inefficace. Pour le constater, il suffit de tracer notre fonction fibo.


#trace "fibo";;  
>> fibo is now traced.  
- : unit = ()  
#fibo 4;;  
fibo <-- 4  
fibo <-- 2  
fibo <-- 0  
fibo --> 1  
fibo <-- 1  
fibo --> 1  
fibo --> 2  
fibo <-- 3  
fibo <-- 1  
fibo --> 1  
fibo <-- 2  
fibo <-- 0  
fibo --> 1  
fibo <-- 1  
fibo --> 1  
fibo --> 2  
fibo --> 3  
fibo --> 5  
- : int = 5


Programme 3.19: trace d’une récursivité multiple

On voit que F3 a été calculé 1 fois, F2 a été calculé 2 fois, F1 a été calculé 3 fois et F0 a été calculé 2 fois. Il est facile de modifier notre procédure pour qu’elle affiche en plus le nombre de fois où elle a été appelée avec un certain paramètre. Pour cela nous utiliserons un tableau initialisé à 0 et nous incrémenterons le i-ième élément de ce tableau chaque fois que la procédure sera appelée avec le paramètre i. On obtient une nouvelle fonction essai_fibo qui commence par initialiser le tableau dans lequel est stocké le nombre des appels puis définit la fonction récursive fibo qui calcule effectivement Fn en mettant à jour au fur et à mesure le tableau nb_appels ; ensuite essai_fibo appelle effectivement la fonction fibo avec le paramètre n et retourne le tableau des nombres d’appels.


#let essai_fibo n =  
       let nb_appels = make_vect (n+1) 0 in  
       let rec fibo = function  
             0 -> begin  
                    nb_appels.(0) <- nb_appels.(0)+1;  
                    1  
                  end  
          |  1 -> begin  
                    nb_appels.(1) <- nb_appels.(1)+1;  
                    1  
                 end  
          |  n -> begin  
                  nb_appels.(n) <- nb_appels.(n)+1;  
                  (fibo (n-1)) + (fibo (n-2))  
                 end  
        in fibo n;  
        nb_appels;;  
essai_fibo : int -> int vect = <fun>  
#essai_fibo 14;;  
- : int vect = [|233; 377; 233; 144; 89; 55; 34; 21; 13; 8; 5; 3; 2; 1; 1|]


Programme 3.20: recalculs dans une récursivité multiple

On constate ainsi que F2 a été calculé 233 fois lors du calcul de F14.

Note de programmation  On a ici une méthode habituelle de programmation Caml qui consiste à utiliser une définition de fonction récursive (ici fibo) à l’intérieur d’une autre fonction (ici essai_fibo). Le seul but de la fonction extérieure essai_fibo est de créer un environnement adéquat au déroulement de la fonction récursive : elle crée le tableau en l’initialisant, elle crée la fonction récursive, puis elle appelle la fonction récursive, et enfin elle retourne le résultat intéressant (qui ici, par exception, n’est pas le résultat de la fonction récursive).

On aurait pu bien entendu utiliser un tableau global pour stocker le nombre d’appels (car il n’est pas question d’en faire une variable locale à la fonction fibo qui serait recréée à chaque appel de la fonction). Cela aurait pourtant de nombreux inconvénients :

La principale source d’inefficacité de notre fonction réside dans le recalcul incessant des mêmes valeurs. Pour éviter ce recalcul, il suffit de stocker au fur et à mesure les valeurs déjà calculées ; lorsque la fonction fibo est appelée avec un paramètre i, on commence par tester si cette valeur a déjà été calculée ; si c’est le cas, la fonction retourne directement le résultat déjà calculé, sinon, elle s’appelle récursivement. Un moyen simple d’effectuer ce test est de tenir compte de ce que les nombres de Fibonacci sont strictement positifs : on initialise un tableau à 0 et lors d’un appel à fibo n,

On obtient


#let nouveau_fibo n =  
   let valeurs_fibo = make_vect (n+1) 0 in  
      valeurs_fibo.(0) <- 1;  
      valeurs_fibo.(1) <- 1;  
      let rec fibo p=  
         if valeurs_fibo.(p)<>0  
             then valeurs_fibo.(p)  
             else  
               begin  
                 let temporaire = (fibo (p-1))+(fibo (p-2)) in  
                    valeurs_fibo.(p) <- temporaire;  
                    temporaire  
               end  
      in  
        fibo n;;  
 
 
nouveau_fibo : int -> int = <fun>  
#nouveau_fibo 35;;  
- : int = 14930352


Programme 3.21: nombres de Fibonacci avec stockage

On constate alors que la fonction fibo n’est appelée avec le paramètre i qu’au plus deux fois, lors du premier calcul éventuel de Fi+1 et Fi+2. Le nombre total d’appels de la fonction fibo est cette fois majoré par 2(n + 1). Dans le cas particulier4 de F100, le calcul demanderait seulement dans les 200 appels de la fonction, au lieu des 1022 appels dans la méthode purement récursive. Pour le calcul de F100, la méthode avec stockage est en gros cent milliards de milliards de fois plus rapide !

Nous voyons sur cet exemple que la méthode consistant à stocker les résultats intermédiaires nous a permis de diminuer la complexité de l’algorithme de calcul de Fn

Bien entendu le gain de rapidité, qui est gigantesque dès que n atteint quelques dizaines, a un coût : il a fallu utiliser de la mémoire pour stocker les résultats intermédiaires. En fait le programmeur est souvent confronté à un dilemme

Dans notre cas particulier, l’occupation en mémoire supplémentaire, qui est l’ordre de quelques centaines d’octets, est tout à fait négligeable en face du gain de rapidité considérable obtenu, et il n’y pas d’hésitation possible : il faut utiliser le stockage des valeurs intermédiaires.

Généralisation de la récursivité multiple Soit E un ensemble muni d’un ordre bien fondé , supposons donnée une partie A de E et soit φ1,k des applications de E \ A dans E vérifiant

∀i ∈ {1,...,k}, ∀x ∈ E \ A, φi(x) ≺ x

Nous supposons que nous avons un problème à résoudre pour x ∈ E et que

Alors, d’après le principe d’induction généralisé appliqué au prédicat

P(x) : je sais résoudre le problème pour x

on sait résoudre le problème pour tout x ∈ E.

Essayons par exemple de construire une fonction qui calcule le pgcd de deux entiers sans division. Nous pouvons appliquer les règles suivantes

Nous avons ici A = {(0,y) | y ∈ N} et φ1 : N2 \ A N2 définie par

         { (y,x)      si x > y
φ1(x,y) =  (x,y - x)  si 1 ≤ x ≤ y

Munissons N2 de l’ordre lexicographique

                (                         )
(n,m ) ≼ (n′,m′) si n < n′ ou (n = n′ et m ≤ m ′)

On sait qu’il s’agit là d’un bon ordre. De plus il est clair que

∀(x,y) ∈ N2 \A, φ (x,y) ≺ (x,y)
                1

Le principe d’induction généralisé nous montre que nous pouvons ainsi calculer le pgcd de deux entiers. Voici la fonction Caml correspondante :


#let rec pgcd x y =  
    if x>y then pgcd y x  
    else if x>0 then pgcd x (y-x)  
    else y;;  
 
pgcd : int -> int -> int = <fun>  
#pgcd 69825 53865;;  
- : int = 1995


Programme 3.22: pgcd récursif par soustraction

Note de programmation  Dans un moment de fatigue, l’auteur de ces lignes avait écrit


else if x>0 then pgcd x  y-x


Programme 3.23: pgcd erroné

au lieu de


else if x>0 then pgcd x (y-x)


Programme 3.24: syntaxe correcte

Pouvez vous deviner ce qui s’est passé ?

Eh bien, Caml interprétait évidemment la ligne comme


else if x>0 then (pgcd x y)-x


Programme 3.25: pgcd erroné

si bien qu’il rappelait de nouveau la fonction avec les mêmes paramètres, entrant dans une boucle infinie dont il sortait au bout d’un temps fini par saturation de la mémoire


Uncaught exception: Out_of_memory


Programme 3.26: résultat d’un appel récursif infini

L’algorithme d’Euclide L’exemple du calcul du pgcd par soustraction est un exemple d’école qui ne prétend à aucune efficacité ; par exemple la fonction est appelée 2000 fois pour calculer le pgcd de 2000 et de 1 ! On gagne un temps considérable en remplaçant y - x par le reste de la division euclidienne de y par x que l’on peut écrire en mathématiques sous la forme y mod x et en Caml sous la forme y mod x. On obtient ainsi l’algorithme d’Euclide dont la justesse se démontre de la même façon que dans le cas précédent en posant A = {(0,y) | y ∈ N}, φ1 : N2 \ A N2 définie par

         {
           (y,x)        si x > y
φ1(x,y) =  (x,y mod x)  si 1 ≤ x ≤ y

et en utilisant l’ordre lexicographique sur N2. Voici la fonction Caml correspondante :


#let rec pgcd x y =  
    if x>y then pgcd y x  
    else if x>0 then pgcd x (y mod x)  
    else y;;  
 
pgcd : int -> int -> int = <fun>  
#pgcd 710220 3644865;;  
- : int = 1995


Programme 3.27: algorithme d’Euclide récursif

La fonction d’Ackermann La récursivité multiple peut prendre des formes encore plus complexes où la fonction elle même que l’on cherche à calculer intervient dans la définition des fonctions φi.

La fonction d’Ackermann est la fonction Ack : N2 N définie par

Pour voir que la fonction est effectivement définie, nous allons appliquer le principe d’induction. Pour cela, nous munissons N2 de l’ordre lexicographique

                (                         )
(n,m ) ≼ (n′,m′) si n < n′ ou (n = n′ et m ≤ m ′)

On sait qu’il s’agit là d’un bon ordre. Considérons le prédicat suivant

P(n,m) : les formules de définition calculent Ack(n,m) en un nombre fini d’opérations

Nous allons montrer que P(n,m) est vrai pour tout (n,m) ∈ N2. Raisonnons par l’absurde et supposons A = {(n,m) ∈ N2 | P(n,m) est faux } non vide. Alors A a un plus petit élément (n0,m0). Comme les formules de définition calculent en une seule fois Ack(n,m) si n = 0, on a n0 > 0.

On a donc finalement A = , ce qui montre que la fonction est bien définie.

En Caml, on peut donc écrire :


#let rec ack x =  
      match x with  
         (0,m) -> m+1  
      |  (n,0) -> ack(n-1,1)  
      |  (n,m) -> ack (n-1,ack(n,m-1));;  
ack : int * int -> int = <fun>  
#ack (3,4);;  
- : int = 125


Programme 3.28: fonction d’Ackermann

3.3.3 Procédures et fonctions récursives croisées

Pour terminer notre étude de différents modes de récursivité, nous évoquerons les fonctions récursives croisées à l’aide d’un exemple tiré des mathématiques. Nous en rencontrerons des exemples plus fondamentaux dans le chapitre sur les expressions algébriques.

Pour illustrer cette récursivité croisée, nous utiliserons l’exemple de l’étude de suites récurrentes du type xn = f(xn-1,yn-1),yn = g(xn-1,yn-1), les valeurs initiales x0 et y0 étant données. Le calcul de xn et yn nécessite donc la connaissance simultanée de xn-1 et de yn-1. Il est clair que la déclaration des fonctions x et y doit être à la fois récursive et simultanée. A cet effet la construction let rec permet de définir simultanément plusieurs identificateurs liés les uns aux autres de manière récursive, chacun d’entre eux pouvant faire appel à tous les autres.

Définissons par exemple deux suites récurrentes par xn = xn-1 + yn-1 et yn = xn-1yn-1 avec x0 = 1, y0 = 2. Pour calculer xn et yn on peut utiliser les deux fonctions Caml suivantes


#let rec x = function  
           0 -> 1 | n -> x(n-1)+y(n-1)  
and  y =  function  
           0 -> 2 | n -> x(n-1)*y(n-1);;  
x : int -> int = <fun>  
y : int -> int = <fun>  
 
#x 8;;  
- : int = 1063433425  
#y 6;;  
- : int = 5019630


Programme 3.29: récursivité croisée

Remarque  Cet exemple de récursivité croisée est assez artificiel puisque le même calcul peut être effectué en une seule fois sur le couple z = (x,y) en écrivant


#let rec z = function  
      0 -> (1,2)  
   |  n -> let (xprec,yprec) = z(n-1) in  
             (xprec+yprec,xprec1*yprec);;  
z : int -> int * int = <fun>  
#z 6;;  
- : int * int = 13901, 5019630  
#z 8;;  
- : int * int = 1063433425, 505469074


Programme 3.30: récursivité croisée et récursivité simple

Qui plus est, au passage on a les valeurs des deux suites à la fois pour le même prix. Nous verrons plus tard des exemples moins artificiels de récursivité croisée, l’important est seulement ici de remarquer que cette récursivité croisée existe et est possible.

3.3.4 Ensembles définis récursivement

La méthodologie récursive ne s’applique pas seulement aux procédures ou fonctions, mais aussi à la définition même de certains objets. Intuitivement, la définition récursive d’un ensemble X consiste en la donnée explicite de certains éléments de X et d’un moyen de construire de nouveaux éléments de X à partir d’éléments déjà connus. On peut ainsi construire des objets complexes à partir d’objets simples et d’opérations d’assemblages.

De manière plus formelle, donnons nous un ensemble E, une partie B de E et un ensemble K d’applications φ : En(φ) E.

Définition 3.3.1 On dit qu’une partie A de E est K stable si

∀φ ∈ K, ∀a1,...,an(φ) ∈ A, φ(a1,...,an(φ)) ∈ A

Il est clair que toute intersection de parties K stables est encore K stable et que E lui-même est K stable. On en déduit que l’intersection de toutes les parties K stables contenant B est encore une partie K stable contenant B, et qu’elle est contenue dans toute partie K stable contenant B ; c’est donc le plus petit élément de l’ensemble des parties K stables contenant B.

Définition 3.3.2 Soit E un ensemble, B une partie de E, K un ensemble d’opérations φ : En(φ) E. On appelle ensemble X défini récursivement par les deux relations

la plus petite partie X de E qui est K stable et contient B (c’est aussi l’intersection de toutes les parties K stables contenant B).

Exemple  Voici quelques exemples de définitions récursives (ou inductives)

La proposition suivante montre que, dans les définitions récursives d’ensembles, les objets construits sont obtenus à partir d’un nombre fini (mais variable) d’opérations à partir des objets de base.

Proposition 3.3.1 Soit E, B et K comme ci dessus et soit X l’ensemble défini récursivement par la donnée de B et K. Alors tout élément de X peut s’obtenir à partir de la base B par application d’un nombre fini d’opérations φ ∈ K ; de manière plus formelle, si l’on pose X0 = B et pour p ∈ N,

         ⋃
Xp+1 = Xp  {φ (x1,...,xn(φ)) | φ ∈ K et x1,...,xn(φ) ∈ Xp}

alors X = p∈NXp.

Démonstration: soit Y = p∈NXp. Il est clair que B = X0 Y  ; d’autre part, Y est K stable car si φ ∈ K et x1,,xn(φ) sont dans Y , on a x1 ∈ Xp1,,xn(φ) ∈ Xpn(φ) et comme la suite (Xp) est croissante, on a x1,,xn(φ) ∈ Xmm = max{p1,,pn(φ)} ; mais alors φ(x1,,xn(φ)) ∈ Xm+1 Y . Comme Y est K stable contenant B, on a nécessairement X Y (puisque X est l’intersection de toutes les parties K stables contenant B). Inversement, on a bien évidemment que si A est une partie K stable et si Xp A, alors Xp+1 A. C’est vrai en particulier pour X et comme B = X0 X, on a par récurrence que p, Xp X, et donc Y X. On en déduit que X = Y .

Beaucoup de démonstrations sur les ensembles définis récursivement utiliseront le théorème suivant

Théorème 3.3.1 (Principe d’induction structurelle) Soit E un ensemble, B une partie de E, K un ensemble d’opérations φ : En(φ) E. On considère l’ensemble X défini récursivement par les deux relations

Soit P un prédicat sur E. On suppose que P(x) est vrai pour tout x ∈ B et que pour tout φ ∈ K et pour tout x1,,xn(φ) ∈ E,

P(x1),...,P(xn(φ)) sont vrais ⇒ P (φ(x1,...,xn(φ))) est vrai

Alors P(x) est vrai pour tout x ∈ E.

Démonstration: soit Y = {x ∈ E | P(x) est vrai}. On sait que B Y et que Y est K stable puisque

φ ∈ K, x1,...,xn(φ) ∈ Y ⇒ φ (x1,...,xn (φ))

On en déduit que Y contient l’ensemble X qui est l’intersection de toutes les parties de E qui sont K stables et contiennent B.

Exemple  Revenons sur l’ensemble X des parenthésages bien formés constitué du sous ensemble de l’ensemble des mots défini récursivement par

Nous allons montrer par le principe d’induction structurelle qu’un élément de X comporte autant de parenthèses ouvrantes que de parenthèses fermantes. C’est vrai pour le mot vide qui comporte 0 parenthèse ouvrante et 0 parenthèse fermante. De plus si x et y comportent autant de parenthèses ouvrantes que de parenthèses fermantes, il en est de même de (x) (qui a une parenthèse ouvrante et une parenthèse fermante de plus que x) et de xy (dont le nombre de parenthèses ouvrantes ou fermantes est la somme du nombre correspondant pour x et du nombre correspondant pour y). D’après le principe d’induction structurelle tout élément x de X vérifie la propriété.

Remarque  La réciproque du résultat précédent est bien évidemment fausse. Le parenthésage ())()( a le même nombre de parenthèses ouvrantes et fermantes et cependant il n’est pas bien formé ; d’ailleurs le même principe d’induction structurelle montre qu’un parenthésage bien formé doit commencer par une parenthèse ouvrante et se terminer sur une parenthèse fermante. Ces conditions ne suffisent toujours pas à caractériser les parenthésages bien formés comme le montre l’exemple du parenthésage ())()(() qui n’est pas bien formé, bien qu’ayant le même nombre de parenthèses ouvrantes et fermantes, commençant par une parenthèse ouvrante et se terminant par une parenthèse fermante.

3.4 Récursivité et itération

3.4.1 Aperçus sur les appels de fonctions et de procédures

Imaginons le déroulement d’un programme comme le parcours d’un chemin ayant une origine et une extrémité. Un appel de sous programme (fonction ou procédure) est l’analogue d’un circuit greffé sur le chemin parcouru, circuit dont l’origine est confondu avec l’extrémité. Pour gérer ce circuit, le micro-processeur a besoin de retenir le point de départ du circuit ; ceci lui permet de retourner exactement au même point en fin de circuit. De plus l’exécution du sous programme implique en général de créer de nouvelles variables tout en sauvegardant les valeurs des variables créées par la procédure appelante.

A cet effet, le micro-processeur gère une ou plusieurs piles (au sens d’une pile d’assiettes) dans lesquelles il stocke par empilement les adresses de retour des sous-programmes (l’endroit d’où le sous programme a été appelé et où il doit retourner en fin d’exécution) et les valeurs des différentes variables. A l’entrée dans le sous programme, le microprocesseur empile l’adresse de retour. Lors de l’exécution du sous programme il empile au fur et à mesure les nouvelles variables créées. Lors de la sortie du sous programme, il dépile les différentes variables créées par le sous programme et qui n’ont plus de signification en dehors de celui ci, puis il dépile l’adresse de retour qu’il utilise ensuite pour retourner à l’endroit voulu (c’est à dire le point d’appel).

Tout appel de sous programme (procédure ou fonction) consomme à la fois de la mémoire (pour stocker au moins l’adresse de retour et souvent des variables auxiliaires) et du temps (pour empiler et dépiler les adresses et les variables)5.

3.4.2 Récursivité contre itération

Nous avons vu combien la programmation récursive était naturelle, élégante et puissante pour trouver des solutions à des problèmes. Mais cette programmation fait un usage intensif d’appels de sous programmes et comme nous l’avons vu par ailleurs tout appel de sous programme consomme à la fois du temps et de la mémoire. D’autre part, l’exemple du calcul de la suite de Fibonacci nous a démontré qu’un usage non réfléchi de la récursivité pouvait conduire à une très grande inefficacité : un temps de calcul de Fn de l’ordre de 2n à la place du temps de calcul proportionnel à n que l’on peut obtenir avec un peu d’intelligence. Bien entendu ce n’est pas la récursivité elle-même qui est en cause, mais une utilisation non réfléchie de celle-ci.

Il peut parfois sembler intéressant pour des raisons d’efficacité de remplacer des appels récursifs de sous programmes par une simple itération obtenue par une boucle indexée ou une boucle avec test booléen. Nous allons d’abord étudier quelques exemples très simples avant d’essayer de faire une théorie de cette transformation.

En ce qui concerne le calcul des puissances, on peut remarquer que an = i=1na ce qui conduit immédiatement à introduire une référence y sur i=1ja et donc à définir


#let puiss x n =  
     let y = ref 1 in  
       for i = 1 to n do  
          y := !y*x  
       done;  
       !y;;  
puiss : int -> int -> int = <fun>  
#puiss 2 8;;  
- : int = 256  
#puiss 2 0;;  
- : int = 1


Programme 3.31: calcul itératif des puissances

Revenons sur le cas du calcul de la factorielle. Bien que la définition de la factorielle soit le plus souvent récursive, il est très facile d’en donner une définition itérative en écrivant n! = i=1ni. Ceci nécessite le stockage dans une variable provisoire prov des valeurs successives du produit des i premiers nombres entiers. Les valeurs de cette variable doivent être actualisées au fur et à mesure, ce qui nécessite que cette variable soit une référence. On obtient une nouvelle fonction factorielle que nous pouvons écrire en Caml sous la forme :


#let fact n =  
     let prov = ref 1 in  
        for i = 1 to n do  
           prov := !prov * i  
         done;  
        !prov;;  
fact : int -> int = <fun>  
#fact 8;;  
- : int = 40320


Programme 3.32: calcul itératif de la factorielle

La même méthode s’applique à tout suite définie par récurrence par x0 = a et pour n 0, xn = f(n,xn-1). Ceci permet de définir une fonction générique en Caml, recevant en paramètre la formule de définition par récurrence f, la valeur initiale a et l’indice n du terme à calculer


#let recur f a n =  
    let prov = ref a in  
       for i = 1 to n do  
          prov := f i (!prov)  
       done;  
     !prov;;  
recur : (int -> ’a -> ’a) -> ’a -> int -> ’a = <fun>


Programme 3.33: calcul itératif générique d’une récurrence d’ordre 1

La factorielle correspond à la fonction f(n,x) = nx si bien que l’on obtient un calcul de la factorielle par :


#let f n x = n*x in  
    recur f 1 4;;  
 
- : int = 24  
#let f n x=n*x in  
    recur f 1 8;;  
 
- : int = 40320


Programme 3.34: application d’un calcul générique à la factorielle

La programmation fonctionnelle permet même de définir la fonction factorielle en appliquant simplement notre fonction recur à la fonction f : (n,x)↦→nx et à la valeur initiale a = 1, ce qui donne :


let factorielle =  
     let f n x = n*x in  
        recur f 1;;  
factorielle : int -> int = <fun>  
#factorielle 8;;  
- : int = 40320


Programme 3.35: application d’une fonctionnelle générique à la factorielle

Essayons d’appliquer la même méthode à la suite de Fibonacci définie par F0 = F1 = 1 et Fn = Fn-1 + Fn-2. Pour cela posons xn = Fn et yn = Fn+1. On a x0 = 1, y0 = 1 ; d’autre part xn = Fn = yn-1 et yn = Fn+1 = Fn + Fn-1 = yn-1 + xn-1. En définitive, si on pose zn = (xn,yn), la suite zn est définie par récurrence par zn = f(zn-1) avec f(x,y) = (y,x + y). Ceci permet d’obtenir une fonction itérative de calcul des nombres de Fibonacci en écrivant en Caml :


#let fib2 n =  
     let prov = ref (1,1) in  
        for i = 1 to n do  
           match !prov with (x,y) ->  
              prov := (y,x+y)  
        done;  
        !prov;;  
 
fib2 : int -> int * int = <fun>  
 
#fib2 35;;  
- : int * int = 14930352, 24157817


Programme 3.36: calcul itératif des nombres de Fibonacci

Remarquons que cette fonction calcule à la fois Fn et Fn+1, dans un temps manifestement proportionnel à n, comme la fonction récursive avec stockage des résultats intermédiaires ; mais cette fonction itérative n’utilise pas de tableau de stockage des résultats intermédiaires (elle utilise uniquement une référence au lieu d’un tableau à n éléments). Ceci montre l’amélioration obtenue en transformant la fonction récursive en fonction itérative. Bien entendu, rien n’empêche de scinder le couple (x,y) en son premier et son second élément et d’écrire


#let fib n =  
      let x = ref 1 and y = ref 1 and yPrec = ref 0 in  
        for i = 1 to n do  
           yPrec := !y;  
           y := !x + !y;  
           x := !yPrec  
        done;  
        !x;;  
fib : int -> int = <fun>  
#fib 35;;  
- : int = 14930352


Programme 3.37: calcul itératif des nombres de Fibonacci

Il faut prendre garde à ne pas perdre la valeur pointée par la référence y tant que l’on en a besoin, d’où l’utilisation d’une variable provisoire yPrec qui permet de stocker cette valeur.

Remarque  Le lecteur attentif remarquera que nous avons calculé un terme de trop dans la suite et que l’on peut tenter d’écrire


#let fib n =  
     let x = ref 1 and y = ref 1 and yPrec = ref 0 in  
        for i = 1 to n-1 do  
           yPrec := !y;  
           y := !x + !y;  
           x := !yPrec  
        done;  
        !y;;  
fib : int -> int = <fun>  
#fib 35;;  
- : int = 14930352


Programme 3.38: calcul itératif ”simplifié” des nombres de Fibonacci

avec une petite économie de temps d’exécution. Il faut simplement remarquer que ce gain de temps a été obtenu au prix d’un programme fondamentalement incorrect puisque, lorsqu’il est appelé avec n = 0, il renvoie F1 au lieu de F0. Autrement dit l’utilisation du même schéma de programme avec une autre suite récurrente serait susceptible de renvoyer un résultat erroné. La correction de ce programme nécessite alors un test de la valeur de n pour renvoyer le terme d’indice 0 si n = 0, mais à ce moment, le gain en temps d’exécution disparaît. Comme quoi, à vouloir mieux faire

3.4.3 Récursivité terminale

Nous avons vu dans le paragraphe précédent la manière de procéder pour remplacer un appel récursif de fonction par une boucle indexée dans le calcul des termes d’une suite récurrente xn = f(n,xn-1). Le fait que l’ensemble sur lequel on travaille est l’ensemble N des entiers naturels peut masquer la méthode générale sous-jacente.

Donnons nous un ensemble E muni d’un ordre bien fondé (pour lequel toute partie admet donc un élément minimal) ; soit B une partie de E et φ : E \ B E telle que x ∈ E, φ(x) x. Soit f une fonction de B dans un ensemble E. Il existe alors une unique application F : E Edéfinie récursivement par

Supposons que nous avons défini une procédure action qui pour chaque x ∈ E effectue une certaine action sur l’environnement et soit prog1 le sous programme récursif défini par


let rec prog1 x =  
      action x;  
      if dansB(x) then f(x)  
                  else prog1 phi x;;


Programme 3.39: récursivité terminale générique

Considérons d’autre part le sous programme prog2 défini par :


let prog2 x =  
    let xRef = ref x in  
       while not(dansB(x)) do  
          action !xRef;  
          xRef := phi !xRef  
       done;  
       action !xRef;  
       f !xRef;;


Programme 3.40: suppression d’une récursivité terminale

Proposition 3.4.1 Les deux sous programmes prog1 et prog2 effectuent la même action et retournent le même résultat pour tout x ∈ E.

Démonstration: C’est clair pour x ∈ B, puisqu’alors aussi bien prog1 que prog2 effectuent l’action action(x) puis renvoient f(x). Soit X l’ensemble des éléments vérifiant cette propriété et supposons XE. Soit x0 un élément minimal de E \ X. Le sous programme prog1 appliqué à x0 effectue l’action action(x0), puis appelle le sous programme prog1 sur φ(x0). Le sous programme prog2 appliqué à x0 effectue l’action action(x0) puis remplace x0 par φ(x0) avant d’effectuer la même action et de renvoyer le même résultat que le sous programme prog2 sur φ(x0). Mais, comme φ(x0) x0 et x0 = min(E\X), on a φ(x0)∕∈E\X, et donc φ(x0) ∈ X. On en déduit que prog1 et prog2 effectuent la même action et retournent le même résultat avec le paramètre x0, donc x0 ∈ X contrairement à sa définition.

Le fait essentiel qui permet le remplacement des appels récursifs par une simple boucle booléenne est que ces appels récursifs sont la dernière instruction du sous programme ; de ce fait, toute l’action du sous programme étant déjà effectuée au moment de l’appel récursif, aucune sauvegarde de l’environnement n’est nécessaire. On dit dans ce cas que la récursivité est terminale6.

3.4.4 Un exemple de dérécursivation non terminale

Nous venons de voir comment un appel récursif terminal pouvait être remplacé par une boucle conditionnelle. Il n’en va pas de même si l’appel récursif se situe avant que l’action du sous programme ne soit terminée, cas de la récursivité non terminale. Dans ce cas il est nécessaire de sauvegarder au minimum les valeurs successives des variables qui seront utilisées par le suite de l’action du sous programme. La dérécursivation est encore possible mais beaucoup plus complexe. Nous allons en voir un exemple dans le cas du calcul de fonctions définies par induction.

Soit f une fonction de B dans un ensemble E, g une application de E × E dans E. Il existe alors une unique application F : E Edéfinie récursivement par

La première méthode de calcul repose sur un calcul récursif suivant le schéma de définition même de la fonction F que nous pouvons écrire en Caml sous la forme


let rec F x =  
     if dansB(x) then f(x)  
     else g x F(phi(x));;


Programme 3.41: récursivité non terminale

où la fonction dansB est un test booléen qui renvoie true si et seulement si x est dans B.

La deuxième méthode de calcul repose sur une boucle à test booléen. Elle suppose la gestion de deux références, une liste pour conserver les valeurs successives de x et un élément de Epour conserver le résultat de l’appel de fonction. Dans un souci de lisibilité et d’efficacité, nous introduirons une troisième référence sur la variable x ; celle ci n’est pas indispensable puisqu’elle sert uniquement de relais pour conserver la valeur de tête de la liste. Nous commencerons par calculer les valeurs successives de x,φ(x),k(x) jusqu’à ce que nous arrivions dans B, ce qui ne peut manquer de se produire du fait du caractère bien fondé de notre ordre ; ces valeurs sont stockées au fur et à mesure dans la liste pointée par xListe. Il suffit ensuite de remonter le calcul de F tout au long de la liste en utilisant et supprimant au fur et à mesure l’élément de tête de la liste. Nous pouvons donc écrire notre calcul itératif sous la forme :


let F x =  
       let xRef = ref x and xListe = ref [x] and yRef = ref y0 in  
       while not(dansB(!xRef)) do  
          xRef := phi !xRef;  
          xListe := !xRef::!xListe  
       done;  
       yRef := f !xRef; (* !xRef est dans B *)  
       xListe := tl !xListe; (* supprime l’élément de tête *)  
       while !xListe<>() do  
          match !xListe with  
            h::r -> begin  
                      yRef := g h !yRef;  
                      xListe := r;(* supprime l’élément de tête *)  
                    end;  
      !yRef;;


Programme 3.42: version itérative d’une récursivité non terminale

Faut-il procéder à un tel remplacement d’appels récursifs par une (ou plusieurs) boucles booléennes ? Notons tout d’abord la différence de simplicité et de lisibilité entre les deux formes. La version récursive de la fonction tient en trois lignes et colle au plus près à la définition mathématique, la version itérative demande une dizaine de lignes, et pas mal de réflexion, pour se convaincre qu’elle effectue le même calcul.

En dehors de l’exercice académique que représente la dérécursivation d’un sous programme, exercice qui oblige à se plonger plus profondément dans la logique de la machine, le seul intérêt que l’on peut voir à ce type de transformation est d’améliorer un sous programme qui est critique soit du point de vue de la vitesse d’exécution (notre exemple n’étant certainement pas grandement amélioré avec ses deux boucles booléennes et une gestion des listes qui échappe en grande partie à notre contrôle), soit du point de vue de la mémoire, en gérant avec intelligence ce qui doit être sauvegardé (là encore notre exemple n’est guère significatif puisqu’il oblige à créer une référence sur une liste qui croît au fur et à mesure de nos appels à φ).

De ces deux points de vue (vitesse d’exécution et gestion de la mémoire), peut-être vaut-il mieux utiliser de manière plus intelligente et moins brutale la récursivité, en introduisant par exemple des fonctions auxiliaires, plutôt que de se lancer dans une dérécursivation coûteuse en temps de travail et aux résultats plus ou moins incertains.

3.5 Exemples de tris

3.5.1 Introduction aux tris

Le tri est une opération fondamentale de traitement des données. Il constitue le plus souvent une opération préalable à un traitement efficace de ces données. Pour se convaincre de l’utilité d’un tri, imaginez que les mots dans votre dictionnaire préféré soient mis en vrac au lieu d’être triés par ordre alphabétique et que vous ayiez à y chercher le mot existentiel ; la seule solution serait alors de parcourir tout le dictionnaire jusqu’à trouver le mot en question. De même, la recherche d’un nom sur une liste d’admis à un concours est grandement facilitée par un tri alphabétique de la liste des reçus. C’est ainsi que de nombreux algorithmes informatiques supposent que des données ont été préalablement triées.

Dans le cas de gros volumes de données comme on en trouve très fréquemment dans l’informatique courante, le choix d’une méthode de tri est cruciale. Il se trouve cependant qu’il n’existe pas de méthode de tri optimale universelle. Toute méthode de tri utilise quelques opérations fondamentales comme la comparaison entre deux éléments et l’échange de deux éléments. Suivant le type de données considéré le coût de la comparaison et celui de l’échange peuvent être très différents et, dans un souci d’efficacité, on peut être amené à privilégier un petit nombre de comparaisons ou un petit nombre d’échanges.

De plus la façon dont on accède aux données influe grandement sur le choix d’une méthode de tri :

Dans la suite de ce chapitre, nous supposerons que nous disposons de N données stockées dans un tableau7 a[0],,a[N + 1] dans les éléments d’indice 1 à N (les éléments d’indice 0 et N + 1 seront souvent réservés à un usage particulier). Pour simplifier , nous supposerons que les données stockées sont des entiers : il est immédiat d’adapter les méthodes au cas d’un type quelconque muni d’une relation d’ordre total. Nous utiliserons systématiquement une procédure echange qui reçoit en paramètres un tableau et deux indices et procède à l’échange des deux éléments d’indices correspondants du tableau. En Caml, on peut écrire une telle procédure sous la forme :


#let echange tableau i j =  
     let temp = tableau.(i) in  
       tableau.(i)<- tableau.(j);  
       tableau.(j)<- temp;;  
echange : ’a vect -> int -> int -> unit = <fun>


Programme 3.43: échange dans un tableau

la variable temp servant à stocker temporairement la valeur de tableau.(i).

A titre d’application, nous utiliserons un tableau de taille n + 2 initialisé avec des nombres entiers choisis au hasard parmi 1lim - 1. Pour cela nous construisons une fonction Caml hasard_vect ; cette fonction utilise deux fonctions de la bibliothèque d’utilitaires random :

L’intérêt du paramètre lim est de forcer des répétitions à l’intérieur du tableau. Nous obtenons la fonction :


#let hasard_vect n lim =  
  let v = make_vect (n+2) 0 in  
    random__init 1995;  
    for i = 1 to n do  
       v.(i)<- random__int lim  
    done;  
    v;;  
hasard : int -> int -> int vect = <fun>  
#let v = hasard_vect 15 10;;  
v : int vect = [|0; 6; 4; 4; 4; 0; 0; 8; 0;  
          8; 8; 6; 4; 0; 6; 6; 0|]


Programme 3.44: vecteur aléatoire

Pour la commodité, nous utiliserons également une procédure d’affichage des tableaux d’entiers qui enlève le premier et le dernier élément du tableau :


#let affiche_tableau a =  
    let n = vect_length a in  
       print_string "[|";  
       for i = 1 to n-3 do  
          print_int a.(i);  
          print_char ‘;‘  
       done;  
       print_int a.(n-2);  
       print_string "|]";  
       print_newline();;  
affiche_tableau : int vect -> unit = <fun>  
#affiche_tableau v;;  
[|0;0;0;0;0;4;4;4;4;6;6;6;6;8;8;8;0|]  
- : unit = ()


Programme 3.45: affichage d’un tableau d’entiers

3.5.2 Le tri par sélection

C’est l’une des méthodes de tri les plus simples : on cherche d’abord l’élément le plus petit dans le tableau et on l’échange avec le premier élément du tableau ; ensuite on cherche l’élément immédiatement supérieur et on l’échange avec le deuxième élément du tableau et ainsi de suite jusqu’à épuisement du tableau ; ce tri procède donc par sélection du plus petit élément parmi a[i],,a[N] puis échange ce plus petit élément avec a[i].

Une telle procédure peut s’écrire en Caml.


#let tri_selection a =  
     let N = (vect_length a)-2 and min = ref 0 in  
        for i = 1 to N-1 do  
            min := i;  
            for j = i+1 to N do  
              if a.(j)<a.(!min) then min := j  
            done;  
            echange a i !min  
          done;;  
tri_selection : int vect -> unit = <fun>


Programme 3.46: tri par sélection d’un tableau

et voici son application à un exemple avec les modifications successives du tableau


#let v = hasard_vect 15 15 in tri_selection v;;  
 
[|11;9;14;9;5;0;13;0;13;13;1;14;10;11;11|]  
[|0;9;14;9;5;11;13;0;13;13;1;14;10;11;11|]  
[|0;0;14;9;5;11;13;9;13;13;1;14;10;11;11|]  
[|0;0;1;9;5;11;13;9;13;13;14;14;10;11;11|]  
[|0;0;1;5;9;11;13;9;13;13;14;14;10;11;11|]  
[|0;0;1;5;9;11;13;9;13;13;14;14;10;11;11|]  
[|0;0;1;5;9;9;13;11;13;13;14;14;10;11;11|]  
[|0;0;1;5;9;9;10;11;13;13;14;14;13;11;11|]  
[|0;0;1;5;9;9;10;11;13;13;14;14;13;11;11|]  
[|0;0;1;5;9;9;10;11;11;13;14;14;13;13;11|]  
[|0;0;1;5;9;9;10;11;11;11;14;14;13;13;13|]  
[|0;0;1;5;9;9;10;11;11;11;13;14;14;13;13|]  
[|0;0;1;5;9;9;10;11;11;11;13;13;14;14;13|]  
[|0;0;1;5;9;9;10;11;11;11;13;13;13;14;14|]  
[|0;0;1;5;9;9;10;11;11;11;13;13;13;14;14|]  
- : unit = ()


Programme 3.47: exécution d’un tri par sélection

Théorème 3.5.1 Le tri par sélection trie un tableau de N éléments avec un nombre de comparaisons équivalent à N 2∕2 et un nombre d’échanges égal à N - 1.

Démonstration: Il faut tout d’abord démontrer que le tri par sélection trie effectivement le tableau. La terminaison de l’algorithme est garantie par le fait qu’il s’agit de boucles indexées. Il nous reste à exhiber deux invariants de boucles, l’un pour la boucle interne indexée par j, l’autre pour la boucle externe indexée par i. En ce qui concerne la boucle interne, un invariant est

P(j) : après exécution de l’itération d’indice j ∈ [i + 1,N], a[min] est le minimum de a[i],a[i + 1],,a[j]

C’est évidemment vrai après la première itération, et si la propriété est vraie à la sortie du corps pour j - 1, on a deux possibilités

ce qui montre que P(j) est vrai.

Après exécution de la boucle interne, on en déduit que a[min] est le minimum de a[i],a[i + 1],,a[N]. L’invariant de la boucle externe indexée par i sera donc

P(i) : après l’itération d’indice i, on a

a[1] ≤ a[2] ≤ ...≤ a[i] = min(a[i],a[i+ 1],...,a[N ])

Après exécution de la boucle externe, on a donc

a[1] ≤ a[2] ≤ ...≤ a[N - 1] = min(a[N - 1],a[N ])

ce qui montre que le tableau est trié.

Dans le tri par sélection de N éléments, on effectue une comparaison par exécution du corps de la boucle interne, soit (N - 1) + (N - 2) + + 1 = N (N - 1)∕2 comparaisons et un échange par exécution du corps de la boucle externe, soit N - 1 échanges. Le tri par sélection de N éléments demande donc un nombre de comparaisons qui est équivalent à N2∕2 et un nombre d’échanges qui est équivalent à N.

3.5.3 Le tri par insertion

Le tri par insertion est similaire au tri du joueur de cartes qui insère les cartes une à une dans son jeu de manière à ce qu’à tout instant le jeu soit trié. Pour cela il parcourt les cartes déjà insérées en partant de la plus grande et insère la carte considérée juste après la première carte immédiatement inférieure qu’il rencontre au cours de son parcours (en début de jeu s’il n’en a rencontré aucune). On peut formaliser cet algorithme sous la forme

pour chaque i, insérer l’élément a[i] parmi a[1],a[i - 1]

où la procédure d’insertion peut être définie par

prendre le premier j, en descendant à partir de i, tel que a[j - 1] a[i], en décalant au fur et à mesure les éléments rencontrés vers la droite, puis insérer a[i] à la j-ième place.

ce qui peut s’écrire en Caml :


tri_insertion a =  
     let N = (vect_length a)-2 in  
        for i = 2 to N do  
           let v = a.(i) and j = ref i in  
              while (a.(!j-1)>v) do  
                 a.(!j) <- a.(!j-1);  
                 j := !j -1  
              done;  
              a.(!j)<- v  
      done;;


Programme 3.48: tri par insertion d’un tableau (avec sentinelle)

En fait ce sous programme contient une erreur évidente : si a[i] est le plus petit élément de a[1],,a[i - 1], la boucle interne va se poursuivre jusqu’à j = 1, puis va provoquer un débordement vers la gauche du tableau avec la comparaison suivante de a[0] à v. La première manière de corriger cette erreur est d’éviter un débordement vers la gauche en testant si j > 1. Cela peut se faire de la manière suivante


tri_insertion a =  
     let N = (vect_length a)-2 in  
        for i = 2 to N do  
           let v = a.(i) and j = ref i in  
              while (!j>1) & (a.(!j-1)>v) do  
                 a.(!j) <- a.(!j-1);  
                 j := !j -1  
              done;  
              a.(!j)<- v  
      done;;


Programme 3.49: tri par insertion d’un tableau avec test de débordement

Cette précaution double le nombre de tests à effectuer alors que la situation décrite est relativement exceptionnelle8. Une autre solution est d’utiliser la place réservée a[0] et de mettre à cet endroit une sentinelle, c’est à dire un élément dont on est certain qu’il va arrêter la boucle. Il suffit pour cela qu’il soit inférieur à tout élément rencontré. Tout naturellement, si j devient égal à 1, on aura a[j - 1] v et la boucle s’arrêtera d’elle même. Si nous travaillons par exemple avec des entiers positifs, la valeur 0 que nous avons choisie pour a[0] convient parfaitement, si bien que la première version du programme de tri par insertion, qui était erronée si l’on ne tenait pas compte de a[0] devient maintenant correcte si a[0] = 0 et si tous les a[i] sont des entiers positifs. Voici un exemple d’exécution avec affichage des tableaux successifs


#let v = hasard_vect 15 15 in  
    tri_insertion v;;  
 
[|9;11;14;9;5;0;13;0;13;13;1;14;10;11;11|]  
[|9;11;14;9;5;0;13;0;13;13;1;14;10;11;11|]  
[|9;9;11;14;5;0;13;0;13;13;1;14;10;11;11|]  
[|5;9;9;11;14;0;13;0;13;13;1;14;10;11;11|]  
[|0;5;9;9;11;14;13;0;13;13;1;14;10;11;11|]  
[|0;5;9;9;11;13;14;0;13;13;1;14;10;11;11|]  
[|0;0;5;9;9;11;13;14;13;13;1;14;10;11;11|]  
[|0;0;5;9;9;11;13;13;14;13;1;14;10;11;11|]  
[|0;0;5;9;9;11;13;13;13;14;1;14;10;11;11|]  
[|0;0;1;5;9;9;11;13;13;13;14;14;10;11;11|]  
[|0;0;1;5;9;9;11;13;13;13;14;14;10;11;11|]  
[|0;0;1;5;9;9;10;11;13;13;13;14;14;11;11|]  
[|0;0;1;5;9;9;10;11;11;13;13;13;14;14;11|]  
[|0;0;1;5;9;9;10;11;11;11;13;13;13;14;14|]  
- : unit = ()


Programme 3.50: exécution d’un tri par insertion

Remarquons cependant que la méthode de la sentinelle est rarement praticable, puisqu’elle exige que l’on connaisse a priori un élément plus petit que tous les autres ; de plus elle oblige à travailler sur un tableau ayant un élément de plus que le tableau initial, d’où la plupart du temps une recopie du tableau dans un tableau plus grand. Le gain obtenu n’est donc pas franchement évident.

Théorème 3.5.2 Le tri par insertion trie un tableau de N éléments avec un nombre de comparaisons et un nombre d’affectations équivalents à

Démonstration: il faut tout d’abord démontrer que le tri par insertion trie effectivement le tableau. La terminaison de la boucle extérieure est garantie par le fait qu’il s’agit d’une boucle indexée et la terminaison de la boucle intérieure par la décroissance stricte de l’indice j qui doit de toute façon rester positif puisque a0 v.

Il nous reste à exhiber des invariants des deux boucles. En ce qui concerne la boucle booléenne intérieure, il est clair qu’à l’entrée dans le corps de la boucle, on a v < aj aj+1 ai et que lors de la sortie de la boucle on a en plus v aj-1. Après la sortie de la boucle booléenne, on a donc a0 a1 aj-1 v < aj+1 ai et après l’affectation de v à aj, on a donc a0 a1 ai ce qui fournit un invariant pour la boucle extérieure (indexée). Lorsque i atteint la valeur n à la sortie de la boucle extérieure, on a donc a0 a1 an ce qui montre que le tableau est trié.

Dans le cas le plus défavorable (quand le tableau est à l’origine trié en ordre décroissant), chaque élément ai remonte toute la chaîne jusqu’à arriver en première position et on effectue donc N + (N - 1) + + 2 + 1 = N (N  + 1)∕2 ~ 2
N ∕2 comparaisons et autant d’affectations.

Dans le cas moyen (cas d’un tableau aléatoire), on peut s’attendre à ce que ai vienne s’insérer environ à la moitié de la liste, ce qui divise par deux le nombre de comparaisons et d’affectations.

3.5.4 Le tri à bulles

Il s’agit d’une méthode de tri dont l’intérêt est plutôt anecdotique, ce tri n’étant intéressant ni du point de vue du nombre de comparaisons, ni du point de vue du nombre d’échanges. L’idée est de parcourir le tableau et d’échanger deux éléments consécutifs dès qu’ils sont dans l’ordre contraire de l’ordre souhaité. On itère ce parcours tant qu’un échange a été effectué au cours du balayage. Lorsque plus aucun échange n’est effectué, c’est que le tableau est trié. On peut écrire une procédure Caml sous la forme d’une fonction parcours qui retourne true si un échange a été effectué au cours du parcours et d’une fonction de tri qui se contente d’appeler la fonction de parcours tant que celle ci retourne qu’un échange a été effectué.


let tri_bulles a =  
    let y_a_echange = ref false and N = (vect_length a)-2 in  
         let parcours() =  
           begin  
             y_a_echange := false;  
             for i = 1 to N-1 do  
               if a.(i)>a.(i+1) then  
                  begin  
                    echange a i (i+1);  
                    y_a_echange := true  
                  end  
              done;  
              !y_a_echange  
            end  
         in  
           while parcours() do () done;;


Programme 3.51: tri à bulles

Remarque  Le nom de tri à bulles provient de ce que les éléments les plus petits remontent au fur et à mesure des échanges vers l’origine du tableau, de la même façon que les bulles d’un élément plus léger remontent vers la surface d’un élément plus lourd.

La présence de la boucle booléenne montre que le nombre de comparaisons et d’échanges dépend de manière essentielle de la distribution des éléments. Dans le cas le plus favorable d’un tableau déjà trié, il y aura un seul parcours et donc N - 1 comparaisons et aucun échange. Au contraire, dans le cas d’un tableau ordonné par ordre décroissant, il y aura (N - 1)2 comparaisons et autant d’échanges.

En fait, on peut simplifier la procédure de tri à bulles en faisant la remarque suivante : lors du premier parcours du tableau, le plus grand élément du tableau va s’échanger avec tous les éléments consécutifs jusqu’à parvenir à la dernière position à la fin du parcours. A partir de là, cet élément ne va plus intervenir (et donc n’a plus à être considéré dans les comparaisons) ; au cours du second parcours, c’est l’élément suivant en taille qui va s’enfoncer dans les profondeurs du tableau, jusqu’à parvenir à l’avant dernière position, et ainsi de suite. Ceci permet d’écrire le tri à bulles sous la forme


let tri_bulles a =  
    let N = (vect_length a)-2 in  
       for i = N downto 1 do  
          for j = 2 to i do  
             if a.(j-1)>a.(j) then  
                  echange a (j-1) j  
          done  
       done;;  
 
let v = hasard_vect 15 15 in  
         tri_bulles v;  
         v;;  
#tri_bulles : int vect -> unit = <fun>  
#- : int vect = [|0; 0; 0; 1; 5; 9; 9; 10;  
          11; 11; 11; 13; 13; 13; 14; 14; 0|]


Programme 3.52: simplification du tri à bulles

Sous cette forme on constate que le tri à bulles procède de la même façon que le tri par sélection, mais en commençant par les éléments les plus grands. Il opère le même nombre de comparaisons N (N - 1)∕2 mais un nombre beaucoup plus grands d’échanges (encore N (N - 1)∕2 dans le cas le plus défavorable d’un tableau trié à l’envers, au lieu des N échanges du tri par sélection). En conclusion, le tri à bulles est de peu d’intérêt et on peut toujours lui préférer un tri par sélection.

3.5.5 Méthodes performantes de tri

Nous verrons dans les autres chapitres des méthodes de tri de performances supérieures (tout au moins pour les gros tableaux) :

Ceci ne veut pas dire que le tri par sélection ou le tri par insertion soient à négliger. D’une part ils sont faciles à programmer et, pour des tableaux de petite taille, sont parfois plus rapides que les méthodes plus sophistiquées. Signalons également une variante plus performante du tri par insertion appelée le Shell sort qui procède en triant les éléments de p en p en utilisant une suite décroissante bien choisie d’entiers p : sa complexité est en N32 dans le cas le plus défavorable et n’est pas connue dans le cas moyen.