Cours sur la récursivité

Une définition... récursive !

"Une procédure récursive est une procédure récursive."

Une définition plus "sérieuse"

Une procédure récursive est une procédure qui s'appelle elle-même.

La récursivité est un domaine très intéressant de l'informatique, un peu abstrait, mais très élégant; elle permet de résoudre certains problèmes d'une manière très rapide, alors que si on devait les résoudre de manière itérative, il nous faudrait beaucoup plus de temps et de structures de données intermédiaires.

La récursivité utilise toujours la pile du programme en cours.

On appelle "pile" une zone mémoire réservée à chaque programme; sa taille peut être fixée manuellement par l'utilisateur. Son rôle est de stocker les variables locales et les paramètres d'une procédure. Supposons que nous sommes dans une procédure "proc1" dans laquelle nous avons des variables locales. Ensuite nous faisons appel à une procédure "proc2"; comme le microprocesseur va commencer à exécuter "proc2" mais qu'ensuite il reviendra continuer l'exécution de "proc1", il faut bien stocker quelque part les variables de la procédure en cours "proc1"; c'est le rôle de la pile. Tout ceci est géré de façon transparente pour l'utilisateur. Dans une procédure récursive, toutes les variables locales sont stockées dans la pile, et empilées autant de fois qu'il y a d'appels récursifs. Donc la pile se remplit progressivement, et si on ne fait pas attention on arrive à un "débordement de pile". Ensuite, les variables sont désempilées (et on dit "désempilées", pas "dépilées").

Dans ce qui suit, nous allons utiliser le terme "procédure" pour désigner aussi bien une procédure qu'une fonction.

Une procédure récursive comporte un appel à elle-même, alors qu'une procédure non récursive ne comporte que des appels à d'autres procédures.

Toute procédure récursive comporte une instruction (ou un bloc d'instructions) nommée "point terminal" ou "point d'appui" ou "point d'arrêt", qui indique que le reste des instructions ne doit plus être exécuté.

procedure recursive(paramètres);
// déclaration des variables locales
begin
if TEST_D'ARRET then
   begin
   instructions du point d'arrêt
   end
else  //----- exécution 
   begin
   instructions;
   recursive(paramètres changés);  // appel récursif
   instructions;
   end;
end;

On constate, et il le faut, que les paramètres de l'appel récursif changent; en effet, à chaque appel, l'ordinateur stocke dans la pile les variables locales; le fait de ne rien changer dans les paramètres ferait que l'ordinateur effectuerait un appel infini à cette procédure, ce qui se traduirait en réalité par un débordement de pile, et d'arrêt de l'exécution de la procédure en cours. Grâce à ces changements, tôt ou tard l'ordinateur rencontrera un ensemble de paramètres vérifiant le test d'arrêt, et donc à ce moment la procédure récursive aura atteint le "fond" (point terminal). Ensuite les paramètres ainsi que les variables locales sont désempilées au fur et à mesure qu'on remonte les niveaux.

Nous allons étudier en détail maintenant le mécanisme de la récursivité sur un exemple concret, la combinaison des lettres d'une chaîne de caractères (ou anagrammes). La réalisation de la procédure récursive faisant cela sera étudiée plus loin, nous allons décrire ici le mécanisme interne et le stockage des paramètres et des variables locales.

procedure combinaison2(st, tete: string);
var i: integer;
begin
  if length(st) = 1 then memo1.lines.add(tete + st)
  else
    for i := 1 to length(st) do
    begin
      combinaison1(copy(st, 2, length(st) - 1), tete + st[1]);
      st := copy(st, 2, length(st) - 1) + st[1];
    end;
end;

voici l'appel de cette procédure : combinaison('abc','');