Chapitre iii récursivité et paradigme diviser pour régner

CHAPITRE III:

RÉCURSIVITÉ ET PARADIGME «

DIVISER POUR RÉGNER »

Université Saad Dahleb de Blida

Faculté des Sciences

Département d’Informatique

Licence Génie des Systèmes Informatique (GSI)

Semestre 5 (3ème année)

ALGORITHMIQUE 02

Cours n°3: 20 Octobre 2013

AROUSSI Sana

Disponible sur https://sites.google.com/a/esi.dz/s-aroussi/

https://sites.google.com/a/esi.dz/s-aroussi/



PLAN DU CHAPITRE III

Partie 1: La récursivité

Partie 2: La dérécursivation

Partie 3: La paradigme « Diviser pour régner »

2

PARTIE1: LA RÉCURSIVITÉ

PLAN DE LA PARTIE I

Définitions

Évolution d’un appel récursif

Types de la récursivité

Récursivité terminale vs non terminale

Complexité des algorithmes récursifs

Écrire un algorithme récursif

Exemple: Tours de Hanoi

4

5

Un algorithme est dit récursif s'il est défini en fonction de

lui-même.

DÉFINITIONS

Exemple : la factorielle n!

Itératif

n! = 1 * 2 * ... * n

Récursif

n! = n * (n-1)!

Facto (n: entier): entier

Début

F1;

Pour i2 à n faire

FF*i;

retourne F;

Fin


Début

retourne n*Facto (n-1);

Fin

6

L'exécution d'un appel récursif passe par deux phases, la

phase de descente et la phase de la remontée :

Dans la phase de descente, chaque appel récursif fait à son tour

un appel récursif.

ÉVOLUTION D’UN APPEL RÉCURSIF

Exemple : 4! = Facto(4)

Facto(4) 4 * Facto(3)




Facto(4) 0 * Facto(-1)

7

Puisqu'un algorithme récursif s'appelle lui-même, il est impératif

qu'on prévoit une condition d'arrêt à la récursion, sinon le

programme ne s'arrête jamais!

CONDITION D’ARRÊT

Exemple : la factorielle n!

Version précédente Version correcte


Début


Fin


Début

Si (n=1) alors retourne 1

Sinon retourne n*Facto (n-1);

Fin

8

En arrivant à la condition terminale, on commence la phase de la

remontée qui se poursuit jusqu'à ce que l'appel initial soit terminé,

ce qui termine le processus récursif.

ÉVOLUTION D’UN APPEL RÉCURSIF

Exemple :




24 24

1 1 2 2

6 6

Ph

ase

de l

a r

em

on

tée

Ph

ase

de l

a r

em

on

tée

9

1. La récursivité simple où l’algorithme contient un seul appel

récursif dans son corps.

Exemple : la fonction factorielle


Début

Si (n=1) alors retourne 1

Sinon retourne n*Facto (n-1);

Fin

TYPES DE RÉCURSIVITÉ

10

2. La récursivité multiple où l’algorithme contient plus d'un appel

récursif dans son corps

Exemple : le calcul du nombre de combinaisons en se servant de la

relation de Pascal :


11

3. La récursivité mutuelle: Des modules sont dits mutuellement

récursifs s’ils dépendent les unes des autres

Exemple : la définition de la parité d'un entier peut être écrite de la

manière suivante :


12

4. La récursivité imbriquée consiste à faire un appel récursif à

l'intérieur d'un autre appel récursif.

Exemple : La fonction d'Ackermann


13

Un module récursif est dit terminal si aucun traitement n'est effectué

à la remontée d'un appel récursif (sauf le retour du module).

Un module récursif est dit non terminal si le résultat de l'appel

récursif est utilisé pour réaliser un traitement (en plus du retour du

module).

RÉCURSIVITÉ TERMINALE VS NON TERMINALE

Récusivité non terminale Récursivité Terminal


Début

Si (n=1) alors

retourne 1

Sinon


Fin

Facto (n: entier, resultat: entier): entier

Début

si (n = 1) alors

retourne resultat;

sinon

retourne Facto (n-1, n * resultat);

