Chapitre 3

La récursivité
Cliquezetpour
le paradigme « diviser
modifier le pour
style du régner »
titre

1. Récursivité
2. Dérécursivation
3. Diviser pour régner
I. Récursivité
1. Définition
Définition récursive, algorithme récursif.
Une définition récursive est une définition dans laquelle intervient ce que
l’on veut définir. Un algorithme est dit récursif lorsqu’il est défini en fonction
de lui-même.

Dans le cadre de ce cours, nous ne nous intéresserons qu’aux programmes et algorithmes récursifs.

Mais la notion de définition récursive est beaucoup plus générale :

en mathématiques : définition de l’exponentielle :

en programmation : définition en Ocaml d’une liste infinie dont tous les éléments valent 1 :

letrec z = 1::z ;

ENSAH Preuve d'un algorithme N. KANNOUF – page : 71

I. Récursivité
2. Récursivité simple
Revenons à la fonction puissance . Cette fonction peut être définie récursivement :

L’algorithme correspondant s’écrit :

PUISSANCE (x, n)

Si n = 0 alors renvoyer 1

sinon renvoyer x*PUISSANCE(x, n - 1)

ENSAH Preuve d'un algorithme N. KANNOUF – page : 72

I. Récursivité
3. Récursivité multiple
Une définition récursive peut contenir plus d’un appel récursif. Nous voulons calculer ici les
combinaisons en se servant de la relation de Pascal :

L’algorithme correspondant s’écrit :

COMBINAISON (n, p)

Si p = 0 ou p = n alors renvoyer 1

sinon renvoyer COMBINAISON (n-1, p) + COMBINAISON (n -1, p -1)

ENSAH Preuve d'un algorithme N. KANNOUF – page : 73

I. Récursivité
4. Récursivité mutuelle
Des définitions sont dites mutuellement récursives si elles dépendent les unes des autres. Ça
peut être le cas pour la définition de la parité :

L’algorithme correspondant s’écrit :

ENSAH Preuve d'un algorithme N. KANNOUF – page : 74

I. Récursivité
5. Récursivité imbriquée
La fonction d’Ackermann est définie comme suit :

D’où l’algorithme:
ACKERMANN(m, n)
si m = 0
alors n+1
sinon si n = 0 alors ACKERMANN(m - 1, 1)
sinon ACKERMANN(m-1, ACKERMANN(m, n-1))

En résumé : on peut utiliser la récursivité comme l’on veut, à peu près n’importe comment...

ENSAH Preuve d'un algorithme N. KANNOUF – page : 75

I. Récursivité
6. Principe et dangers de la récursivité
Principe et intérêt : ce sont les mêmes que ceux de la démonstration par récurrence en mathématiques.
On doit avoir :
– un certain nombre de cas dont la résolution est connue, ces « cas simples » formeront les
cas d’arrêt de la récursion ;
– un moyen de se ramener d’un cas « compliqué » à un cas « plus simple ».

La récursivité permet d’écrire des algorithmes concis et élégants.

Difficultés :
– la définition peut être dénuée de sens :
Algorithme A(n)
renvoyer A(n)
– il faut être sûrs que l’on retombera toujours sur un cas connu, c’est-à-dire sur un cas
d’arrêt ; il nous faut nous assurer que la fonction est complètement définie, c’est-à-dire,
qu’elle est définie sur tout son domaine d’applications.

ENSAH Preuve d'un algorithme N. KANNOUF – page : 76

I. Récursivité
6. Principe et dangers de la récursivité (suite)
Moyen : existence d’un ordre strict tel que la suite des valeurs successives des arguments invoqués par la définition soit
strictement monotone et finit toujours par atteindre une valeur pour laquelle la solution est explicitement définie.
L’algorithme ci-dessous teste si a est un diviseur de b.
DIVISEUR ( , )
Si ≤ 0 alors Erreur
sinon si ≥ alors = (test d’égalité)
sinon DIVISEUR( , – )
La suite des valeurs , − , – 2 × , etc. est strictement décroissante, car a est strictement positif, et on finit
toujours pas aboutir à un couple d’arguments ( , ) tel que − est négatif, cas défini explicitement.
Cette méthode ne permet pas de traiter tous les cas:
SYRACUSE(n)
Si = 0 = 1 alors 1
sinon si 2 = 0 alors SYRACUSE ( /2)
sinon SYRACUSE (3 + 1)
Problème ouvert : l’algorithme est bien défini et vaut 1 sur N.
Question : N’y a-t-il vraiment aucun moyen de déterminer automatiquement si un algorithme récursif quelconque va terminer ?

