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
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
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.
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.
|
L’erreur à ne pas faire est d’actualiser systématiquement la valeur de la référence sous la forme
|
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.
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
|
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.
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
|
En ce qui concerne le produit de deux polynômes nous utiliserons le schéma de calcul suivant
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.
|
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.
|
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
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 :
|
et en Caml à :
|
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
|
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 :
|
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.
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
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 a≠0. 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
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 =
. Soit
Sn = 02 + 12 + … + n2 et soit P(n) le prédicat
Alors P(0) est vrai et si P(n) est vrai, alors
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 a≠0. 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.
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
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)nN 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.
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 :
|
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 :
|
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 :
|
|
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
|
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)
|
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.
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 :
|
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.
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)nN 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 :
|
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
si bien que Fn est équivalent, quand n tend vers + ∞à ωn+1 avec ω =
≈ 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.
|
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.
|
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
|
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
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
Munissons N2 de l’ordre lexicographique
On sait qu’il s’agit là d’un bon ordre. De plus il est clair que
Le principe d’induction généralisé nous montre que nous pouvons ainsi calculer le pgcd de deux entiers. Voici la fonction Caml correspondante :
|
Note de programmation Dans un moment de fatigue, l’auteur de ces lignes avait écrit
|
au lieu de
|
Pouvez vous deviner ce qui s’est passé ?
Eh bien, Caml interprétait évidemment la ligne comme
|
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
|
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
et en utilisant l’ordre lexicographique sur N2. Voici la fonction Caml correspondante :
|
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
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 :
|
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
|
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
|
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.
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
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)
Ainsi X est l’ensemble des mots comportant uniquement des parenthèses ouvrantes ou fermantes disposées de façon équilibrée ; par exemple
alors que ())()(X.
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,
alors X = ⋃
pNXp.
Démonstration: soit Y = ⋃
pNXp. 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(φ)
Xm où m = 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,
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
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.
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.
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
|
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 :
|
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
|
La factorielle correspond à la fonction f(n,x) = nx si bien que l’on obtient un calcul de la factorielle par :
|
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 :
|
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 :
|
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
|
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
|
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 …
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 → E′ dé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
|
Considérons d’autre part le sous programme prog2 défini par :
|
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 X≠E. 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.
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 → E′ dé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
|
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 E′ pour 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 :
|
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.
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 :
|
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 1…lim - 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 :
|
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 :
|
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.
|
et voici son application à un exemple avec les modifications successives du tableau
|
Théorème 3.5.1 Le tri par sélection trie un tableau de N éléments avec un nombre de
comparaisons équivalent à 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
Après exécution de la boucle externe, on a donc
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 =
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 à
et un nombre d’échanges qui est équivalent
à N.
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 :
|
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
|
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
|
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 =
~
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.
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é.
|
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
|
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 mais un nombre beaucoup plus grands d’échanges (encore
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.
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 N3∕2 dans le cas le plus défavorable et n’est pas connue dans le cas moyen.