Fin

// la fonction doit être appelée en mettant

resultat à 1

14

RÉCURSIVITÉ TERMINALE VS NON TERMINALE

Facto(4,1) Facto(3, 4*1)

Facto(3, 4) Facto(2, 3*4)

Facto(2, 12) Facto(1, 2*12)

Facto(1, 24)

15

La complexité d’un algorithme récursif se fait par la résolution

d’une équation de récurrence en éliminant la récurrence par

substitution de proche en proche.

Exemple : la fonction factorielle (T(n) le temps d’exécution nécessaire pour un

appel à Facto(n))


Début

Si (n=1) [O (1)] alors

retourne 1 [O (1)]

Sinon

retourne n*Facto (n-1); [T (n) dépend de T(n-1)]

Fin

COMPLEXITÉ DES ALGORITHMES RÉCURSIFS

n = 1

16

COMPLEXITÉ DES ALGORITHMES RÉCURSIFS

Pour calculer la solution générale de cette équation, on peut

procéder par substitution :

O (T) = O (n) O (T) = O (n)

17

Dans un module récursif (procédure ou fonction) les paramètres

doivent être clairement spécifiés

Dans le corps du module il doit y avoir:

un ou plusieurs cas particuliers: ce sont les cas simples qui ne

nécessitent pas d'appels récursifs

un ou plusieurs cas généraux: ce sont les cas complexes qui sont résolus

par des appels récursifs

L'appel récursif d'un cas général doit toujours mener vers un des cas

particuliers

ÉCRIRE UN ALGORITHME RÉCURSIF

18

EXEMPLE DES TOURS DE HANOI

Déplacer n disques (empilés les uns sur les autres) d'un piquet (A)

vers un autre piquet (B) en utilisant un troisième (C) comme

intermédiaire (ce sont des piles, on ne peut accéder qu'au

disque du sommet)

un disque ne peut jamais être placé au dessus d'un autre

plus petit

19

Il faut pouvoir exprimer :

« le déplacement de n disques » en fonction d'un ou de plusieurs «

déplacement de m disques » (avec m < n).

Par exemple (m=n-1) si on avait une solution pour déplacer n-1

disques, comment l'utiliser pour déplacer n disques ?


CONCEPTION DE LA SOLUTION RÉCURSIVE

20


CONCEPTION DE LA SOLUTION RÉCURSIVE

21


ALGORITHME INFORMEL

Pour Transférer n disques de A vers B avec C comme intermédiaire,

il faut :

Cas particulier (n = 1)

déplacer le disque de X vers Y.

Cas général (n > 1)

Transférer les n-1 premiers disques de A vers C, en utilisant B

comme intermédiaire

déplacer l'unique disque qui reste dans A vers B

Transférer les n-1 premiers disques de C vers B, en utilisant A

comme intermédiaire

22


ALGORITHME FINAL

Hanoi( n:entier; A,B,C : caractères )

SI ( n = 1 )

écrire(« déplacer un disque de », A, « vers », B );

SINON

Hanoi ( n-1, A, C, B );


Hanoi( n-1, C, B, A );

FSI

23


AUTRE VERSION

Hanoi( n:entier; A,B,C : caractères )

SI ( n > 0 )

Hanoi ( n-1, A, C, B );


Hanoi( n-1, C, B, A );

FSI

24


COMPLEXITÉ

Hanoi( n:entier; A,B,C : caractères ) [T(n)]

SI ( n > 0 )

Hanoi ( n-1, A, C, B ); [T(n-1)]

écrire(« déplacer un disque de », A, « vers », B ); [O(1)]

Hanoi( n-1, C, B, A ); [T(n-1)]

FSI

T(n) = 2*T(n-1) + a = 2 *(2*T(n-2) + a)+ a = 2*2T(n-2)+ 2a+ a

= ........

= 2n T(0) + (20+21+22+.......+ 2n-1) a

= 2n 0 + (2n -1) a

O (T) = 2 O (T) = 2n

PARTIE 2:

LA DÉRÉCURSIVATION

Cours n°4: 23 Octobre 2013

PLAN DE LA PARTIE II