ENSAH Preuve d'un algorithme N. KANNOUF – page : 77

I. Récursivité
7. Non décidabilité de la terminaison
Question : peut-on écrire un programme qui vérifie automatiquement si un programme donné P termine quand il est
exécuté sur un jeu de données D ?
Entrée Un programme P et un jeu de données D.
Sortie vrai si le programme P termine sur le jeu de données D, et faux sinon.
Démonstration de la non décidabilité
Supposons qu’il existe un tel programme, nommé termine, de vérification de la terminaison. À partir de ce
programme on conçoit le programme Q suivant :
programme Q
résultat = termine(Q, ∅)
tant que résultat = vrai faire attendre une seconde fin tant que
renvoyer résultat
Supposons que le programme Q —qui ne prend pas d’arguments— termine. Donc termine(Q, ∅) renvoie vrai, la
deuxième instruction de Q boucle indéfiniment et Q ne termine pas. Il y a donc contradiction et le programme Q ne
termine pas. Donc, termine(Q, ∅) renvoie faux, la deuxième instruction de Q ne boucle pas, et le programme Q termine
normalement. Il y a une nouvelle fois contradiction : par conséquent, il n’existe pas de programme tel que termine, c’est-
à-dire qui vérifie qu’un programme termine ou non sur un jeu de données...
Le problème de la terminaison est indécidable !
ENSAH Preuve d'un algorithme N. KANNOUF – page : 78
I. Récursivité
8. Importance de l’ordre des appels récursifs
Fonction qui affiche les entiers par ordre décroissant, de n jusqu’à 1 :
DÉCROISSANT(n) Exécution pour n = 2 :
Appel de DÉCROISSANT(2)
Si n = 0 alors ne rien faire Affichage de 2.
sinon afficher n Appel de DÉCROISSANT(1)
Affichage de 1.
DÉCROISSANT(n - 1) Appel de DÉCROISSANT(0)
L’algorithme ne fait rien.
Résultat affichage d’abord de 2 puis de 1 : l’affichage a lieu dans l’ordre décroissant.

Intervertissons maintenant l’ordre de l’affichage et de l’appel récursif :

CROISSANT(n) Exécution pour n = 2 :
Appel de CROISSANT(2)
Si n = 0 alors ne rien faire Appel de CROISSANT(1)
sinon CROISSANT(n - 1) Appel de CROISSANT(0)
L’algorithme ne fait rien.
afficher n Affichage de 1.
Affichage de 2.
Résultat affichage d’abord de 1 puis de 2 : l’affichage a lieu dans l’ordre croissant.

ENSAH Preuve d'un algorithme N. KANNOUF – page : 79

I. Récursivité
9. Exemple d’algorithme récursif : les tours de Hanoï
Le problème
Le jeu est constitué d’une plaquette de bois où sont plantées trois tiges. Sur ces tiges sont enfilés des disques de
diamètres tous différents. Les seules règles du jeu sont que l’on ne peut déplacer qu’un seul disque à la fois, et qu’il
est interdit de poser un disque sur un disque plus petit.
Au début tous les disques sont sur la tige de gauche, et à la fin sur celle de droite.
Résolution (Méthode de résolution du jeu des tours de Hanoï)

ENSAH Preuve d'un algorithme N. KANNOUF – page : 80

I. Récursivité
9. Exemple d’algorithme récursif : les tours de Hanoï (suite)
Algorithme

Exécution avec trois disques

Il ne faut pas chercher à comprendre comment ça marche, mais pourquoi ça marche...

ENSAH Preuve d'un algorithme N. KANNOUF – page : 81

I. Récursivité
9. Exemple d’algorithme récursif : les tours de Hanoï (suite)
Complexité
On compte le nombre de déplacements de disques effectués par l’algorithme HANOÏ
invoqué sur n disques.

d’où l’on en déduit que C(n) = 2 − 1. On a donc ici un algorithme de complexité

exponentielle.

