Université Ben Youcef BENKHEDDA-Alger1

République algérienne démocratique et populaire

Série TD 3 _Récursivité
Ce document contient quelques éléments de correction pour les TD.

Les étudiants de: Réalisé par:

-Section B -Aichaoui Zoubida

2023/2024
 Exercice 01
1. La factorielle d’un nombre entier positif.
2. le nième terme de la suite de Fibonacci.
3. La conversion d’un nombre entier positif donné N écrit en décimal vers une base donnée inférieure à 10 et soit b
4. Le calcul de la somme des n premiers carrés.
5. La recherche dichotomique d’une valeur V dans un vecteur trié donné T de taille N.
6. Le calcul de nombre de postions (digits) d’un nombre entier positif donné N.
7. Le calcul de la fréquence d’apparition (occurrences) d’une valeur donnée V dans un vecteur donné T de taille N.
8. Le calcul de la somme des valeurs d’un vecteur donné T de taille N.
9. Le calcul de la fréquence d’apparition (occurrences) d’une valeur donnée V dans une LLC donnée L.
10. Le calcul de la somme des valeurs d’une LLC donnée L.
11. L’affichage d’une LLC donnée L.
12. La libération d’une LLC donnée L.
13. La création d’une LLC donnée L avec insertions à la fin.
14. Le calcul de la taille d’une LLC donnée L.
15. Le calcul du Maximum d’une LLC d’entiers donnée L.
16. Une fonction Booléenne qui vérifie l’existence d’une valeur donnée V dans une LLC donnée L.
17. Une fonction qui permet de créer une LLC copie (Duplicata)d’une LLC donnée L.
18. Une fonction qui retourne le pointeur du dernier maillon d’une LLC.
3 La conversion d’un entier positif donné N en décimal vers une base donnée < à 10

 Déroulement d'un exemple :

10 2

0 5 2

1 2 2

0 1 2

Donc b = 1010 1 0
3 La conversion d’un entier positif donné N en décimal vers une base donnée < à 10

 Déroulement d'un exemple récursivement :

• 10 / 2 = 5 • 5/2=2 • 2/2=1 • 1/2=0

• Convertir (5) • Convertir (2) • Convertir (1) • Convertir (0)
• Reste = 10 mod 2 • Reste = 5 mod 2 • Reste = 2 mod 2 • Reste = 1 mod 2
• Afficher Reste • Afficher Reste • Afficher Reste • Afficher Reste

b = 1010 b = 101 b = 10 b=1

 STOP : quand N = 0
3 La conversion d’un entier positif donné N en décimal vers une base donnée < à 10

Procédure Convertir (N, b: entier)

Début

si (N == 0) alors
écrire 0 ;

sinon
Convertir (N div b, b);
écrire (N mod b)

Fin procédure
 4 Le calcul de la somme des n premiers carrés

 Déroulement d'un exemple récursivement :

• 4 • 3 • 2 • 1
• SommeCarrés (4-1) • SommeCarrés (3-1) • SommeCarrés (2-1) • SommeCarrés (1-1)
• Carre = 4*4 • Carre = 3*3 • Carre = 2*2 • Carre = 1*1
• Afficher S=S+ Carre • Afficher S=S+ Carre • Afficher S=S+ Carre • Afficher S=S+ Carre

b = 1^2 + 2^2 + 3^2 + 4^2 b = 1^2 + 2^2 + 3^2 b = 1^2 + 2^2 b = 1^2

 STOP : quand N = 0
4 Le calcul de la somme des n premiers carrés

fonction SommeCarrés(n: entier): entier

Si n = 0 alors
return 0

Sinon
return n * n + SommeCarrés (n - 1);
=4*4 +sommeCarres(3)
=4*4 +3*3+SommCarres(2)
Fin fonction =4*4 +3*3+2*2+SommeCarres(1)
=4*4 +3*3+2*2+ 1*1+SommeCarres(0)
=4*4 +3*3+2*2+ 1*1+0
5 La recherche dichotomique d’une valeur V dans un vecteur trié donné T de taille N.

 Déroulement d'un exemple :

milieu = (debut + fin) / 2
Milieu = i = 3

i=0 i=1 i=2 i=3 i=4 i=5 i=6

2 5 6 7 10 12 30

7 < 30
Milieu+1 =4
2 5 6 10 12 30
12 < 30

10 30
5 La recherche dichotomique d’une valeur V dans un vecteur trié donné T de taille N.

 Déroulement d'un exemple :

