Algorithmique & Structures de Données 1 Ch 8 : La récursivité

LA RECURSIVITÉ

1. Introduction
L’algorithmique présentée jusqu’à maintenant peut être qualifiée d’élémentaire, car elle décrit des
processus de traitement et les modèles de données relativement traditionnels dans la plupart des
langages.
Ce chapitre débute une deuxième approche de traitements, consacrée à la description de concepts et
de méthodes purement algorithmiques, avec l’étude des traitements récursifs. Cette partie fait appel
à des notions et à des raisonnements plus abstraits.
La récursivité est un domaine très intéressant de l’informatique, un peu abstrait, mais très élégant ;
elle permet de résoudre certains problèmes d’une manière très rapide, alors que si on devait les
résoudre de manière itérative, il nous faudrait beaucoup plus de temps et de structures de données
intermédiaires.
2. Principe
La conception des algorithmes présentés jusque là s’appuie sur la méthode itérative, basée sur les
boucles, et qui décrit le calcul pas à pas. La récursivité propose une autre approche des traitements,
à la fois plus séduisante, plus simple à écrire, mais souvent plus complexe à concevoir.
La description d’un calcul basé su la méthode itérative définit un traitement élémentaire qui
progresse grâce à une boucle, du premier jusqu’au dernier calcul. A la fin de la boucle, le dernier
traitement donne le résultat final. Ainsi, le calcul de XN (le calcul itératif d’une puissance) se résume
à calculer x1, puis x 2, x ,3 … N fois. Il progresse à chaque nouvelle itération de la boucle, en réutilisant
le résultat de l’itération précédente et en le multipliant par x, ce qui correspond au calcul suivant :
xN = (… ( ( ( ( (x)*x)*x)*x)*x)*…)*x N fois

La récursivité propose une approche opposée. Le calcul final est exprimé en fonction du calcul
précédent, ce qui donne xN=x*xN-1. Avec cette méthode, le calcul se définit par lui-même : c’est la
notion de récursivité. Ce formalisme mathématique donne l’impression de ne pas avancer dans la
recherche de la solution, car si on connaît la valeur de x, on ne connaît pas celle de xN-1 ; en
poursuivant le raisonnement, on peut exprimer xN-1 comme égal à x*xN-2, et ainsi de suite, jusqu’à
obtenir x1=x. Ainsi, de proche en proche, le calcul devient :
1 1
xN = x*xN- = x*(x*x N-2) = x*( x *(x*x N-3)) = x*(x*(x*(…*(x*x )…)))

La comparaison entre ces deux méthodes est présentée à la figure ci dessous, qui décrit le calcul de
x4.

45
Algorithmique & Structures de Données 1 Ch 8 : La récursivité

Méthode itérative Méthode récursive

Calcul effectué Résultat final

1 * X * X * X * X X4 =

X0 * X X * X3

X1 * X X * X2

X2 * X X * X1

X3 * X X * X0

=X4 X * X * X * X * 1
Résultat final Calcul effectué