Généralités

Élimination de la récursivité terminale simple

Élimination de la récursivité terminale multiple

Élimination de la récursivité non terminale simple

Élimination de la récursivité: Algorithme Général

26

27

Au niveau de l’utilisateur: la récursivité permet d’écrire

des algorithmes concis et élégants.

Au niveau de la machine: le compilateur élimine toujours

la récursivité (Dérécursiver) en construisant un

programme itératif (ensemble des instructions

séquentielles) afin d’économiser l'espace de la pile

d'exécution.

Dérécursiver, c’est transformer un algorithme récursif

en un algorithme itératif équivalent ne contenant pas des

appels récursifs.

GÉNÉRALITÉS

28

Rappel: Un algorithme est dit récursif terminal s’il ne

contient aucun traitement après un appel récursif.

ÉLIMINATION DE LA RÉCURSIVITÉ TERMINALE SIMPLE

Procédure ALGO (X) // Liste des paramètres

Si (COND) alors // Condition portant sur X

TRAIT1 // Traitement de base de l’algorithme (dépendant de X)

ALGO (B(X)) // B(X) représente la transformation des paramètres

Sinon

TRAIT2 // Traitement de terminaison (dépendant de X)

Fsi

29

Algorithme Récursif Algorithme Itératif

Procédure ALGO-R (X)

Début

Si (COND) alors

TRAIT1

ALGO-R (B(X))

Sinon

TRAIT2

Fsi

Fin

Procédure ALGO-I (X)

Début

Tant que (COND) faire

TRAIT1

X B(X)

FTQ

TRAIT2

Fin



EXEMPLE: FACTORIELLE

30


Fonction Facto-R (n, resultat)

Début

Si (n>1) alors

Retourner (Facto-R (n-1, n * resultat))

Sinon

Retourner (resultat)

Fsi

Fin

Fonction Facto-I (n, resultat)

Début

Resultat1

Tant que (n>1) faire

résultat n * resultat

n n-1

FTQ

Retourner (resultat)

Fin

ÉLIMINATION DE LA RÉCURSIVITÉ TERMINALE MULTIPLE

EXEMPLE: PGCD

31

Écrire une fonction récursive permettant de calculer le PGCD (Plus

Grand Commun Diviseur) de deux nombres naturels non nul (a, b) en

utilisant l’algorithme d’Euclide:

32


Fonction PGCD-R (a, b)

Début

Si (a = b) alors Retourner (a)

Sinon // ab

Si (a>b) alors

Retourner (PGCD-R (a-b, b))

Sinon

Retourner (PGCD-R (a, b-a))

Fsi

Fin

Fonction PGCD-R (a, b)

Début

Tant que (ab) faire

Si (a>b) alors aa-b

Sinon bb-a

FTQ

Retourner (a)

Fin

ÉLIMINATION DE LA RÉCURSIVITÉ TERMINALE MULTIPLE

EXEMPLE: PGCD

33

Dans un algorithme récursif non terminal, l’appel récursif est

suivi d’un traitement Il reste un traitement (TRAIT2) à

reprendre après l’appel récursif

ÉLIMINATION DE LA RÉCURSIVITÉ NON TERMINALE SIMPLE

Procédure ALGO (X) // Liste des paramètres

Si (COND) alors // Condition portant sur X

TRAIT1 // Traitement de base de l’algorithme (dépendant de X)

ALGO (B(X)) // B(X) représente la transformation des paramètres

TRAIT2 // Traitement à reprendre après le retour (dépendant de X)

Sinon

TRAIT3 // Traitement de terminaison (dépendant de X)

Fsi

34

Il faut donc sauvegarder le contexte de l’appel récursif

(typiquement les paramètres de l’appel engendrant l’appel

récursif) sur une pile

Les piles sont des structures de stockage qui fonctionnent

sur le principe LIFO « last In First Out: le dernier entré

est le premier sorti»

Le principe est de simuler la pile d’appels des processus

pour éliminer la récursivité non terminale.

ÉLIMINATION DE LA RÉCURSIVITÉ NON TERMINALE SIMPLE

35


