Récursivité & Paradigme Diviser pour Régner

CHAPITRE II:
1

La récursivité et Le paradigme
Diviser pour Régner
1. Introduction
La récursivité fournit un moyen simple et propre d’écrire du code. C' est un concept général
qui peut être illustré dans quasiment tous les langages de programmation, et qui peut être utile
dans de nombreuses situations.
L’objectif de ce premier chapitre est d’introduire la notion de récursivité et de présenter le
paradigme Diviser pour Régner.

2. La récursivité
2.1 Définition d'un sous-programme récursif
Un sous-programme est dit récursif si durant son exécution, il fait appel à lui même pour
continuer son exécution. Chaque appel à la fonction est indépendant des autres, avec ses
propres variables. Dans ce cas, la solution du problème général demande la résolution de
plusieurs sous-problèmes particuliers qui sont semblables au premier problème.

L'exemple le plus classique d'emploi de la récursivité est l'écriture de la fonction factorielle.

Pour rappel, la factorielle d'un nombre n est définie comme n fois la factorielle du
nombre n-1, et la factorielle de 1 est 1. Ainsi, pour résoudre le problème « combien vaut la
factorielle de 4 ?», il faut résoudre le problème « combien vaut la factorielle de 3 ?»…etc.

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.

La récursivité utilise toujours la Pile d’exécution du programme en cours qui est un

emplacement mémoire destiné à mémoriser les paramètres, les variables locales ainsi que
l’adresse de retour de chaque fonction en cours d’exécution. En effet, dans une procédure
récursive, toutes les variables locales sont stockées dans la pile, et empilées autant de fois
qu'il y a d'appels récursifs. Ces variables seront par la suite désempilées. La pile fonctionne

Dr KHAMTACHE-KHOULALENE Nadjet
 Récursivité & Paradigme Diviser pour Régner

selon le principe LIFO (Last-In-First-Out) et elle a une taille fixée (une mauvaise utilisation
2
de la récursivité peut entraîner un débordement de pile).

2.2 Ecriture d’un sous-programme récursif

Pour écrire un sous-programme récursif, il faut que le problème que l'on doit
résoudre se prête bien à l'utilisation d'un sous-programme récursif.
Tout sous-programme récursif comporte une instruction (ou un bloc d'instructions) nommée
"point terminal" ou "point d'appui" ou "point d'arrêt", qui indique que le reste des instructions
ne doit plus être exécuté.
La structure très nette des problèmes propres à la récursivité (un problème = un ou plusieurs
sous-problèmes) permet de présenter une manière générale d'écrire des sous-programmes
récursifs :
1. D'abord, il faut gérer le cas simple, c'est-à-dire celui qui ne nécessite pas de rappeler
récursivement le sous-programme. Pour la factorielle, c'est le cas où n vaut 1 (car on
sait directement que 1! = 1).
2. Ensuite, il faut gérer le ou les sous-problèmes récursifs, en rappelant le sous-
programme récursif pour chaque sous-problème à résoudre.

2.3 Différence entre les fonctions et procédures récursives

La seule différence qui existe entre les fonctions et les procédures récursives réside dans la
manière dont ce fait l’appel. Nous allons voir dans ce qui suit quelques exemples classiques
de fonctions et procédures récursives :

 Exemple 1 : calcul de la factorielle