La méthode itérative utilise clairement une boucle. La valeur initiale (en dehors de la boucle) est 1,
soit x0.
La méthode récursive ne peut pas utiliser de boucle, puisque le calcul est exprimé en fonction d’un
autre qui n’est pas encore connu, sauf pour la création terminale (x1) dont on peut connaître la
valeur (la récursion terminale est la dernière étape du traitement récursif).
Le traitement est donc formalisé par une fonction (ou une procédure) qui décrit le calcul plutôt que
de le faire. On parle de fonction récursive car elle s’appelle elle-même. Le fonctionnement d’une
telle fonction se passe en deux phases : la descente en profondeur par appel récursifs, puis la
remontée du résultat de chaque appel (traitement différé). Voici le détail de ce fonctionnement sur
l’exemple du calcul de la puissance d’un nombre.
Le premier appel de la fonction puissance(x,N) effectue le calcul de x*puissance(x,N-1). Ce calcul
reste en « suspens », car il déclenche l’appel à la fonction puissance(x,N-1) qui effectue le calcul de
x*puissance(x,N-2). Ce calcul reste lui-même en attente du résultat du nouvel appel à la fonction
puissance(x,N-2), qui calcule x*puissance(x,N-3), etc. On voit que, s’il n’y a pas de boucle, il y a
bien une répétition de calculs par une suite d’appels en cascade de la même fonction avec des
exposants de plus en plus petits. Chaque appel est suspendu par un nouvel appel, dont il attend le
résultat. Si l’enchaînement des appels n’est pas contrôlé, on aboutit à une fonction récursive infinie
qui provoque un arrêt brutal du programme. Il faut donc prévoir le cas de la récursion terminale (cas
trivial), c'est-à-dire de l’appel dont le résultat est obtenu de manière itérative. Dans notre exemple,
cela se produit quand la puissance est égale à 1. Alors, le résultat de la fonction est x. La condition
terminale peut aussi correspondre à l’exposant 0, qui donne le résultat 1. Quand le « fond » des
appels récursifs est atteint (la récursion terminale donne un résultat et ne fait plus d’appel), l’appel
le plus profond se termine et retourne son résultat à l’appel précèdent. Cet appel, qui était en attente
46
Algorithmique & Structures de Données 1 Ch 8 : La récursivité

d’un résultat, reçoit la valeur de retour, poursuit son calcul, et retourne son résultat à l’appel
précédent, qui repend le traitement suspendu et retourne son résultat, et ainsi de suite. Cette phase
constitue la remontée du résultat de chaque appel. Enfin, le premier appel reçoit le résultat final. Le
fonctionnement des appels récursifs, avec une phase de descente et une phase de remontée, est
présenté à la figure ci dessous, qui calcule x4. Pour simplifier la présentation, puissance(x,N) est
noté P(x,N).

L’élégance de cette méthode de programmation tient au fait que le calcul s’effectue de lui-même
avec, comme seules informations, la valeur de la récursion finale et la description du calcul. C’est à
la fois simple et puissant. Concevoir une fonction récursive suppose le respect de deux règles :
définir la récursion terminale et décrire la méthode de calcul à partir de la fonction elle-même.
Voici l’écriture de la fonction récursive puissance (x,N) :
Fonction puissance (x : réel ; N : entier) : réel
variable
résultat : réel
début
Si (N==1) alors
résultat←x
Sinon
résultat←x*puissance(x,N-1)
FinSi
puissance←résultat
fin

47
Algorithmique & Structures de Données 1 Ch 8 : La récursivité

 Diviser pour résoudre

La fonction récursive puissance() est dite simple, car elle s’appelle une seule fois. Il existe
d’autres modèles pour lesquels la fonction s’appelle plusieurs fois. C’est le cas des algorithmes de
type diviser pour résoudre, qui divisent l’ensemble des données en plusieurs parties (généralement
deux), et la fonction récursive contient deux appels récursifs appliqués au premier, puis au
deuxième sous-ensemble.
3. Les types de récursivité:
La récursivité directe ou simple :
Module récursif(paramètres)
Début
<action>
Récursif (paramètres changés)
<action>
Fin

La récursivité indirecte ou croisée :

Module récursif1(p. formels) Module récursif2(paramètres formels)
Début Début
……………….. …………………
récursif2(…………..) récursif1( ...................... )
………………… …………………
Fin récursif1 Fin récursif2
4. Transformer une boucle en un module récursif
Soit la fonction suivante qui calcule le pgcd de 2 nombres entiers
0) DEF FN pgcd(a,b :entier) :entier
1) Tant que (b<>0) faire
r a mod b
a b
br
Fin tant que
2) pgcda
3) Fin pgcd
 Déterminer la condition de terminaison (b=0)
 Si (b=0), la fonction retourne a et le traitement s’arrête.
 Sinon, calculer la pgcd non pas avec les paramètres (a,b) mais avec (b, a mod b), c’est