Procédure ALGO-R (X)

Début

Si (COND) alors

TRAIT1

ALGO-R (B(X))

TRAIT2

Sinon

TRAIT3

Fsi

Fin

Procédure ALGO-I (X)

Début

Init(P) //Initialiser la Pile P.

Tant que (COND) faire

TRAIT1

Empiler(P, X)

X B(X)

FTQ

TRAIT3

Tant que (Non Vide (P)) Faire

Dépiler(P, U)

TRAIT2

FTQ

Fin

36

ÉLIMINATION DE LA RÉCURSIVITÉ NON TERMINALE SIMPLE EXEMPLE: FACTORIELLE


Fonction ALGO-I (N)

Début

Init(P) //P contient la valeur de N.

Tant que (n>1) faire

Empiler(P, N)

N N-1

FTQ

Y1

Tant que (Non Vide (P)) Faire

Dépiler(P, U)

Y Y * U

FTQ

Facto-RY;

Fin

Fonction Facto-R (N)

Début

Si (n>1) alors

Y N * Facto-R (N-1)

Sinon

Y1

Fsi

Facto-RY;

Fin

37

ÉLIMINATION DE LA RÉCURSIVITÉ

ALGORITHME GÉNÉRAL

1. Définir la zone de données

•Contient les paramètres, l’adresse du retour et les variables locales.

2. Définir les points d'appel et de retour.

•Il y a donc toujours un appel dans l'algorithme appelant. C'est le premier appel.

3. Appel de la procédure

•3.1. Empiler la zone de données courante.

•3.2. Préparer le nouvel appel en préparant la nouvelle zone de données avec les

paramètres (passage de paramètres) et avec l'adresse de retour (point d'appel).

•3.4. Se brancher vers le début de la fonction.

4. Retour de la procédure

•4.1. Récupérer l'adresse de retour qui se trouve dans la zone de données courante.

•4.2. Dépiler une zone de donnée (restaurer la dernière sauvegardée)

•4.3. Se brancher vers cette adresse.

38


EXEMPLE: LES TOURS DE HANOI

Programme appelant

.....

Et0:Hanoi(4,’A’,’B’,’C’);

.....

1. Soit Z la zone de données, Z = [n, S, D, I, @retour]

2. Soient Et0, Et2, Et3 les points d’appel et de retour et Et1

l’adresse de début de la fonction

Procédure appelée

Procédure Hanoi-R ( n, S, D, I)

Et1 SI ( n > 0 )

Et2 Hanoi-R ( n-1, S, I, D );

écrire(SD );

Et3 Hanoi-R ( n-1, I, D, S );

FSI

39



Prog. appelant

Et0:Hanoi(4,’A’,’B’,’C’);

//suite du prog

CreerPile(P);

Empiler(P,Z);

Z.n4; Z.S ‘A’; Z.D ‘C’; Z.I ‘B’; Z.@Et0;

goto Et1;

Et0: suite du prog

Proc Hanoi-R ( n, S, D, I) /*Traduction de la procédure*/

Et1 SI ( n > 0 ) Et1: SI ( Z.n > 0 )

Et2 Hanoi-R ( n-1, S, I, D ); Empiler(P,Z)

Z.nZ.n-1; TZ.D; Z.DZ.I; Z.IT; Z.@Et2;

goto Et1;

écrire(SD ); Et2: écrire(Z.SZ.D );

Et3 Hanoi-R ( n-1, I, D, S ); Empiler(P,Z)

Z.nZ.n-1; TZ.S; Z.SZ.I; Z.IT; Z.@Et3;

goto Et1;

FSI Et3: FSI

Fin TmpZ.@;

Depiler(P,Z);

goto tmp

40



CreerPile(P); Empiler(P,Z); Z.n4; Z.S ‘A’; Z.D ‘C’; Z.I ‘B’; Z.@Et0;

Allera Et1;

Et1: SI ( Z.n > 0 )

Empiler(P,Z); Z.n:=Z.n-1; T:=Z.D;Z.D:=Z.I;Z.I:=T;Z.@=Et2;

goto Et1;

