La récursivité
2) Définition : En pratique ... d'utiliser les rangs de ces arguments (le premier
paramètre, .... Écrire une fonction récursive chiffre( n, k) qui permet de retourner.
part of the document
cursive :
Ces conseils sont illustrés par l'exemple suivant :
Écrire une fonction récursive permettant de calculer la somme
des chiffres d'un entier n positif (exemple : n = 528, la somme
des chiffres de n est 15).
1. Observer le problème afin de :
a) décrire la condition d'arrêt : quand peut-on
trouver "facilement" la solution ?
(une solution triviale) :
Si on a le choix entre n = 528 et n = 8, il est
certain qu'on choisit n = 8. La somme des chiffres
de 8 est 8.
Conclusion : Si n a un seul chiffre, on arrête. La
somme des chiffres est n lui-même.
if ( n < 10 ) return n;
b) de réduire le problème à un problème d'ordre
inférieur pour que la condition d'arrêt soit
atteinte un moment donné :
somChif(528) 8 + somChif(52)
8 + ( 2 + somChif(5) )
8 + 2 + 5
D'un problème de 3 chiffres, on réduit d'abord à un
problème de deux chiffres : somChif(52). Celui-ci
est réduit à celui d'un seul chiffre : somChif(5).
On rencontre la condition d'arrêt.
else
return n % 10 + somChif ( n / 10 ) ;
2. Écriture de la fonction :
int somChif ( int n )
{
if ( n < 10 ) /* condition d'arrêt */
return n;
else
/* réduction du problème : */
return n % 10 + somChif ( n / 10 ) ;
}
Exercice :
Illustrer les conseils précédents pour écrire une fonction récursive
qui permet de calculer le produit de deux entiers positifs a et b.
Notes :
1. Si vous avez le choix entre : 12 x 456 et 12 x 0
lequel des deux calculs est le plus simple ?
2. 12 x 9 = 12 + 12 + 12 + ... + 12 ( 9 fois )
= 12 + (12 + 12 + ... + 12) ( 8 fois)
= 12 + 12 x 8
etc ...
4) Simulation :
Ne pas utiliser les "noms" des arguments. Il est préférable
d'utiliser les rangs de ces arguments (le premier paramètre,
le deuxième paramètre, etc ...)
Exemple 1 :
Soit la fonction récursive suivante :
int facto ( int n )
{
if ( n 1, exemple k = 3, on a :
chiffre (8724, 3)
chiffre ( 872, 2) (872 est 8724 / 10, 2 est 3-1)
chiffre ( 87, 1) (87 est 872 / 10, 1 est 2-1)
Solution :
int chiffre ( int n, int k )
{
if ( k == 1 ) /* le premier chiffre à partir de la droite */
return n % 10 ;
else
return chiffre ( n / 10, k - 1 ) ;
}
Exemple 3 : Tours de Hanoi.
Supposons qu'on dispose de 3 disques à la tour 1 et on aimerait
les déplacer à la deuxième tour en utilisant la tour 3 comme
intermédiaire.
Les règles du jeu sont les suivantes :
- les disques ont un diamètre différent
- on déplace un disque à la fois
- on n'a pas le droit de placer un disque de diamètre supérieur
sur un de diamètre inférieur.
état 0 :
| | |
--- | |
| | |
------- | |
| | |
----------- | |
| | |
---------------- ---------------- ----------------
Tour 1 Tour 2 Tour 3
état 1 : déplacer un disque de Tour 1 à Tour 2
| | |
| | |
| | |
------- | |
| | |
----------- --- |
| | |
---------------- ---------------- ----------------
Tour 1 Tour 2 Tour 3
état 2 : déplacer un disque de Tour 1 à Tour 3
| | |
| | |
| | |
| | |
| | |
----------- --- -------
| | |
---------------- ---------------- ----------------
Tour 1 Tour 2 Tour 3
état 3 : déplacer un disque de Tour 2 à Tour 3
| | |
| | |
| | |
| | ---
| | |
----------- | -------
| | |
---------------- ---------------- ----------------
Tour 1 Tour 2 Tour 3
état 4 : déplacer un disque de Tour 1 à Tour 2
| | |
| | |
| | |
| | ---
| | |
| ----------- -------
| | |
---------------- ---------------- ----------------
Tour 1 Tour 2 Tour 3
état 5 : déplacer un disque de Tour 3 à Tour 1
| | |
| | |
| | |
| | |
| | |
--- ----------- -------
| | |
---------------- ---------------- ----------------
Tour 1 Tour 2 Tour 3
état 6 : déplacer un disque de Tour 3 à Tour 2
| | |
| ------ |
| | |
--- ----------- |
| | |
---------------- ---------------- ----------------
Tour 1 Tour 2 Tour 3
état 7 : déplacer un disque de Tour 1 à Tour 2
| | |
| --- |
| | |
| ------ |
| | |
| ----------- |
| | |
---------------- ---------------- ----------------
Tour 1 Tour 2 Tour 3
Le processus sera plus compliqué et mêlant quand le nombre de
disques deviendra grand.
Solution :
#include
void deplacer (int n, int t1, int t2, int t3)
{
if ( n == 1 )
printf("De la tour %d à la tour %d\n", t1, t2) ;
else
{ deplacer (n-1, t1, t3, t2) ;
deplacer ( 1 , t1, t2, t3) ;
deplacer (n-1, t3, t2, t1) ;
}
}
void main()
{ int nbDisques ;
printf("Entrez le nombre de disques à déplacer ");
scanf ("%d", &nbDisques);
deplacer ( nbDisques, 1, 2, 3);
}
Note :
Une autre version possible de deplacer est :
void deplacer (int n, int t1, int t2, int t3)
{
if ( n > 0 )
{
deplacer (n-1, t1, t3, t2) ;
printf("De la tour %d à la tour %d\n", t1, t2) ;
deplacer (n-1, t3, t2, t1) ;
}
}
exécution :
Entrez le nombre de disques à déplacer 3
De la tour 1 à la tour 2
De la tour 1 à la tour 3
De la tour 2 à la tour 3
De la tour 1 à la tour 2
De la tour 3 à la tour 1
De la tour 3 à la tour 2
De la tour 1 à la tour 2
Exercice:
Simuler l'appel suivant :
deplacer (3, 1, 2, 3) ;
6) Tri rapide (Quick Sort) :
Supposons qu'on dispose du tableau t qui contient les 9
éléments suivants à trier :
t[0] t[1] t[2] t[3] t[4] t[5] t[6] t[7] t[8]
T%P%P%P%P%P%W%P%P%P%P%P%W%P%P%P%P%P%W%P%P%P%P%P%W%P%P%P%P%P%W%P%P%P%P%P%W%P%P%P%P%P%W%P%P%P%P%P%W%P%P%P%P%P%W%
Q% 43 Q% 75 Q% 23 Q% 46 Q% 55 Q% 12 Q% 64 Q% 77 Q% 33 Q%
Z%P%P%P%P%P%]%P%P%P%P%P%]%P%P%P%P%P%]%P%P%P%P%P%]%P%P%P%P%P%]%P%P%P%P%P%]%P%P%P%P%P%]%P%P%P%P%P%]%P%P%P%P%P%]%
L'idée de la méthode QuickSort est simple :
1) Pour la première fois, on tri le tableau au complet,
c'est-à-dire de l'indice 0 à l'indice (nbElement - 1)
(ici 8). Ceci correspond à l'appel suivant :
quickSort(t, 0, nbElement - 1) ;
2) On partitionne le tableau en deux côtés d'une valeur du pivot.
A gauche, on trouve des valeurs la valeur du pivot.
t[0] t[1] t[2] t[3] t[4] t[5] t[6] t[7] t[8]
T%P%P%P%P%P%W%P%P%P%P%P%W%P%P%P%P%P%W%P%P%P%P%P%W%P%P%P%P%P%W%P%P%P%P%P%W%P%P%P%P%P%W%P%P%P%P%P%W%P%P%P%P%P%W%
Q% 12 Q% 33 Q% 23 Q% 43 Q% 55 Q% 46 Q% 64 Q% 77 Q% 75 Q%
Z%P%P%P%P%P%]%P%P%P%P%P%]%P%P%P%P%P%]%P%P%P%P%P%]%P%P%P%P%P%]%P%P%P%P%P%]%P%P%P%P%P%]%P%P%P%P%P%]%P%P%P%P%P%]%
__________________ ^ _____________________________
valeurs 43
|
valeur du pivot
( 43 trouve sa bonne place
à l'indice du pivot 3 )
On verra plus loin la technique de la partition.
On réapplique de nouveau le QuickSort pour la partie gauche
(indices 0 à 2) et la partie droite (indices 4 à 8) du tableau.
Cette réapplication nous montre le concept de la récursivité.
Quelle est la condition d'arrêt ?
- on tri une partie du tableau quand elle contient au moins deux
valeurs à mettre en ordre. C'est-à-dire : l'indice gauche est
inférieur à l'indice droite. Sinon, la partie est triée.
Quelle est la réduction du problème à celui d'un ordre inférieur ?
- au lieu d'appliquer le QuickSort sur tout le tableau,
on l'applique sur deux sous-tableaux : celui à gauche
de l'indice du pivot et celui à droite de cet indice.
Chacun de ces deux sous-tableaux contient moins
d'éléments, ce qui fait accélérer le processus de tri
(i.e. de la répartition).
Exemple1 :
Cet exemple permet de voir la programmation de la méthode du tri
rapide. On utilise un petit tableau de 7 éléments dont la simulation
du tri sera présentée en classe :
int t[10] = { 20, 15, 80, 32, 10, 90, 46 } ;
int nbElem = 7 ;
Solution :
/* Fichier : Q_Sort1.A95 : Tri rapide avec Quick Sort
Matière principale : le tri rapide
*/
#include
void partitionner(int t[], int, int, int *) ; /* prototype */
/* données simple pour démontrer que le tri rapide fonctionne */
int t[10] = { 20, 15, 80, 32, 10, 90, 46 } ;
int nbElem = 7 ;
void afficher(int t[], int nbElem, char * quand)
{ int i ;
printf("\nContenu du tableau %s\n\n", quand);
for (i = 0 ; i < nbElem ; i++)
printf(" %3d", t[i]);
printf("\n\n");
}
void quickSort (int t[], int gauche, int droite)
{
int indPivot ;
if (gauche < droite)
{ partitionner (t, gauche, droite, &indPivot);
quickSort(t, gauche, indPivot - 1 );
quickSort(t, indPivot+1, droite);
}
}
void echanger(int * a, int * b) /* transmis par pointeur */
{
int tempo ;
tempo = *a , *a = *b, *b = tempo ; /* opérateur séquentiel "," */
}
void partitionner(int t[], int debut, int fin, int * indice)
{
int g = debut , d = fin ;
int valPivot = t[debut];
do
{ while (g