1 𝒔𝒊 𝑛 = 0 𝑜𝑢 𝑛 = 1
𝑛! = {
𝑛 × (𝑛 − 1)! 𝒔𝒊𝒏𝒐𝒏
L'algorithme correspondant est le suivant:
Fonction Fact (n :entier) : entier ;
Début
Si (n=0) ou (n=1) Alors
Fact  1 ;
Sinon
Fact  n × Fact (n-1);
Fin;

Fin;

Dr KHAMTACHE-KHOULALENE Nadjet
 Récursivité & Paradigme Diviser pour Régner

Déroulement:
3
XFact(4)

4×Fact(3)
24
3×Fact(2)

24 2×Fact(1)

6 1

 Exemple 2 : calcul du nombre d’occurrences d’une valeur donnée dans un tableau

d’entiers
L'algorithme correspondant est comme suit:

Algorithme Calcul ;
Type Tab= Tableau [1..50] d’entiers ;
Var A : Tab ;
i, n, Nbre, Val : entier ;

Procédure Occurrence (A : Tab ; Var Nbre : entier ; i, n, val : entier) ;

Début
Si (i≤n) Alors
Si (A[i]=Val) Alors
Nbre Nbre+ 1;
Fin;
Occurrence (A, Nbre, i+1, n, val) ;
Fin;
Fin;

Début {PP}
Lire (n) ;
Pour i allant de 1 à n Faire
Lire (A[i]) ;
Fin ;
Lire (val) ;
Nbre 0;
i 1;
Occurrence (A, Nbre, i, n, val) ;
Ecrire(Nbre) ;
Fin;

Dr KHAMTACHE-KHOULALENE Nadjet
 Récursivité & Paradigme Diviser pour Régner

Déroulement:
Soit le tableau A suivant:
4

5 12 14 12 7

On cherche le nombre d'occurrences de la valeur 12 dans le tableau A:

Occurrence (A, 0, 1, 5, 12)

Occurrence (A, 0, 2, 5, 12)

Occurrence (A, 1, 3, 5, 12)

Occurrence (A, 1, 4, 5, 12)

Occurrence (A, 2, 5, 5, 12)

Occurrence (A, 2, 6, 5, 12)

2
2.4 Types de récursivité
a) Récursivité simple : c'est une récursivité dans laquelle on trouve un seul appel récursif.

Exemple :
Soit la fonction Puissance (x,n). Cette dernière peut être définie récursivement comme
suit :
1 𝒔𝒊 𝑛=0
𝑋𝑛 = {
𝑥 × 𝑥 𝑛−1 𝒔𝒊 𝑛≥1
L’algorithme correspondant est :

Fonction Puissance (x, n :entier) : entier ;

Début
Si (n=1) Alors
Puissance  1 ;
Sinon
Puissance  𝑥 × Puissance(x,n-1);
Fin;
Fin;

Dr KHAMTACHE-KHOULALENE Nadjet
 Récursivité & Paradigme Diviser pour Régner

b) Récursivité multiple : C’est une récursivité contenant plus d’un appel récursif. 5
𝑝
Exemple : Calcul des combinaisons (𝐶𝑛 ) en utilisant la relation de Pascal.

𝑝 1 𝒔𝒊 𝑝 = 0 𝒐𝒖 𝑝 = 𝑛
𝐶𝑛 = { 𝑝 𝑝−1
𝐶𝑛−1 + 𝐶𝑛−1 𝒔𝒊𝒏𝒐𝒏

L’algorithme correspondant est :

Fonction Pascal ( n , p :entier) : entier ;

Début
Si (p=0) Ou (p=1) Alors
Pascal  1 ;
Sinon
Pascal  Pascal(n-1,p)+ Pascal(n-1,p-1);
Fin;
Fin;

c) Récursivité mutuelle : Des fonctions sont dites mutuellement récursives si elles

dépendent les unes des autres.

Exemple : Définition de la parité.

𝑉𝑟𝑎𝑖 𝒔𝒊 𝑛 = 0 𝐹𝑎𝑢𝑥 𝒔𝒊 𝑛 = 0
Pair (n) = { Impair (n) = {
𝐼𝑚𝑝𝑎𝑖𝑟 (𝑛 − 1) 𝑺𝒊𝒏𝒐𝒏 𝑃𝑎𝑖𝑟 (𝑛 − 1) 𝑺𝒊𝒏𝒐𝒏

Les algorithmes correspondant sont :

Fonction Pair ( n :entier) : Booléen; Fonction Impair ( n :entier) : Booléen;

Début Début

Si (n=0) Alors Si (n=0) Alors

Pair  Vrai ; Impair  Faux ;

Sinon Sinon

Pair  Impair(n-1); Impair  Pair(n-1);

Fin; Fin;

Fin; Fin;

Dr KHAMTACHE-KHOULALENE Nadjet
 Récursivité & Paradigme Diviser pour Régner

d) Récursivité imbriquée : Dans ce type de récursivité, les paramètres du sous-programme

récursif sont eux-mêmes récursifs. 6

Exemple : Fonction d’Ackermann

Cette fonction est définie comme suit :
𝑛+1 𝒔𝒊 𝑚 = 0
𝐴(𝑚, 𝑛) = { 𝐴 ( 𝑚 − 1,1 ) 𝒔𝒊 𝑚 > 0 𝑒𝑡 𝑛 = 0
𝐴(𝑚 − 1, 𝐴(𝑚, 𝑛 − 1)) 𝑺𝒊𝒏𝒐𝒏

L’algorithme correspondant est :

Fonction Ackermann ( m , n:entier) : entier ;

Début
Si (m=0) Alors
Ackermann n+ 1 ;
Sinon
Si ( 𝑚 > 0) 𝑒𝑡 (𝑛 = 0) 𝐀𝐥𝐨𝐫𝐬
Ackermann  Ackermann (𝑚 − 1,1);
Sinon
Ackermann  Ackermann (m-1, Ackermann(m,n-1));
Fin;
Fin;
Fin;

2.5 Récursivité terminale et Récursivité non terminale

a) Récursivité terminale
Un algorithme est dit récursif terminal s’il ne contient aucun traitement après un appel
récursif. C’est une récursivité dont l’appel récursif est la toute dernière instruction réalisée.
En d’autres termes, aucun traitement n’est effectué à la remontée d’un appel récursif sauf le
retour de la valeur.
Exemple : Appel initial : 'Fact1 (n, 1)'

Fonction Fact1 (n, Resultat : Entier) : Entier ;

Début
Si (n=1) Alors
Fact1 Resultat ;
Sinon
Fact1 Fact1 (n-1, n×Resultat) ;
Fin ;
Fin ;

Dr KHAMTACHE-KHOULALENE Nadjet
 Récursivité & Paradigme Diviser pour Régner

b) Récursivité non terminale