Et2: écrire(Z.SZ.D );

Empiler(P,Z) Z.n:=Z.n-1; T=Z.S; Z.S:=Z.I; Z.I:=T; Z.@=Et3;

goto Et1;

Et3: FSI

Répéter

Tmp:=Z.@; Depiler(P,Z);

Jusqu’à tmp!=Et3;

Si tmp = Et2

alors goto Et2;

Sinon allera Et0;

Et0: suite du prog

Amélioration: Peut on éliminer les goto???

Équivalente à non pile vide

1

2

3 3

CONCLUSION

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.

41

PARTIE 3: DIVISER POUR

RÉGNER Cours n°5: 23 Octobre 2013

PLAN DE LA PARTIE III

Principe

Complexité des Algorithmes « Diviser pour

Régner »

43

44

La récursivité est un outils puissant permet de concevoir des

solutions (simples) sans se préoccuper des détails

algorithmiques internes

Paradigme Diviser pour Régner: spécifier la solution du

problème en fonction de la (ou des) solution(s) d'un (ou de

plusieurs) sous-problème plus simple(s).

Comment trouver la solution d'un sous-problème ?

Ce n'est pas important car on prendra comme hypothèse que

chaque appel récursif résoudra un sous-problème

Si on arrive à trouver une solution globale en utilisant ces

hypothèses, alors ces dernières (hypothèses) sont forcément

correctes, de même que la solution globale Cela ressemble à la

« démonstration par récurrence »

PRINCIPE

45

PRINCIPE D

ivis

er

Ré

gn

er

Co

mb

iner

Problème

Global

Sous

Problème

1

Sous

Problème

2

Sous

Problème

K

Décomposer le problème en k

sous problème de taille

moindre

Sous

Solution

1

Sous

Solution

2

Sous

Solution

K

Chaque sous problème sera résolu par la même décomposition récursive

....jusqu’à l’obtention de sous problèmes triviaux

Solution

Globale

Combinaison des solutions

obtenues

46

EXEMPLE 1 : RECHERCHE MAXIMUM

Soit Tab un tableau à n éléments, écrire une fonction

récursive permettant de rechercher de l’indice du

maximum dans Tab en utilisant le paradigme diviser

pour régner

5 8 1 10

5 8 1 10

5 8 1 10

8 10

10

Div

iser

Rég

ner

Combiner

47

EXEMPLE 1 : RECHERCHE MAXIMUM

Fonction maximum ( Tab , indDeb, indFin)

Si ( indDeb = indFin) alors retourner (indDeb)

Sinon

M(indDeb+indFin)/2 // division du problème en 2 sous-problèmes

k1 maximum (Tab, indDeb, m ) // régner sur le 1er sous-problème

k2 maximum (Tab, m+1, indFin) // régner sur le 2ème sous-problème

// Combiner les solutions

Si (Tab[k1] > Tab[k2]) alors retourner (k1)

Sinon retourner (k2)

Fsi

Fsi

Fin

T(n)

T(n) = 2 T(n/2) + c

T(n/2)

T(n/2)

48

EXEMPLE 2 : RECHERCHE DICHOTOMIQUE

Soit Tab un tableau trié (ordre croissant) à n éléments.

La recherche par dichotomie compare l‘élément cherché x avec

l‘élément en position m situé au milieu du sous-tableau :

si Tab[m] = x : on a trouvé l‘élément en position m

si Tab[m] > x : il est impossible que x se trouve après la position

m dans le tableau. Il reste à traiter uniquement la moitié

inférieure du tableau

De même si Tab[m] < x : il reste à traiter uniquement la moitié

supérieure du tableau

On continue ainsi la recherche jusqu’à trouver l’élément ou bien

aboutir sur un tableau de taille nulle, x n'est pas présent et la

recherche s'arrête.

49

EXEMPLE 2 : RECHERCHE DICHOTOMIQUE

Fonction RechDicho(Tab :Tableau, borneinf :entier, bornesup :entier, x :entier) : bool

Si (borneinf<=bornesup) alors

mil (borneinf+bornesup) DIV 2 ;

Si (Tab[mil]=elem) Alors retourner (vrai)

