Chapitre annexe. Récursivité

1

IntroductionOn a appris comment écrire des actions répétitives avec des

boucles. Cette manière de traiter des actions répétitives s'appelle programmation itérative. Il existe un procédé concurrentiel à celle-ci: la récursivité.

Tout processus répétitif peut être considéré de deux points de vue. Ainsi, pour monter un escalier de n marches on peut

soit faire de 1 à n: monter une marche (approche itérative)

soit monter une marche, puis monter un escalier de n –1 marches, ...

Une fois l'escalier restant ne comporte que 0 marches, s'arrêter. (approche récursive).

2

Processus répétitifs : répétition "classique" et récurrence

Donnons un exemple de processus répétitif exprimé de façon itérative et récursive.

Une puissance n (n > 0) d'un réel x peut être programmée à l'aide d'une boucle pour:

3

données : float x, int n

résultat de type float

Entête en C : float puiss(float x, int n);

{variables locales : float p, int ip 1POUR (i 1 à n) FAIRE

p p*xretourner p}

4

Mais on peut également donner la recette suivante, qu'on va d'abord décrire.

Pour faciliter l'écriture, appelons la fonction puissance f :

nxnxf ),(

Alorsf(x,n)=f(x,n–1)x où f(x,n–1) est pour le moment inconnue, mais on peut la calculer comme

f(x,n–1)=f(x,n–2)x où f(x,n–2) est pour le moment inconnue, mais on peut la calculer comme

f(x,n–2)=f(x,n–3)x etc…

En continuant, on arrive à ce que la fonction figurant dans le terme de droite est f(x,n–n)=f(n, 0)=x0=1.

A ce point, elle n'est plus inconnue. Cela peut se programmer comme suit:

5

données : float x, int nrésultat de type float

Entête en C : float puis(float x, int n)

{variables locales : float pSI (n = 0) ALORS {1: condition d'arrêt}p 1

SINONp x * puis(x,n-1) {2: action répétée: multiplication par

x}{3: appel récurrent de puis avec un paramètre

modifié}

retourner p}

6

Cette écriture n'est rien d'autre que le codage en C de la relation de récurrence:

puissance (x,0) = 1puissance(x,n) = puissance(x,n–1)*x si n > 0

Nous venons de donner un exemple de fonction récursive. A la différence des fonctions vues auparavant, elle comporte un appel à la même fonction (puissance). Cet appel se fait avec une nouvelle valeur de paramètre (n–1 au lieu de n).

7

Toute procédure ou fonction récursive comprend les 3 parties suivantes :

1. la condition d'arrêt du processus

2. l'action à répéter, donc à exécuter dans l'étape courante

3. le passage à l'étape suivante : on continue (appel récurrent) avec une nouvelle valeur du paramètre

La répétition gérée à l’aide des boucles peut se considérer comme une vue globale d'un processus répétitif.

La récurrence peut se considérer comme une vue locale d'un processus répétitif :

étape n et passage à l'étape n+1, si on n'a pas fini.

Ceci est possible pour tout processus répétitif.8

Récursivité simple

DéfinitionUn algorithme sp est récursif, si lors de son

exécution, on doit à nouveau lancer l'exécution de sp.

9

Exemples

Placer 10 étoiles sur une ligne à l'écran

10

Version non-récursive :

Entête en C : void etoiles_non_rec()

{variables locales : int iPOUR (i 1 à 10) FAIRE

écrire (‘*’)}Appel dans l’algorithme appelant :...etoiles_non_rec()...

11

Version récursive :

données : int nEntête en C : void etoiles_rec (int n);{SI (n 10) ALORS

{écrire (‘*’)etoiles_rec(n+1)

}}Appel dans l’algorithme appelant :...etoiles_rec(1).. 12

À l'appel de tout module (récurrent ou non), les valeurs des variables locales de ce module sont placées en mémoire centrale en haut d'une pile (tout à fait comparable avec une pile d'assiettes), sur celles du module qui l'a appelé, à partir des valeurs des variables du programme principal, qui constituent la base de la pile.

Chaque fois que l'exécution d'un module est terminée, les valeurs de ses variables locales sont supprimées en haut de la pile (on dit: "dépilées").

13

En cas d'appel récurrent, il se produit exactement la même chose:

Un module récurrent appelle un nouvel exemplaire de lui-même, dont les nouvelles valeurs des variables locales s'empilent en mémoire.

14

Par conséquent, une répétition exprimée par récurrence occupe en mémoire une place proportionnelle au nombre de répétitions, alors qu'une répétition "classique" occupe une place indépendante du nombre de répétitions.

En conclusion, on choisit la récursivité seulement si l'écriture est plus simple, et si le nombre maximum de modules empilés est faible (sauf en langage Lisp, où toute répétition s'exprime par récurrence).

15

Afficher les 10 premiers nombres entiers à l'écran:

Version non-récursive :

Entête en C : void compter_rep ()

{variables locales : int iPOUR (i 1 à 10) FAIRE

afficher(i)}

16

Version récursive :

données : int n Entête en C : void compter_rec(int n)

{SI (n 10) ALORS

{afficher(n)compter_rec(n+1)}

}

17

Si l'on place une autre action à répéter après l'appel récurrent, cette action ne se fait pas à l'empilement, mais au dépilement:

On empile les modules (imaginez la pile de modules comme une pile d'assiettes):

dans le premier (bas de la pile), n a pour valeur 1 dans le dernier (haut de la pile), n a pour valeur 10

18

19

On dépile les modules:

on affiche la valeur de n du premier module dépilé (haut de la pile): 10

puis on affiche la valeur de n du deuxième module dépilé (haut de la pile): 9

et ainsi de suite: on affiche donc les nombres décroissants

On parcourt la pile en touchant 2 fois chaque assiette : 1 fois à l'empilement, 1 fois au dépilement

données : int n 

Entête en C : void compterRecur (int n)

{SI (n <= 10) ALORS {afficher('empilement: ', n);

compterRecur(n + 1);

afficher('dépilement : ', n) }}

20

empilement : 1empilement : 2

empilement : 3empilement : 4

empilement : 5empilement : 6

empilement : 7empilement : - 8

empilement : 9empilement : 10dépilement : 10

dépilement : 9dépilement : 8

dépilement : 7dépilement : 6

dépilement : 5dépilement : 4

dépilement : 3dépilement : 2

dépilement : 1

21

Définition

Un sous-algorithme est dit récursif terminal s'il n'y aura aucun calcul à faire à la sortie de la relance récursive pour obtenir le résultat final

22

Calculer la somme des n premiers nombres entiers

Version non-récursive en C :

int somme_iter (int n){int i , som = 0 ;for (i = 1 ; i <= n ; i++)som = som + i ;return som ;}

23

Version récursive :

En fait, cette fonction n'est que le codage en C de la relation de récurrence :somme(1) = 1 somme(n) = somme (n – 1) + n si n > 1 int SommeRecur (int n) { int somme; printf (" empilement : %d \n", n); if (n = 1)

{printf (" depilement : %d \n", n);return 1 ; }

else{ somme = n + SommeRecur(n – 1); printf (" depilement : %d \n", n);return somme ; }

}

24

Appel :...som = SommeRecur(10);printf ("som: %d \n", som);..

25

empilement : 10 empilement : 9 empilement : 8 empilement : 7 empilement : 6 empilement : 5 empilement : 4 empilement : 3 empilement : 2 empilement : 1 dépilement : 1 dépilement : 2 dépilement : 3 dépilement : 4 dépilement : 5 dépilement : 6 dépilement : 7 dépilement : 8dépilement : 9

dépilement : 10

som : 55

26

Circulation des données entre les différentes instances de SommeRecur:

n : 10 9 8 7 6 5 4 3 2 1

55 <-- 45 <--36 <-- 28 <-- 21 <-- 15 <-- 10 <-- 6 <-- 3 <-- 1 SommeRecur(n)

27

Récursivité croisée

II arrive parfois qu'un algorithme soit constitué de deux sous-algorithmes récursifs dont les définitions s'entrecroisent mutuellement.

28

Définition

On dira que l’on a une récursivité croisée quand on a deux sous-algorithmes sp1 et sp2 tels que lors de l'exécution de sp1, on doit lancer l'exécution de sp2, et inversement.

29

L'exemple classique de récursivité croisée est donné par le calcul de la parité d'un entier en C :

int pair(int n) /* Pour n 0, pair(n) est vrai si n est pair et faux sinon */ { if (n == 0)

pair = 1; else

return ( impair(n-1) ); }int impair(int n) ; /* Pour n 0, impair(n) est vrai si n est impair et faux sinon */ { if (n = =0)

impair = 0; else

return (pair(n-1)); }

30

Récursivité multiple

Terminons par une catégorie de programmes récursifs qui mettra le plus en lumière la puissance du procédé : la récursivité multiple.

31

Définition

On dira qu'il y a une récursivité multiple (double, triple, ... ) dans un sous-algorithme sp si, lors de son exécution, il faudra plusieurs relances récursives conjointes de sp pour obtenir le résultat final

32

L'exemple très simple c'est le calcul du terme d'ordre n de la suite de Fibonacci, définie par :

F(n) = F(n-1) + F(n-2)F(1) = 1F(2) = 1

En C :int fibo(int n){if (n <=2)

return 1;return fibo(n-1) + fibo(n-2);}

33