l’appel récursif.
On aura donc la fonction récursive suivante :

48
 Algorithmique & Structures de Données 1 Ch 8 : La récursivité

0) DEF FN pgcd(a,b :entier) :entier

1) Si (b=0) alors
Pgcda
Sinon
Pgcdpgcd(b,a mod b)
FinSi
2) Fin pgcd
5. Pile et récursivité :
Le concept de récursivité a un effet sur la gestion de la mémoire centrale pour le langage de
programmation utilisé. Chaque langage de programmation qui, permet l'emploi de procédures et de
fonctions récursives, utilise au niveau de la mémoire centrale une pile des états actifs, appelée parfois
plus simplement "pile du système".
On appelle pile un tableau où la dernière information entrée est aussi la première à sortir. En termes
informatiques on parle d'une liste LIFO (Last-In-First-Out).

La pile du système
A chaque appel récursif d'un sous-programme on attribue un niveau de récursivité et on appelle
profondeur de récursivité le nombre maximum d'appels récursifs d'un sous programme. Lors des
appels récursifs, le compilateur doit se rappeler exactement où il en était à chaque niveau en
stockant les informations nécessaires dans la pile. La pile garde donc trace de l'état de chaque
variable de chaque sous-programme rendu actif dans un programme à un moment donné. Ces états
de variables portent le nom générique de contextes. Quand une procédure P est appelée, son
contexte est placé sur le dessus de la pile (empilé) {des contextes résultant d'appels antérieurs de
sous-programmes peuvent être déjà présents dans la pile}. A la fin de l'exécution de la procédure P,
son contexte doit se trouver de nouveau au sommet de la pile.
Le contexte de P relatif à cet appel est alors dépilé et l'exécution du programme continue à la ligne
d'invocation originale. Cette adresse de retour a été empilée juste avant le contexte de P au moment
de l'appel de la procédure.
Remarque : si le nombre d'appels récursifs est important, il peut y avoir un dépassement de
capacité de mémoire provoquant ainsi un arrêt de l'exécution du programme.
Seuls les problèmes dont la solution se base sur une relation de récurrence avec une condition de
sortie peuvent être résolus de façon récursive.

49
Algorithmique & Structures de Données 1 Ch 8 : La récursivité

6. Algorithmes récursifs
Tri Fusion
Avant de traiter, ce principe de tri on doit traiter l’algorithme qui permet de fusionner deux tableaux
triés dans un troisième. Le principe de ce tri, consiste à fusionner deux tableaux triés pour former un
troisième encore trié en effet un tableau qui contient un seul élément est un tableau trié, donc on
peut prendre deux élément comme deux tableaux triés et on les fusionne pour former un troisième
trié et on remonte jusqu’à trier tous les éléments du tableau.
Procedure TriFusion(var T:Tab;deb,fin:entier)
variable
I1,I2,IFu,i,milieu:entier
début
Si (deb <> fin) alors
milieu←(fin+deb)div 2
TriFusion(T,deb,milieu)
TriFusion(T,milieu+1,fin)
Pour i de deb à milieu faire
tabinter[i-deb+1] ←T[i]
FinPour
I1←deb
I2←milieu+1
IFu←deb
TQ(I1<=milieu) et (I2<=fin) faire
Si(tabinter[I1-deb+1]<T[I2]) alors
T[IFu] ←tabinter[I1-deb+1]
I1←I1+1
Sinon
T[IFu] ←T[I2]
I2←I2+1
FinSi
IFu←IFu+1
FinTQ
TQ(I1<=milieu)faire
T[IFu] ←tabinter[I1-deb+1]
I1←I1+1
IFu←IFu+1
FinTQ
TQ(I2<=fin) faire
T[IFu] ←T[I2]
I2←I2+1
IFu←IFu+1
FinTQ
FinSi
Fin

50
Algorithmique & Structures de Données 1 Ch 8 : La récursivité