i=0 i=1 i=2 i=3 i=4 i=5 i=6

2 5 6 7 10 12 30

7>2
Milieu-1 =2
2 5 6 10 12 30
7>2

2 6
5 La recherche dichotomique d’une valeur V dans un vecteur trié donné T de taille N.

fonction RechercheDichotomiqueRecursif (T[]:entier; début, fin, V: entier): booleen;

Var milieu: entier;

si (début > fin) alors

return faux; // Valeur non trouvée

sinon
milieu <- (début + fin) div 2

si (T[milieu] = V ) alors // Cas où la valeur est trouvée au milieu

return vrai

sinon si (T[milieu] > V) alors

return RechercheDichotomiqueRecursif (T, début, milieu - 1, V)

sinon
return RechercheDichotomiqueRecursif (T, milieu + 1, fin, V)
6 Le calcul de nombre de postions (digits) d’un nombre entier positif donné N.

 Déroulement d'un exemple récursivement :

• 3021 / 10 = 302 • 302 / 10 = 30 • 30 / 10 = 3 • 3 / 10 = 0

• digit (302) • digit (30) • digit (3) • digit (0)
• Afficher 1+Reste • Afficher 1+Reste • Afficher 1+Reste • Afficher 1+Reste

b = 1+3 b = 1+2=3 b = 1+1 b=1

 STOP : quand N = 0
6 Le calcul de nombre de postions (digits) d’un nombre entier positif donné N.

fonction digit(N: entier): entier

Si (N =0) alors =1 +digit(3021)

return 0 =1+1+ digit(302)
=1+1+1+ digit(30)
Sinon =1+1+1+ 1+ digit(3)
return 1+ digit (N / 10); =1+1+1+ 1+1+digit(0)
=1+1+1+ 1+1+0
Fin function
9 Le calcul de la fréquence d’apparition d’une valeur V dans une LLC donnée L

