Enseignant : Ahmadi Ferid AS : 2008/2009 - Examen corrige

Chapitre II: La récursivité
Objectifs :

. Définir la récursivité.
. Résoudre des problèmes récursifs
. Comparer les approches de programmation itérative et récursive.


I. Notion de récursivité:

La récursivité est une méthode algorithmique qui consiste à appeler un sous-
programme dans son propre corps.
Une procédure ou une fonction est dite récursive si son corps contient un
ou plusieurs appels à-elle- même.

Le principal avantage d'un algorithme récursif est qu'il est généralement
plus simple, plus lisible et facile à comprendre. Par contre, le principal
problème est la définition du ou des cas d'arrêt.

II. Les types de récursivité:


1) La récursivité directe ou simple :

Module récursif(paramètres)

Début



Récursif (paramètres changés)



Fin

2) 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


III. Etude d'un exemple : La fonction factorielle

1) Solution itérative :

Analyse de la fonction Factorielle

| |DEF FN Fact (n : entier): entier |
|S |LDE |O.U |
|2 |Résultat = Fact< F |F |
| | | |
|1 |F = [ ] Pour i de 2 à n faire |i |
| |F < F * i | |
| |Fin pour | |
|3 |Fin Fact | |


Algorithme de la fonction Factorielle

0) DEF FN Fact (n : entier): entier

1) [F < 1] Pour i de 2 à n faire

F < F * i

Fin pour

2) Fact < F

3) Fin fact

2) Solution récursive :

La solution de récurrence est définie par : 0 ! = 1 et n ! = n*(n-
1) !

Cette relation donne la fonction récursive suivante :

0) DEF FN Fact (n : entier): entier

1) Si n=0 alors

Fact < 1

Sinon

Fact < n * Fact (n-1)

Fin Si

2) Fin fact

IV.Mécanisme de fonctionnement de la récursivité


Considérons le calcul de 4 ! Par la fonction récursive définie ci-
dessus :

Fact (4) renvoie 4* Fact(3)

Fact(3) renvoie 3* Fact(2)

Fact(2) renvoie 2* Fact(1)

Fact(1) renvoie
1* Fact (0)


Fact(0) renvoie 1(arrêt de la récursivité)


Fact(1) renvoie 1*1=1

Fact(2) renvoie 2*1=2

Fact(3) renvoie 3*2=6

Fact(4) renvoie 4*6=24

V. 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 (b0) 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 recursif.

On aura donc la fonction récursive suivante :

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

1) Si (b=0) alors

Pgcd(a

Sinon

Pgcd(pgcd(b,a mod b)

2) Fin pgcd



VI. 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, comme par exemple Pascal, 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.

Une pile est donc tout simplement un tableau indiquant où le compilateur en
était dans le déroulement de chacune de ses tâches interrompues :

- les adresses de retour

- les valeurs affectées aux différentes variables.

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.

VII. Choix entre itération et récursivité


Le choix de la solution itérative peut être imposé par le langage de
programmation. En effet, certains langages tels que Cobol et T. Basic ne
sont pas récursifs.

D'autre part, 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.







Série d'exercices

Exercice N°1 :

Ecrire une fonction récursive PPCM qui permet de retourner le PPCM de deux
entiers donnés.

Exercice N°2 :

Ecrire une fonction récursive Som_Tab permettant de calculer la somme des
éléments d'un tableau.

Exercice N°3 :

Ecrire une fonction récursive Som_Mat permettant de calculer la somme des
éléments d'une matrice.

Exercice N°4 :

Ecrire une procedure récursive Rech_Seq qui permet de vérifier l'existence
d'un entier x dans un tableau T qui contient n entiers, en utilisant la
méthode de recherche séquentielle.

Exercice N°5 :

Ecrire une procédure récursive Rech_Dic qui permet de vérifier l'existence
d'un entier x dans un tableau T qui contient n entiers, en utilisant la
méthode de recherche dichotomique.

Exercice N°6 :

Ecrire une fonction récursive Inverse_Tab qui permet d'inverser les
éléments d'un tableau.

Exercice N°7 :

Ecrire une fonction récursive Inverse_Chaine qui permet d'inverser une
chaîne de caractères.

Exercice N°8 :

Ecrire une fonction récursive Palindrome qui vérifie si une chaine de
caractères est un palindrome ou non.

Exercice N°9 :

Ecrire une procédure récursive Tri_Bulles qui permet de trier un tableau T
de n entiers en utilisant la méthode de tri à bulles.

Exercice N°10 :

Ecrire une procédure récursive Tri_Selection qui permet de trier un tableau
T de n entiers en utilisant la méthode de tri par selection.

Exercice N°11 :

Ecrire une procédure récursive Tri_Insertion qui permet de trier un tableau
T de n entiers en utilisant la méthode de tri par insertion.

























Correction des exercices

Exercice N°1 :

function PPCM(max,min:integer):longint;

begin

if (max mod min=0) then

ppcm:=max

else

ppcm:=PPCM(max+max1,min);

end;

Exercice N°2 :

function Som_Tab(t:tab;d,n:integer):integer;

begin

if n=0 then

somme:=0

else

somme:=t[n]+ Som_Tab(t,d,n-1);

end;

Exercice N°3 :

Function Som_Mat(k,l: integer):integer;

begin

if k > n then

somme:=0

else

begin

if l