Le tri rapide
Le tri rapide, aussi appelé QuickSort, est probablement l’algorithme de tri le plus employé de tous.
Il possède trois qualités fondamentales : il est performant dans de nombreux cas, il effectue un tri
sur place, donc sans allouer d’espace mémoire supplémentaire, et il est facile à écrire. L’algorithme
de base a été découvert par C.A.R. Hoare en 1960. Il a depuis reçu quelques petites modifications
qui améliorent encore ses performances.
Ce tri fonctionne sur le modèle « diviser pour résoudre ». Il partitionne l’ensemble des données en
deux sous-ensembles, qui sont eux-mêmes triés indépendamment. C’est donc un algorithme
récursif. La procédure de partitionnement est la principale tâche de cet algorithme.
Elle utilise l’un des éléments de la liste comme valeur pivot. Elle bascule ensuite les éléments qui
lui sont supérieurs et qui sont situés à sa droite dans la partition de droite, et les éléments qui lui
sont inférieurs et qui sont situés à sa droite dans la partition de gauche. Ainsi, à la fin du
partitionnement, la valeur pivot est sa place définitive. La partition de gauche ne contient que des
valeurs plus petites que le pivot, et celle de droite, que des valeurs plus grandes. Le choix de la
valeur pivot est donc capital. On appelle récursivement la procédure de tri sur la partition de gauche
et sur la partition de droite. La condition récursive terminale est atteinte quand il n’y a plus qu’une
seule valeur dans la partition. Le tableau est alors trié.
 Segmentation :
L’algorithme de segmentation, permet de partitionner le tableau en deux parties. La partie gauche
contient tous les éléments inférieurs ou égaux au pivot choisi (X) et la partie droite contient tous les
éléments supérieurs ou égaux au pivot. Le pivot choisi est l’élément existant en milieu du tableau.
Lors du partitionnement on utilise deux compteurs un initialisé à la première position (gauche) et
l’autre à la dernière case (droite). Après, on commence à parcourir la partie gauche du tableau en
incrémentant le compteur lorsque on trouve un élément inférieur au pivot. La boucle s’arrête en
trouvant un élément supérieur ou égal. Le compteur droite se décrémente lorsqu’ il trouve un
élément supérieur au pivot, la boucle s’arrête en trouvant un élément inférieur ou égal à X. L’étape
suivante est une permutation des éléments indexés par les compteurs gauche et droite. Ce
paragraphe discute certaines questions qui se posent en examinant la solution de l’algorithme.
1- Pourquoi TQ(T[gauche]<x) et non pas TQ(T[gauche]<=x) ?

Le choix de < et non pas ≤ est vérifié. En effet, le pivot x joue le rôle d’une sentinelle car
l’incrémentation du compteur gauche ne peut pas dépasser la longueur du tableau. Donc
l’élément X joue le rôle d’un mur car quand le compteur gauche atteint un élément égal à X la
condition n’est pas vérifiée et la boucle s’arrête. De plus, on est sûr que le compteur gauche
doit passer par le pivot X car X c’est un élément appartenant au tableau d’où la boucle while ne
peut pas être infinie.
2- Pourquoi si(gauche<=droite) et non pas si(gauche<droite)?

Cette question se pose lorsqu’ on remarque que le traitement est une permutation. Donc
pourquoi permuter lorsqu’on a gauche=droite ? La réponse que c’est inutile. Mais pourquoi

51
Algorithmique & Structures de Données 1 Ch 8 : La récursivité

donc ≤ ? La réponse c’est pour passer par les instructions gauche++ et droite--. Donc
pourquoi incrémenter gauche et décrémenter droite lorsque gauche=droite ?
Pour répondre à cette question on doit comprendre dans quel cas gauche = droite. Les deux
compteurs sont égaux lorsque tous les deux sont pointés sur un élément égal au pivot. Donc ils
doivent surmonter l’élément pivot ou on tombe dans une boucle infinie car les deux boucles
while ne peuvent pas dépasser cet élément (égal au pivot x).
3- Pourquoi itérer une autre fois si gauche= droite ?

