Retour à l'index
Un sous-programme est dit récursif lorsqu'il fait appel à lui-même ou à des sous-programmes qui lui font références. On parle de récursivité directe lorsque le sous-programme s'appelle lui-même et de récursivité croisée lorsque plusieurs sous-programmes s'appellent mutuellement.
Commençons par la récursivité directe, à propos d'exemples divers. La théorisation de cette notion ne concerne pas un cours d'initiation à la programmation tel que celui-ci.
| Un programme itératif | Nous savons programmer cette fonction sans faire appel à la récursivité. En général il intervient alors au moins une boucle, ou itération. On a donc le programme suivant :
#include <stdio.h>
int fact(int n)
{
int F, k;
F = 1;
for (k = 2; k <= n; k++)
F = F*k;
return F;
}
int main(void)
{
int n;
printf("n = ");
scanf("%d",&n);
printf("%d! = %d.\n", n, fact(n));
}
|
| Un programme récursif | Le programme récursif repose sur la définition récursive suivante de la fonction factorielle :
0! = 1; (n + 1)! = (n + 1) * n!; Ceci donne lieu au programme suivant :
#include <stdio.h>
int fact(int n)
{
if (n == 0)
return 1;
else
return n*fact(n-1) ;
}
int main(void)
{
int n;
printf("n = ");
scanf("%d",&n);
printf("%d ! = %d.\n", n, fact(n));
}
|
| Commentaire | On remarque que le corps de la function fait appel à la fonction elle-même. Nous n'avions jamais dit que cela était permis jusqu'à maintenant. Cela est permis dans certains langages de programmation tel que le langage C. Bien entendu cela complique l'implémentation d'un tel langage mais facilite la tâche du programmeur. |
| Introduction | Il ne faut pas croire que tout programme syntaxiquement correct avec des appels récursifs permet de définir une application. Considérons, par exemple, la pseudo-définition suivante :
IDIOT(n) = IDIOT(n+1) + 1. Il est évident qu'un programme associé à cette pseudo-déffinition va boucler quelle que soit la valeur de n. |
| Prospective | Une étude plus approfondie du problème de la justification des définitions par récurrence fait l'objet d'un cours plus avancé, comme nous l'avons déjà dit. |
| Le problème | On introduit une phrase au clavier se terminant par un point (et ne contenant pas d'autre point que celui-ci). Le programme doit écrire cette phrase à l'écran dans l'ordre inverse. Une session d'utilisation de ce programme sera, par exemple :
|
| Un algorithme itératif | Il suffit de considérer une phrase comme un tableau de caractères et d'énumérer les éléments de ce tableau dans l'ordre inverse. |
| Un algorithme récursif | On lit le premier caractère de cette phrase. Si c'est un point on l'affiche et c'est terminé. Sinon on fait appel à notre procédure pour la fin de la phrase (qui est un mot plus court) puis on affiche ce caractère et ce sera alors terminé. |
| Un programme récursif | Cet algorithme conduit au programme suivant pour un compilateur C pour MS-DOS :
#include <stdio.h>
#include <conio.h> /* non portable */
int inverse(void)
{
char C;
C = getche();
if (C != '.')
inverse();
else
printf("\nCette phrase dans l\'ordre inverse est :\n");
putchar(C);
}
int main(void)
{
printf("Ecrire une phrase :\n");
inverse();
}
|
| Introduction | Nous avons déjà vu l'intérêt du tri de tableaux et un certain nombre d'algorithmes naturels pour résoudre ce problème. Nous allons voir ici une autre méthode de tri, le tri-fusion (merge sort en anglais). |
| Principe du tri-fusion | L'idée de départ est simple : on sépare le tableau en deux parties égales (à un élément près si le nombre d'éléments n'est pas pair), on trie la première partie, on trie la deuxième partie, puis on fusionne ces deux parties triées, c'est-à-dire qu'on prend le plus petit élément du premier sous-tableau, le plus petit élément du deuxième sous-tableau et on place le plus petit des deux dans le nouveau tableau et on recommence ainsi de suite. Bien entendu pour trier les deux parties on fait de même, ce qui conduit à un algorithme récursif. Pour qu'il n'y ait pas de problème d'arrêt il suffit de remarquer qu'un tableau à un seul élément est nécessairement trié. |
| Première partie de l'algorithme | Ceci nous conduit, par exemple, à la fonction suivante, faisant appel à une fonction de fusion, qui trie la partie de tableau comprise entre les indices a et b inclus [on ne le fait pas seulement entre 1 et n à cause de l'appel récursif] :
#include <stdio.h>
const int max = 100;
void tri_fusion (int TA[ ], int a, int b )
{
int c;
if (a != b)
{
c = (a + b)/2;
tri_fusion(TA, a, c);
tri_fusion(TA, c+1, b);
fusion(TA, a, c, b);
}
}
|
| Principe de la fusion | Reste à écrire la fonction de fusion. Cette fonction a pour arguments un tableau TA, d'élements numérotés de 1 à n, et des entiers a, b, c tels que 1 a c < b n, les parties du tableau entre a et c d'une part, c + 1 et b d'autre part, étant triées. Cette fonction doit changer la valeur du tableau pour que la partie comprise entre a et b soit triée. L'idée est de considérer ces deux parties triées comme des tas de cartes triées. On prend la carte du dessus dans chacun des tas, on les compare, on met celle de valeur la plus petite dans un autre tas, on prend une nouvelle carte (s'il en reste) dans le tas auquel elle appartenait, et on continue ainsi de suite. |
| Deuxième partie de l'algorithme | Ceci nous conduit, par exemple, à la fonction suivante :
void fusion(int TA[ ], int a, int c, int b)
{
int TB[max]; /* tas auxiliaire */
int i, j, k, l; /* les indices respectifs de la premiere partie, de la deuxieme partie et du tas auxiliaire */
i = a;
j = c+1;
k = a;
while((i <= c) && (j <= b))
{
if (TA[i] < TA[j])
{
TB[k] = TA[i];
i++;
}
else
{
TB[k] = TA[j];
j++;
}
k++;
}
/* Si le deuxieme tas n'est pas vide */
if (j <= b)
for (l = j; l <= b; l++)
TB[l] = TA[l];
/* Si le premier tas n'est pas vide */
if (i <= c)
for (l = i; l <= c; l++)
{
TB[k] = TA[l];
k++;
}
/* On copie le tableau auxiliaire dans TA */
for (k = a; k <= b; k++)
TA[k] = TB[k];
}
|
| Un programme complet | Ceci nous conduit au programme complet suivant nous permettant de tester nos fonctions :
/* Fusion.c */
#include <stdio.h>
const int max = 100;
void fusion(int TA[ ], int a, int c, int b);
void tri_fusion (int TA[ ], int a, int b );
int main(void)
{
int TA[max];
int n, i;
/* Nombre effectif d'elements */
printf("Entrer le nombre d\'elements du tableau : ");
scanf("%d", &n);
/* Saisie du tableau */
for (i = 1; i <= n; i++)
{
printf("element numero %d : ", i);
scanf("%d", &(TA[i]));
}
/* Tri */
tri_fusion(TA, 1, n);
/* Affichage */
printf("Les elements sont, dans l\'ordre croissant : ");
for (i = 1; i <= n; i++)
printf(" %d", TA[i]);
putchar('\n');
}
|
| Le problème | On dispose de trois plots et de 64 disques tous de rayons diffiérents, percés en leur centre de façon à passer à travers les plots. Au départ les 64 disques sont sur le premier plot, rangés par taille, le plus grand tout en bas. Le but est de déplacer ces disques pour les amener sur le troisième plot en suivant les règles suivantes :
|
| Un algorithme récursif | Commençons par généraliser le problème au cas de n disques, le problème initial revenant à prendre n égal à 64.
Pour n = 1 c'est facile, il n'y a même pas à utiliser le plot du milieu : on déplace directement le disque du premier au troisième plot. Supposons que l'on sache résoudre le problème pour une valeur n et montrons qu'on peut alors le résoudre pour la valeur n + 1. En échangeant les rôles des plots 2 et 3, on peut déplacer n disques du plot 1 vers le plot 2, en utilisant le plot 3 comme plot auxiliaire. Déplaçons alors le disque restant (le plus grand) du plot 1 vers le plot 3. En échangeant le rôle des plots 1 et 2, on peut finalement déplacer les n disques du plot 2 vers le plot 3. |
| Précisions sur le cahier des charges | Ecrivons un programme qui, étant donnée l'entrée n, entier naturel non nul, nous donne la liste des déplacements à effectuer pour résoudre le problème, sous la forme :
|
| La fonction fondamentale | Nous avons vraiment intérêt à introduire la fonction DEPLACE(N, P, Q, R) qui consiste à déplacer N disques du plot P vers le plot R, en se servant du plot Q comme plot intermédiaire. |
| Implémentation | Ceci nous conduit au programme suivant :
#include <stdio.h>
void deplace(int n, int P, int Q, int R)
{
if (n == 1)
{
printf("Deplacer un disque du plot %d", P);
printf(" vers le plot %d\n", R);
}
else
{
deplace(n-1, P, R, Q);
deplace(1, P, Q, R);
deplace(n-1, Q, P, R);
}
}
int main(void)
{
int n;
printf("Entrer le nombre de disques : ");
scanf("%d", &n);
deplace(n, 1, 2, 3);
}
|
| Un exemple de session | Pour n = 3 on obtient :
|
Cours, éxercices ou graphismes libre de droit. Un mail est souhaitable | Webmestre : Aublet Bastien (bastien.aublet@hotmail.fr)