Un algorithme est dit récursif non terminal s’il contient un traitement après un appel 7
récursif.

Exemple : Appel initial : 'Fact1 (n, 1)'

Fonction Fact2 (n : Entier) : Entier ;

Début
Si (n=1) Alors
Fact2 1;
Sinon
Fact2 n× Fact2 (n-1) ;
Fin ;
Fin ;

Ainsi, au lancement de la fonction, on aura :

 Une descente récursive (mémoriser les opérations à faire jusqu’à la condition d’arrêt),
 Condition terminale,
 Une remontée récursive (Réaliser les opérations en partant de la condition d’arrêt).

3. Le paradigme Diviser pour Régner

3.1 Définition

Diviser pour régner (divide-and-conquer en Anglais) est une technique permettant de

construire des algorithmiques récursifs. La stratégie consiste à découper le problème en sous-
problèmes similaires (d’où l’algorithme récursif résultant) dans l’espoir d’affaiblir ou de
casser la difficulté du problème initial.

L’archétype d’un algorithme résultant de cette approche est sans doute le tri-fusion: On
découpe le tableau de taille n en deux sous-tableaux de taille n/2 et l’on tri chacun
récursivement. Ils sont ensuite recombinés (d’où le terme de fusion) pour obtenir un tableau
entièrement trié.

L'algorithme du Tri par fusion est présenté ci-dessous:

Dr KHAMTACHE-KHOULALENE Nadjet
 Récursivité & Paradigme Diviser pour Régner

Procédure triFusion(var A : Tableau [1..50] d’entiers, début, fin : Entier) ;

8
Variables milieu : entier
Début
Si (début < fin) Alors
milieu ←(début + fin) div 2 ;
triFusion(A, début, milieu) ;
triFusion(A, milieu+1, fin) ;
fusion(A,debut,milieu,fin) ;
FinSi ;
Fin ;
Il faut noter que c’est en fait la fusion qui trie le tableau. Les appels récursifs n’ont pas pour
effet d’ordonner les éléments. Au mieux ils modifient les indices du début et de la fin des
sous-tableaux à trier ce qui virtuellement découpe le tableau en sous-tableaux de plus en plus
petits. La fonction de comparaison de deux éléments n’est présente que dans la fonction
fusion() dont le code est donner ci-dessous:

Procédure Fusion(var A : Tableau [1..50] d’entiers; début, milieu, fin : entier) ;

Variables i, i1, i2 : entier ; Tmp: Tableau [1..50] d’entiers ;

Début
i ←1 ; i1←début ; i2←milieu + 1 ;
Tantque (i1 <= milieu) et (i2 <= fin) Faire
Si A[i1] < A[i2] Alors
Tmp[i] ←A[i1] ;
i1 ← i1 +1 ;
Sinon
Tmp[i] ←A[i2] ;
i2 ← i2 + 1;
FinSi ;
i ←i + 1 ;
FinTantque ;

Tantque (i1 <= milieu) Faire

Tmp[i] ←A[i1] ; i ←i + 1 ; i1 ← i1+ 1 ;
FinTantque ;

Tantque (i2 <= fin) Faire

Tmp[i] ←A[i2] ; i ←i + 1 ; i2← i2 + 1 ;
FinTantque ;