ENSAH Preuve d'un algorithme N. KANNOUF – page : 82

II. Dérécursivation

Dérécursiver, c’est transformer un algorithme récursif en un algorithme équivalent ne contenant pas

d’appels récursifs.

Récursivité terminale

Récursivité non terminale

Remarques

ENSAH Preuve d'un algorithme N. KANNOUF – page : 83

II. Dérécursivation
1. Récursivité terminale
Définition de la Récursivité terminale :
Un algorithme est dit récursif terminal s’il ne contient aucun
traitement après un appel récursif.
Exemple :
ALGORITHME P(U)
si C alors D;P( (U))
sinon T
où :
– U est la liste des paramètres ; Avec ces notations, l’algorithme P équivaut à
– C est une condition portant sur U ; l’algorithme suivant :
– D est le traitement de base de l’algorithme (dépendant de U) ; ALGORITHME P’(U)
– ( ) représente la transformation des paramètres ; tant que C faire D;U ← (U)
– T est le traitement de terminaison (dépendant de U). T
L’algorithme P’ est une version dérécursivée de
l’algorithme P.

ENSAH Preuve d'un algorithme N. KANNOUF – page : 84

II. Dérécursivation
2. Récursivité non terminale
Ici, pour pouvoir dérécursiver, il va falloir sauvegarder le contexte de l’appel récursif, typiquement les
paramètres de l’appel engendrant l’appel récursif. Originellement, l’algorithme est :

ALGORITHME Q(U)

si C(U) alors D(U);Q( (U));F(U)

sinon T(U)

Les piles sont des structures de stockage (via les primitives empiler et dépiler) qui fonctionnent sur le
principe « le dernier entré est le premier sorti ». Les compilateurs utilisent des piles pour stocker les
paramètres des appels de fonctions, et en particulier lors de la transcription des fonctions récursives. Nous
mimons ici l’utilisation des piles pour dérécursiver l’algorithme.

ENSAH Preuve d'un algorithme N. KANNOUF – page : 85

II. Dérécursivation
2. Récursivité non terminale (suite)
Après dérécursivation on obtiendra donc :

ENSAH Preuve d'un algorithme N. KANNOUF – page : 86

II. Dérécursivation L’exécution correspondante
de Q’ est présentée figure
2. Récursivité non terminale (suite) à gauche. Les instructions
de gestion de piles y
Illustration de la dérécursivation de l’algorithme Q figurent en italique, et les
instructions de
l’algorithme originel (ce
et Q’: qui nous importe) y
figurent en gras.
Exemple d’exécution de Q :

ENSAH Preuve d'un algorithme N. KANNOUF – page : 87

II. Dérécursivation
3. Remarques

Les programmes itératifs sont souvent plus efficaces, mais les programmes récursifs

sont plus faciles à écrire. Les compilateurs savent, la plupart du temps, reconnaître les

appels récursifs terminaux, et ceux-ci n’engendrent pas de surcoût par rapport à la

version itérative du même programme.

Il est toujours possible de dérécursiver un algorithme récursif.

ENSAH Preuve d'un algorithme N. KANNOUF – page : 88

III. Diviser pour régner
1. Principe

Nombres d’algorithmes ont une structure récursive : pour résoudre un problème donné, ils s’appellent
eux-mêmes récursivement une ou plusieurs fois sur des problèmes très similaires, mais de tailles
moindres, résolvent les sous-problèmes de manière récursive puis combinent les résultats pour trouver
une solution au problème initial.

Le paradigme « diviser pour régner » donne lieu à trois étapes à chaque niveau de récursivité :

Diviser : le problème en un certain nombre de sous-problèmes ;

Régner : sur les sous-problèmes en les résolvant récursivement ou, si la taille d’un sous-problème est
assez réduite, le résoudre directement ;

Combiner : les solutions des sous-problèmes en une solution complète du problème initial.

ENSAH Preuve d'un algorithme N. KANNOUF – page : 89

III. Diviser pour régner
2. Premier exemple : multiplication naïve de matrices
Nous nous intéressons ici à la multiplication de matrices carrés de taille n.

Algorithme naïf
L’algorithme classique est le suivant :

Cet algorithme effectue θ( !) multiplications et autant d’additions.

ENSAH Preuve d'un algorithme N. KANNOUF – page : 90