fonction cptApparition (tète :^maillon; V: entier, cpt: entier) {

si (tète = NULL)
return cpt
sinon
si (tète^.val = V)
cpt <- cpt+1

return cptApparition (tète^.suiv, V , cpt);

fin fonction

tète
0 2 1 2 3
10 Le calcul de la somme des valeurs d’une LLC donnée L.

fonction somme (tète :^maillon) ;entier

si (tète = NULL) =0 +somme(2)

return 0; =0+2+ somme(1)
sinon =0+2+1+ somme(2)
=0+2+1+ 2+ somme(3)
return tète^.val + somme (tète^.suiv)
=0+2+1+ 2+3+somme(Null)
=0+2+1+ 2+3+0
fin procédure

tète
0 2 1 2 3
S=0+8 S=2+6 S=1+5 S=2+3 S=3
11 L’affichage d’une LLC donnée L

procédure affichage (tète :^maillon) {

si (tète = NULL)
Afficher une nouvelle ligne
sinon
écrire (tète^.val, ' ‘)
affichage (tète^.suiv)

fin procédure

tète
0 2 1 2 3
12 La libération d’une LLC donnée L

fonction libérer (tète :^maillon) {

si (tète = NULL)
return;
sinon
libérer (tète^.suiv)
free(tète)

fin procédure

tète
0 2 1 3
13 La création d’une LLC donnée L avec insertions à la fin

tète
Etape 1: 0

tète tète
Etape 2; 0 2

tète tète
Etape 3;
0 2 1

tète tète
Etape 4; 0 2 1

tète
Etape 5; 0 2 1
13 La création d’une LLC donnée L avec insertions à la fin

fonction InsererFin (tète :^maillon; valeur: entier) :^maillon

si (tète = NULL)
New(nouv);
nouv^.val := valeur;
nouv^.suiv := null;
return nouv;
sinon
tète^.suiv <- InsererFin(tète^.suiv, valeur);
return tete;

fin fonction

tète
0 2 1 2 3
14 Le calcul de la taille d’une LLC donnée L

fonction taille (tète :^maillon, cpt: entier) {

si (tète = NULL)
return cpt
sinon
cpt <- cpt+1
return taille (tète^.suiv, cpt)

fin fonction

tète
0 2 1 2 3
15 Le calcul du Maximum d’une LLC d’entiers donnée L

tète
0 6 1 3

• 0 • 6 • 1 • 3
• FindMax (suiv) • FindMax (suiv) • FindMax (suiv) • FindMax (suiv)
• Comparer (0,max) • Comparer (6,max) • Comparer (1,max) • Comparer (3,max)

max = 6 max = 6 max = 3 max = 3

 STOP : quand suiv = null

15 Le calcul du Maximum d’une LLC d’entiers donnée L

function FindMax (tete: ^maillon): entier;

Var max: entier;

si (tete = null) alors

exit

si (tete ^.suiv = null ) alors // Cas de base : seul élément dans la LLC
return tete^.val

sinon
max <- FindMax(tete^.suiv); // Appel récursif pour le reste de la liste chaînée

si ( tete^.val > max ) alors // Compare le maximum trouvé avec la valeur

return tete^.val
sinon
return max
Fin fonction
16 Une fonction qui vérifie l’existence d’une valeur V dans une LLC donnée L

function ValueExists(tete: ^millon; V: entier): Boolean;

si (tete = null) alors

return False
sinon

si( tete^.val = V )alors

return True
sinon
return ValueExists(tete^.suiv, V);

tète
0 2 1 2 3
17 Une fonction qui permet de créer une LLC copie d’une LLC donnée L.

function DuplicateList(tete: ^maillon): ^maillon;

Var nouv: ^ maillon

si (tete = null) alors // Cas de base : LLC vide

return null

sinon

allouer(nouv); // Crée un nouveau nœud pour la copie

nouv^.val <- tete^.val; // Copie les données du nœud original
nouv^.suiv <- DuplicateList(tete^.suiv) // Appel récursif pour le reste de la liste chaînée
return nouv

tète
0 2 1 2 3
18 Une fonction qui retourne le pointeur du dernier maillon d’une LLC

function FindLastNode(tete: ^maillon): ^maillon;

si (tete = null) alors

exit

si (tete ^.suiv = null ) alors // Cas de base : seul élément dans la LLC
return tete
sinon

return FindLastNode(tete^.suiv) // Appel récursif pour le reste de la liste chaînée

tète
0 2 1 2 3
Exercice 02

étant donnée une matrice carrée T[N][N], où N>1 et N est impair. On veut représenter
un triangle dans la moitié supérieure de cette matrice en mettant a jour certaines cases
de la matrice T.
1. Écrire une action paramétrée récursive afin de représenter un triangle dans la moitié supérieure
de la matrice T.
2. Écrire une action paramétrée récursive afin de représenter un triangle dans la moitié inférieure
de la matrice T.
3. En s’inspirant des deux questions précédentes, écrire une action paramétrés récursive dans le
but de représenter un losange
Exercice 02
2 représenter un triangle dans la moitié superieur de la matrice T

milieu

ligne=0

ligne=1

ligne=2

ligne=3
1 représenter un triangle dans la moitié supérieure de la matrice T

Version itérative Version récursive

void remplirTriangleSU(int T[][N], int valeur) { void remplirTriangleSURecursif(int T[][N], int valeur, int
ligne, int k) {
for (int ligne = 0; ligne < N/2 + 1 ; ++ligne) {
for(int k =0 ;k<= ligne ;k++){ if (ligne < N/2 + 1) {
T[ligne][N/2 +k] = valeur; if (k <= ligne) {
T[ligne][N/2 -k] = valeur; T[ligne][N/2 +k] = valeur;
} T[ligne][N/2 -k] = valeur;
} remplirTriangleSURecursif(T, valeur, ligne, k + 1);
} } else { // sauter la ligne
remplirTriangleSURecursif(T, valeur, ligne + 1, 0);
}
}
}

remplirTriangleSU(matrice, 1); remplirTriangleSURecursif(matrice, 1,0,0);

2 représenter un triangle dans la moitié inferieur de la matrice T
2 représenter un triangle dans la moitié inferieur de la matrice T

Version itérative Version récursive

void remplirTriangleInferieur(int T[][N], int void remplirTriangleINRecursif(int T[][N], int valeur, int ligne,
valeur) { int col, int h) {
int h =1;
for (int ligne = N/2 + 1; ligne <= N ; ++ligne) { if (ligne < N) {
for(int col = h ;col< N - h ;col++){ if (col <= N - h) {
T[ligne][col] = valeur; T[ligne][col] = valeur;
} remplirTriangleINRecursif(T, valeur, ligne, col + 1, h);
h++; } else {
} remplirTriangleINRecursif(T, valeur, ligne + 1, h, h + 1);
} }
}
}

remplirTriangleInferieur(matrice, 1); remplirTriangleinferieurRecursif(matrice, 1, N/2, 1, 1);