Pour la simple raison, c’est qu’on doit surmonter l’élément pivot en exécutant les instructions
gauche++ ; et droite -- ; existants dans le traitement de si.
Procedure Segmentation(var T:Tab;n:entier)
variable
x,gauche,droite,inter:entier
début
gauche←1
droite ← n
x←T[(gauche+droite)div 2]
répéter
TQ (T[gauche]<x) faire gauche←gauche+1 finTQ
TQ(T[droite]>x) faire droite←droite-1 finTQ
Si(gauche<=droite) alors
inter←T[gauche]
T[gauche] ←T[droite]
T[droite] ←inter
gauche←gauche+1
droite←droite-1
finSi
jusqu’à (gauche>droite)
fin

 Tri Rapide
Il est clair qu’on doit traiter le problème de segmentation avant de traiter le problème du tri rapide.
Le traitement de la segmentation s’arrête avec ces deux cas possibles des compteurs gauche et
droite.

Où pivot

droite gauche droite gauche

C'est-à-dire on a dans les deux cas possibles tous les éléments qui existent avant le compteur droite
sont inférieurs ou égaux au pivot et les éléments existants à droite du compteur gauche sont
supérieurs ou égaux au pivot. On remarque bien que dans le deuxième cas le pivot occupe sa place
finale.

52
Algorithmique & Structures de Données 1 Ch 8 : La récursivité

Donc il suffit maintenant de segmenter la partie gauche existante entre le premier élément et
l’élément d’indice droite et la partie droite existante entre l’élément d’indice gauche et le dernier
élément de la série.
Procedure permuter(var e1:entier;var e2:entier)
variable
inter: entier
début
inter←e1
e1←e2
e2←inter
fin
Procedure TriRapide(var T:Tab;g,d:entier)
variable
x,gauche,droite:entier
début
gauche←g
droite←d
x←T[(gauche+droite)div 2]
répéter
TQ (T[gauche]<x) faire gauche←gauche+1 FinTQ
TQ(T[droite]>x) faire droite←droite-1 FinTQ
Si(gauche<=droite) alors
permuter(T[gauche],T[droite])
gauche←gauche+1
droite←droite-1
FinSi
jusqu’à (gauche>droite)
Si(g<droite) alors
TriRapide(T,g,droite)
FinSi
Si(d>gauche) alors
TriRapide(T,gauche,d)
FinSi
Fin

53
Algorithmique & Structures de Données 1 Ch 8 : La récursivité

La Tour De Hanoi
 Présentation

Les Tours de Hanoi sont un jeu constitué de trois tours symbolisées par des piquets, sur les quels
sont enfilés des disques de tailles différentes, qui forment une pyramide cylindrique. Le nombre de
disques est défini au début de la partie, et il est de trois minimums. Le but du jeu est de déplacer la
pyramide située initialement sur la tour 1 vers la tour 3, comme le montre la figure 2 qui présente la
position initiale et la position finale avec trois disques.
Chaque phase de jeu ne déplace qu’un seul disque à la fois, d’une tour vers une autre en respectant
l’ordonnancement des disques, du plus petit (en haut) vers le plus grand (en bas), sur chaque piquet.
Il est donc interdit de déplacer un disque plus grand (en bas), sur chaque piquet. Il est donc interdit
de déplacer un disque plus grand vers une tour contenant en haut de la pile un disque plus petit.
Voici un exemple de début du jeu : déplacer le premier disque de la tour 1 vers la tour 2, déplacer le
premier disque de la tour 3 vers la tour 2. Cette suite d’actions équivaut à déplacer les deux
premiers disques de la tour 1 vers la tour 2, en respectant les règles indiquées précédemment.
Il s’agit d’un jeu de réflexion dont voici la règle. Des anneaux de diamètres différents sont empilés
sur un poteau. Un anneau peut être empilé sur un autre seulement s’il a un diamètre inférieur à celui
de l’anneau sur lequel il repose.
Figure 1
Description de la règle.