A ← Tmp ; //Recopier Temp[i] dans A[i]

Fin ;

Dr KHAMTACHE-KHOULALENE Nadjet
 Récursivité & Paradigme Diviser pour Régner

Déroulement :
Soit à trier le tableau suivant : A [7, 14, 12, 4, 3, 20, 17, 1]
9

7 14 12 4 3 20 17 1

7 14 12 4
3 20 17 1

Division

17 1
7 14 12 4
3 20
A chaque étape, le
tableau est divisé en
2 jusqu’à l’obtention 12 4 3 17 1
7 14 20
d’un tableau de taille
1

7 14 4 12 3 20 1 17

A chaque étape, on
fusionne les sous- 4 7 12 14 1 3 17 20
tableaux de sorte à
avoir des sous-
tableaux triés Fusion

1 3 4 7 12 14 17 20

3.2 Forme générale d'un algorithme Diviser pour Régner et Théorème Maître
La forme générale d’un algorithme Diviser pour Régner est comme suit :

a) Diviser : en découpe le problème initial en 𝒂 sous problème de taille 𝒏⁄𝒃 qui sont de
même nature avec 𝒂 ≥ 𝟏 𝒆𝒕 𝒃 > 1.
b) Régner: les sous-problèmes sont résolus récursivement.
c) Recombiner : on utilise les solutions des sous-problèmes pour reconstruire la solution
du problème initial.

Dr KHAMTACHE-KHOULALENE Nadjet
 Récursivité & Paradigme Diviser pour Régner

3.3 Master Theorem

La complexité en temps T (n) d’un algorithme de type Diviser pour Régner peut
10

s’exprimer par une équation de récurrence qui est comme suit :

𝒏
𝑻(𝒏) = 𝑫(𝒏) + 𝒂 𝑻 ( ) + 𝑪(𝒏)
𝒃
Avec :
 𝑫(𝒏) le coût de la division
 𝑪(𝒏) le coût la reconstitution

𝑛
On pose 𝑓(𝑛) = 𝐷(𝑛) + 𝐶 (𝑛)  𝑇(𝑛) = 𝑎 𝑇 ( 𝑏 ) + 𝑓(𝑛)

Ainsi, T(n) peut être borné asymptotiquement comme suit :

 si 𝑓(𝑛) = 𝑂(𝑛(𝑙𝑜𝑔𝑏𝑎)−𝜀 ) pour une certaine constante 𝛆 >0 , alors 𝑇(𝑛) = Θ(𝑛𝑙𝑜𝑔𝑏𝑎 )
 si 𝑓(𝑛) = Θ(𝑛𝑙𝑜𝑔𝑏𝑎 ) alors 𝑇(𝑛) = Θ(𝑛𝑙𝑜𝑔𝑏𝑎 log 𝑛)
 si 𝑓(𝑛) = 𝛺(𝑛(𝑙𝑜𝑔𝑏𝑎)+𝜀 ) alors 𝑇(𝑛) = Θ(𝑓(𝑛))

Dans le cas de l’algorithme du tri par fusion :

𝑛
𝑇(𝑛) = 𝛩(1) + 2 𝑇 ( ) + 𝛩(𝑛)
2
Dans ce cas 𝑓 (𝑛) = 𝛩(𝑛) et peut être écrit sous la forme suivante:

𝑓 (𝑛) = 𝛩(𝑛𝑙𝑜𝑔2 2 )
On se retrouve alors dans le deuxième cas du master Theorem :

 𝑇(𝑛) = Θ(𝑛𝑙𝑜𝑔22 log 𝑛) = Θ(𝑛 log 𝑛)

4. Conclusion
La récursivité permet de réduire un problème à sa plus petite forme pour simplifier la
solution. L’avantage de la récursivité est qu’elle se situe à un niveau d’abstraction
supérieur par rapport à l’itération.
La technique « diviser pour régner » permet de construire des algorithmes récursifs
auxquels on ne pense pas forcément de prime abord. Par rapport à une approche naïve
(souvent itérative), ces algorithmes ne sont pas forcément meilleurs. Leur complexité peut
être aussi mauvaise. Pour obtenir un gain, il est nécessaire d’avoir recours à une « astuce »
de calcul permettant de combiner efficacement les solutions partielles (fusion). Idéalement
la fusion devrait être de complexité inférieure à la complexité globale recherchée.

Dr KHAMTACHE-KHOULALENE Nadjet