III. Diviser pour régner
2. Premier exemple : multiplication naïve de matrices (suite)
Algorithme « diviser pour régner » naïf
Dans la suite nous supposerons que n est une puissance exacte de 2. Décomposons les matrices A, B et
C en sous-matrices de taille = /2 × /2. L’équation = "# peut alors se récrire :

En développant cette équation, nous obtenons :

Chacune de ces quatre opérations correspond à deux multiplications de matrices carrés de taille /2 et
une addition de telles matrices. À partir de ces équations on peut aisément dériver un algorithme « diviser
pour régner » dont la complexité est donnée par la récurrence :

l’addition des matrices carrés de taille /2 étant en $( % ).

ENSAH Preuve d'un algorithme N. KANNOUF – page : 91

III. Diviser pour régner
3. Analyse des algorithmes « diviser pour régner »
Lorsqu’un algorithme contient un appel récursif à lui-même, son temps d’exécution peut souvent être
décrit par une équation de récurrence qui décrit le temps d’exécution global pour un problème de taille
en fonction du temps d’exécution pour des entrées de taille moindre.
La récurrence définissant le temps d’exécution d’un algorithme « diviser pour régner » se décompose
suivant les trois étapes du paradigme de base :
1. Si la taille du problème est suffisamment réduite, n ≤ c pour une certaine constante c, la résolution
est directe et consomme un temps constant $(1).
2. Sinon, on divise le problème en a sous-problèmes chacun de taille &⁄' de la taille du problème initial.
Le temps d’exécution total se décompose alors en trois parties :
a) *( ) : le temps nécessaire à la division du problème en sous-problèmes.
b) ,( ⁄') : le temps de résolution des a sous-problèmes.
c) ( ) : le temps nécessaire pour construire la solution finale à partir des solutions aux sous-problèmes.
La relation de récurrence prend alors la forme :

où l’on interprète ⁄' soit comme ⁄' , soit comme ⁄' .

ENSAH Preuve d'un algorithme N. KANNOUF – page : 92

III. Diviser pour régner
4. Résolution des récurrences
Théorème de la Résolution des récurrences « diviser pour régner »
Soient a ≥ 1 et b > 1 deux constantes, soit f (n) une fonction et soit T(n) une fonction définie
pour les entiers positifs par la récurrence :