Sinon

Si (Tab[mil]>x) Alors Retourner (RechDicho(Tab, borneinf, mil-1, x))

Sinon

Retourner(RechDicho(Tab, mil+1, bornesup, elem))

Fsi

Sinon

Retourner (Faux)

Fsi

T(n)

T(n/2)

T(n) = T(n/2) + c

50

COMPLEXITÉ DES ALGORITHMES « DIVISER POUR RÉGNER »

Le temps d'exécution d’un algorithme « diviser pour régner » se décompose

suivant les trois étapes du paradigme de base :

Diviser: le problème en a sous-problèmes chacun de taille 1/b de la

taille du problème initial. Soit D(n) le temps nécessaire à la division du

problème en sous-problèmes.

Régner: Soit aT (n/b) le temps de résolution des a sous-problèmes.

Combiner: Soit C(n) le temps nécessaire pour construire la solution

finale à partir des solutions aux sous-problèmes.

T(n) = a T (n/b) + D(n) + C(n)

Soit la fonction f (n) la fonction qui regroupe D(n) et C(n). La fonction T(n) est

alors définie :

T(n) = a.T(n / b) + f(n)

51


THÉORÈME DE RÉSOLUTION DE LA RÉCURRENCE :

Pour f (n) = c nk , on a : T(n) = a.T(n / b) + c nk

52


EXEMPLES

Pour T(n) = a.T(n / b) + c nk, on a :

Complexité de l’algorithme de recherche du maximum:

T(n) = 2 T(n/2) + c

a = 2 , b = 2, k = 0 a > bk

T(n) = O(n)

53


EXEMPLES


Complexité de l’algorithme de recherche dichotomique:

T(n) = T(n/2) + c

a = 1 , b = 2, k = 0 a = bk

T(n) = O(log(n))

54


EXEMPLES


55


EXEMPLES


56


AUTRES RÉSOLUTIONS DE RÉCURRENCE

Équations de récurrence linéaires:

Exemple : Les Tours de Hanoi

Hanoi( n:entier; A,B,C : caractères ) [T(n)]

SI ( n > 0 )

Hanoi ( n-1, A, C, B ); [T(n-1)]

écrire(« déplacer un disque de », A, « vers », B ); [cst]

Hanoi( n-1, C, B, A ); [T(n-1)]

FSI

T(n) = 2*T(n-1) + c avec T(0) = 0;

57



Équations de récurrence linéaires:

Exemple : Les Tours de Hanoi

T(n) = 2*T(n-1) + c

O (T) = 2n O (T) = 2n

58



Équations de récurrence linéaires sans second membre (f(n) = cte)

A une telle équation, on peut associer un polynôme:

La résolution de ce polynôme nous donne m racines ri ( avec

m<=k).

La solution de l’équation de récurrence est ainsi donnée par :

Cette solution est en général exponentielle

59



Exemple : La suite de Fibonacci

SOURCES DE CE COURS

Frédéric Vivien, Algorithmique avancée, École Normale Supérieure de Lyon, 2002.,

pp. 93. Disponible sur http://perso.ens-lyon.fr/frederic.vivien/Enseignement/Algo-

2001-2002/Cours.pdf

Slim Msfar, Algorithmique et Complexité, 2012, pp 104. Disponible sur

http://p835.phpnet.org/testremorque/upload/catalogue/coursalgorithmi.pdf

Walid-Khaled Hidouci, La récursivité, École nationale Supérieure d’Informatique,

pp 107. Disponible sur hidouci.esi.dz/algo/cours_recursivite.pdf

La récursivité, Cours d’ Algorithmique et Structures de données dynamiques, École

nationale Supérieure d’Informatique, Année Universitaire 2009-2010.

60

http://perso.ens-lyon.fr/frederic.vivien/Enseignement/Algo-2001-2002/Cours.pdf




























http://www.zegour.netii.net/Site secondaire/Mcp/Cours ppt/1_o-notation.pdf hidouci.esi.dz/algo/cours_recursivite.pdf









Education

Chapitre iii récursivité et paradigme diviser pour régner