Correct Interdit
Le but de jeu est de déplacer les anneaux initialement empilés sur un seul poteau vers un autre en
respectant les règles et en n’utilisant qu’un seul poteau intermédiaire.
Figure 2
Principe du jeu des
Tours de Hanoi.

54
Algorithmique & Structures de Données 1 Ch 8 : La récursivité

 Solution :
Les poteaux sont représentés par des piles d’entiers numérotées 0, 1 et 2. Le jeu entier sera alors
représenté par un tableau t de trois piles. On suppose qu’il y a n anneaux dans le jeu. On attribue à
chaque anneau un numéro de manière à ce que si l’anneau a est plus petit que l’anneau b, alors son
numéro est plus petit. Au départ, on aura donc :

Voici maintenant la fonction qui réalise le déplacement des anneaux du poteau numéro a au poteau
numéro b (on déduit le numéro du poteau intermédiaire c par la formule c=3-a-b). Cette fonction est
récursive. S’il y a un seul anneau, on le déplace directement, sinon on déplace les n-1 premiers
anneaux sur le poteau intermédiaire c (appel récursif à la fonction) et le dernier anneau sur le poteau
final b (appel récursif à la fonction). Ensuite, on déplace les anneaux du poteau intermédiaire c sur
le poteau final a (appel récursif à la fonction). Voici une illustration.

1 3

Voyons maintenant la programmation de cet algorithme.

Nous allons d’abord étudier deux cas concrets de déplacement : d’abord on observe, ensuite on
programme l’algorithme.
 Soit deux disques à déplacer du piquet 1 vers le piquet 3.
Le piquet final est 3, celui initial est 1, donc celui intermédiaire est 2.
Opérations de déplacement :
- disque 1 de piquet 1 vers piquet 2
- disque 2 de piquet 1 vers piquet 3  milieu
- disque 1 de piquet 2 vers piquet 3
 Soit trois disques à déplacer du piquet 1 vers le piquet 3.
Le piquet final est 3, celui initial est 1, donc celui intermédiaire est 2.
Maintenant on doit se retrouver avec les deux premiers disques sur le piquet 2, de façon à pouvoir
déplacer le disque 3 vers le piquet 3 et ensuite les deux premiers du piquet 2 vers le piquet 3.

55
Algorithmique & Structures de Données 1 Ch 8 : La récursivité

Opérations de déplacement :
- disque 1 de piquet 1 vers piquet 3
- disque 2 de piquet 1 vers piquet 2
- disque 1 de piquet 3 vers piquet 2
- disque 3 de piquet 1 vers piquet 3  milieu
- disque 1 de piquet 2 vers piquet 1
- disque 2 de piquet 2 vers piquet 3
- disque 1 de piquet 1 vers piquet 3
En regardant bien les déplacements effectués, on constate les choses suivantes :
- si on a « n » disques à déplacer :
o on déplace « n-1 » disques vers le piquet intermédiaire.
o On déplace le disque « n » du piquet initial vers le piquet final  milieu
o On déplace les « n-1 » disques du piquet intermédiaire vers le piquet final.

Algorithme tour_hanoi
procedure hanoi(nb_disques,depart,arrive:entier)
variable
intermediaire:entier
début
Si nb_disques=1 alors
Ecrire('On déplace un disque de ',depart, ' vers ',arrive)
Sinon
intermediaire←3-depart-arrive
hanoi(nb_disques-1,depart,intermediaire)
Ecrire('On deplace un disque de ',depart,' vers ',arrive)
hanoi(nb_disques-1,intermediaire,arrive)
FinSi
Fin

début
{ déplacement de 5 tours du piquet n°0 vers le piquet n°2 }
hanoi(5,0,2)
Fin

56