, = aT( ⁄')+. ,

où l’on interprète ⁄' soit comme ⁄' , soit comme ⁄' .

T(n) peut alors être bornée asymptotiquement comme suit :

1. Si f (n) = O( (/012 3)45 ) pour une certaine constante 6 > 0, alors T(n) = $( (/012 3) ).

2. Si f (n) = $( /012 3 ), alors T(n) = $( (/012 3) 7 8 ).

3. Si f (n) = Ω( (/012 3):5 ) pour une certaine constante 6 > 0, et si a f ( ⁄') ≤ c f (n) pour
une constante c < 1 et n suffisamment grand, alors T(n) = $( f (n)).

ENSAH Preuve d'un algorithme N. KANNOUF – page : 93

III. Diviser pour régner
4. Résolution des récurrences (suite)
Remarques :
1. Le remplacement des termes T( ⁄') par T( ⁄' ) ou T( ⁄' ) n’affecte pas le comportement
asymptotique de la récurrence. On omettra donc en général les parties entières.

2. Le théorème de RRDR ne couvre pas toutes les possibilité pour f (n). Par exemple, il y a un « trou
» entre les cas 1 et 2 quand f (n) est plus petite que /012 3 , mais pas polynomialement. Dans un
tel cas, on ne peut tout simplement pas appliquer le théorème.

Retour sur le premier exemple

Utilisons le théorème RRDR pour calculer la complexité de notre algorithme de multiplication de

matrices « diviser pour régner » naïf. Ici, a = 8, b = 2 et f (n) = $( % ). Donc 7 8' = 3, nous nous
trouvons dans le cas 1 du théorème (avec 6 = 1), l’algorithme a une complexité en $( !) et nous
n’avons rien gagné...

ENSAH Preuve d'un algorithme N. KANNOUF – page : 94

III. Diviser pour régner
5. Deuxième exemple : algorithme de Strassen pour la multiplication de matrices
L’algorithme de Strassen est un algorithme « diviser pour régner » qui n’effectue que 7 multiplications
de matrices, contrairement à 8 dans l’algorithme précédent, mais qui effectue plus d’additions et de
soustractions de matrices, ce qui est sans conséquence une addition de matrices étant « gratuite » par
rapport au coût d’une multiplication.

Complexité

La complexité de l’algorithme de Strassen est donnée par la récurrence :

T(n) = 7T( ⁄%)+$( % ).

En utilisant le théorème RRDR, nous obtenons comme complexité : T(n) = $( /012 ; ) = O( %,<& ).

ENSAH Preuve d'un algorithme N. KANNOUF – page : 95

III. Diviser pour régner
5. Deuxième exemple : algorithme de Strassen pour la multiplication de matrices (suite)
Algorithme
Il se décompose en quatre étapes :

1. Diviser les matrices A et B en matrices carrés de taille ⁄%.

2. Au moyen de $( %) additions et soustractions scalaires, calculer 14 matrices (à préciser) A1, ...,

A7, B1, ..., B7 carrés de taille ⁄%.

3. Calculer récursivement les 7 produits de matrices => = "> × #> , ? ∈ 1; 7 .

4. Calculer les sous-matrices désirées r, s, t et u en additionnant et/ou soustrayant les combinaisons

idoines des matrices => ad-hoc, à l’aide de $( %) additions et soustractions scalaires.

ENSAH Preuve d'un algorithme N. KANNOUF – page : 96

III. Diviser pour régner
5. Deuxième exemple : algorithme de Strassen pour la multiplication de matrices (suite)
Produits de sous-matrices
Nous supposons que chaque matrice produit => peut s’écrire sous la forme :

=> = "> × #> = >,& + >,% + >,! C + >,D . E>,& F + E>,% . + E>,! 8 + E>,D ℎ ,

où les coefficients >,H et E>,H sont tous pris dans l’ensemble −1; 0; 1 . Nous supposons donc que chaque produit
peut être obtenu en additionnant et soustrayant certaines des sous-matrices de A, en additionnant et soustrayant
certaines des sous-matrices de B, et en multipliant les deux matrices ainsi obtenues.

Récrivons l’équation définissant r :

où « + » représente « +1 », « . » représente « 0 » et « - » représente « -1 ».

ENSAH Preuve d'un algorithme N. KANNOUF – page : 97

III. Diviser pour régner
5. Deuxième exemple : algorithme de Strassen pour la multiplication de matrices (suite)
Produits de sous-matrices
On remarque que l’on peut calculer s par s = P1 +P2
Nous récrivons de même les équations définissant s, t
où P1 et P2 sont calculées chacune au moyen d’une
et u : unique multiplication de matrice :

ENSAH Preuve d'un algorithme N. KANNOUF – page : 98

III. Diviser pour régner
5. Deuxième exemple : algorithme de Strassen pour la multiplication de matrices (suite)
Produits de sous-matrices
Pour calculer r et u on introduit une matrice P5 définie
De même la matrice t peut être calculée par t = P3+P4
comme suit :
avec :

et on cherche à obtenir r à partir de P5 :

ENSAH Preuve d'un algorithme N. KANNOUF – page : 99

III. Diviser pour régner
5. Deuxième exemple : algorithme de Strassen pour la multiplication de matrices (suite)
Produits de sous-matrices
De même, on cherche à obtenir u à partir de P5 :
D’où, en posant

on obtient r = P5 +P4 − P2 + P6.

D’où, en posant

on obtient u = P5+P1−P3−P7.
ENSAH Preuve d'un algorithme N. KANNOUF – page : 100
III. Diviser pour régner
5. Deuxième exemple : algorithme de Strassen pour la multiplication de matrices (suite)
Discussion

L’algorithme de Strassen n’est intéressant en pratique que pour de grandes matrices (n > 45) denses

(peu d’éléments non nuls).

La meilleure borne supérieure connue pour la multiplication de matrices carrés de taille n est environ

en O( %,!;I ). La meilleure borne inférieure connue est en Ω( %) (il faut générer % valeurs). On ne

connaît donc toujours pas le niveau de difficulté réel d’une multiplication de matrices !

ENSAH Preuve d'un algorithme N. KANNOUF – page : 101

 Fin de Séance
Cliquez pour modifier le style du titre