Subsections

• 1.1 Généralités sur la récursivité
  • 1.1.1 Définitions récursives
• 1.2 Fonctions récursives
  • Comment ça marche ?
• 1.3 Variables locales, arguments de fonctions et fonctions récursives
• 1.4 Les strutcures de données récursives

1 Récursivité

 

1.1 Généralités sur la récursivité

1.1.1 Définitions récursives

Un définition récursive ou par récurrence, un objet ou une action est défini en fonction d'un objet ou d'une action de même nature mais de compléxité moindre. Par exemple, on peut définir le factoriel d'un nombre n non négatif de deux manières:

• définition non récursive:

  n ! = n * n-1 * ... 2 * 1

• définition récursive:

  n ! = n * (n-1) ! et 0 ! = 1

  On remarquera que pour calculer n ! il nous faut pouvoir calculer $(n-1) !$.
  \begin{rawhtml} (n-1) ! Si l'on connait le factoriel d'un nombre p , alors en utilisant cette définition récursive, on pourra calculer le factoriel de des nombres p +1, p +2, etc ... Ainsi, une défintion récursive est composée de deux partie: une partie strictement récursive et une partie non récursive (base) servant de point de départ à l'utilisation de la définiton récursive.

1.2 Fonctions récursives

Comme pour les définition récursives, les fonctions récursives sont de fonctions qui sont appelées depuis leur propre corps de fonction soit directement soit indirectement à travers une ou plusieurs fonctions relais. Si la fonction P appelle directement P , on dit que la récursivité est directe. Si P appelle une fonction P₁ , qui appelle une fonction P₂ , ... , qui appelle une fonction P_n et qui enfin appelle P , on dit qu'il s'agit d'une récursivité indirecte.

La grande question qui se pase dans une fonction récursive est celle de l'arrêt de la récursivité. Prenons le cas de la récusivité directe pour simplifier la présentation: si la fonction P appelle dans son propre corps la fonction P , il est tout à fait logique de penser que cette ne s'arrêtera jamais et fonctionnera à << l'infini >> Il est donc primordial qu'une des branches de la fonction P permette de stopper la récursivité.

Pernons un exemple pour clarifier tout ça. Suppons que l'on veuille calculer la somme des n premiers entiers positifs. Une défintion récursive de cette somme serait:

somme(n) = n * somme(n-1) et somme(1) = 1

Ce qui se traduit en C par la fonction suivante:

int somme(int n) {
  int m;
  if (n==1) 
    return 1;
  else {
    m = somme(n-1);
    return n + m;
  }
}

Il est clair que sans le test if (n==1), cette fonction ne s'arrêterait jamais !

Comment ça marche ?

Imaginons qu'on appelle la fonction somme(4). Puisque 4 $\neq$ 1 , cette fonction va s'appeler elle-même avec la valeur 3 (somme(3)). Ce nouvel appel se termine en renvoyant une valeur (dans cet exemple la valeur retournée est 6 = 3 + 2 + 1). Cette valeur sera ajoutée à la valeur 4 et l'appel de somme(4) retournera la valeur 10 (4 + 6).

L'appel somme(3) suivra le même processus et appelera somme(2) qui lui-même fera appel à somme(1).

 

1.3 Variables locales, arguments de fonctions et fonctions récursives

Il est essentiel de comprendre que lorsqu'une fonction récursive définit des varibales locales, un exemplaire de chacune d'entre elles est créée à chaque appel récursif de la fonction. Dans notre exemple somme(4), la variable locale m est créée 4 fois. Ces variables sont restituées au fur et à mesure que l'on quitte la fonction comme toute variable locale d'une fonction.

Il en est de même des arguments des fonctions.

Considérons une fonction void miroir() récursive qui lit caractère par caractère une cahîne terminée par '?' et l'affiche dans l'ordre inverse de celui de la lecture. Exemple d'exécution:

Miroir, qui est la plus belle ? ? elleb sulp al tse iuq ,rioriM

Cette fonction pourrait ressembler à ceci:

 
void miroir() {
   int c = getchar();
   if (c != '?') {
      miroir();
      printf("%c", c);
   }
}
 

Cette même fonction sans vraibale locale aurait nécessité un tableau pour stocker tous les caractères jusqu'au caractère '?' pour ensuite les afficher dans l'ordre inverse.

1.4 Les strutcures de données récursives

Une structure de données récursives, tout comme une définition récursive, est une structure qui fait référence à elle-même. Les structures de données naturellement récursives sont les listes chaînées et les arbres que nous étudierons en détail dans les chapitres 3 et 2.