Récursivité en Langage C

La notion de récursivité est avant tout un problème algorithmique plus qu'au niveau du langage lui-même. Que ce soit en C, C++, Java, VB, Python, etc.., l'implémentation d'une fonction récursive se fera toujours plus ou moins de la même manière. Ici nous allons traiter de la récursivité avec le Langage C, telle est notre rubrique !

Mais qu'est-ce que la récursivité ? Et bien en fait d'un point de vue théorique cela reste assez simple ; il s'agit de programmes ou de fonctions d'un programme qui ont la faculté de s'appeler eux-mêmes (on entend également le terme d'autoappel ce qui est logique). La récursivité est une manière simple et élégante de résoudre certains problèmes algorithmiques, notamment en mathématique, mais cela ne s'improvise pas, il convient donc de savoir comment ce principe fonctionne.

Nous allons voir deux types de fonctions récursives: les fonctions récursives et les fonctions récursives terminales.

Les fonctions récursives comme cité plus haut, sont donc des fonctions s'appelant elles-mêmes, elles sont également un moyen rapide pour poser certains problèmes algorithmiques ; nous allons voir en détail comment elles fonctionnent.

Prenons un problème simple, mais auquel vous n'avez peut-être pas pensé à utiliser la récursivité: le calcul d'une factorielle. Considérons n! (qui se lit: factorielle de n) comme étant la factorielle à calculer, nous aurons ceci: 6! = 6x5x4x3x2x1. Dans cette situation, nous pouvons déjà déterminer notre règle de sortie de notre fonction récursive: la valeur 1 qui symbolise la fin de la récursion !

En effet, il faut une condition de sortie pour la fonction, mais il faut être très vigilant quant au choix de la condition, vous devrez être sûr qu'elle soit validée à un moment ou à un autre sinon c'est comme si vous créez une boucle infinie sans condition de sortie !

La règle de récursion que nous devons définir, est le calcul de la factorielle en elle même soit, si nous considérons notre exemple sur 6!, cité précédemment, nous pouvons définir notre règle de cette manière: n! = (n) (n-1) (n-2) … (1). Nous pouvons en déduire que nous allons faire des appels en décrémentant la valeur de n à chaque appel de la fonction jusqu'à ce que n == 1 !

Vous me direz surement, quoi des maths alors que nous parlons de développement en Langage C ! Hé oui, comme cité plus haut c'est avant tout un problème algorithmique et notre exemple est un exemple mathématique comme c'est le cas pour beaucoup d'algorithmes tout de même, mais je vous rassure, nous n'irons pas plus loin que ça en maths, c'est tout , nous avons ce qu'il nous faut pour créer notre fonction récursive, la voici :

unsigned long factoriel (int n)
{
   if (n < 0) {
      exit (EXIT_FAILURE);
   }
   else if (n == 1 || n == 0) {
      return 1L;
   }
 
   return n * factoriel (n - 1);
}

Nous pouvons observer ici que le dernier return est en fait l'appel récursif et nous soustrayons 1 à chaque appel jusqu'à ce que n == 1 qui est, comme décrit plus haut, notre condition de sortie.

Non, cela ne s'arrête pas là et c'est ici que nous allons voir le fonctionnement des fonctions récursives. Lorsque la fonction rencontre la condition de sortie, elle remonte dans tous les appels précédents pour calculer n avec la valeur précédemment trouvée !

Les appels des fonctions récursives sont en fait empilés (pile qui est une structure de données régie selon le mode LIFO: Last In First Out, Dernier Entré Premier Sorti). Chaque appel se trouve donc l'un à la suite de l'autre dans la pile du programme. Une fonction de ce type possède donc deux parcours: la phase de descente et la phase de remontée.

Voyons ceci grâce à un petit schéma :

Nous voyons très bien la phase de descente et de remontée dans la pile des appels de la fonction récursive. Ce n'est qu'au moment de la remontée, donc également au moment où la condition de sortie est vraie, que les appels enregistrés sont dépilés au fur et à mesure de la remontée. Ici pour des petits calculs cela convient très bien, mais lorsqu'il s'agit de faire de plus profondes récursions, un autre type de fonction récursive existe, mais n'est pas forcément connue de tout le monde, c'est la récursivité terminale, que nous allons étudier dans le prochain chapitre.

Avec ce que nous avons vu plus haut, imaginez un instant que vous devez calculer le factoriel d'un très grand nombre, par exemple, un calcul de probabilité sur le tirage des boules de Loto ! Oui, si vous connaissez les calculs de probabilités, voire les combinatoires, vous savez que les calculs de factorielles y sont omniprésents, mais, je ne vais pas trop entrer dans les détails pour ceux qui ne sont pas très familiers avec ce genre de connaissances mathématiques.

Nous allons simplement imaginer les inconvénients qu'une récursivité normale peut avoir sur des récursions plus profondes. Imaginez une grille de Loto, elle contient 49 numéros dont seulement 6 peuvent êtres tirés au sort. En restant dans un calcul simple pour ne pas trop nous dérouter du sujet, nous aurions une formule comme ceci pour calculer des probabilités :

Ici, nous devrions calculer le factoriel de 49 ce qui nous donne: 49! = 49x48x47 … 8x7x6! ; le résultat obtenu est d'une grandeur inimaginable !

Mais cela n'est pas le sujet, c'est juste pour vous montrer que de cette manière, avec une récursivité normale, nous avons (49-6)x2 passages soit 43 appels empilés l'un après l'autre sans compter qu'il faut également remonter tous les appels ce qui nous fait un total de 86 passages. Vous pouvez vous imaginer la perte de temps sur des récursions encore plus profondes et qui risqueraient par ailleurs de faire exploser la pile ce qui conduirait irrémédiablement au plantage du programme !

C'est là que peuvent intervenir les récursions terminales ! Mais c'est quoi ? Me direz-vous ! Et bien c'est une récursion avec uniquement une phase de descente, sans remontée. Ceci est possible, car la dernière expression return factoriel_terminale (…) de notre fonction nous renvoie directement la valeur obtenue par l'appel récursif courant, sans qu'il n'y ait d'autres opérations à faire, ce qui n'est pas le cas dans notre fonction récursive simple, où l'on multiplie n par le retour de la fonction. En conséquence, les appels de la fonction n'ont pas besoin d'être empilés, car l'appel suivant remplace simplement l'appel précédent dans le contexte d'exécution.

En considérant le même calcul que dans le chapitre précédent, soit calculer 6!, voici l'implémentation de notre fonction récursive terminale :

unsigned long factoriel_terminal (int n, unsigned long result)
{
   if (n < 0) {
      exit (EXIT_FAILURE);
   }
 
   if (n == 1) {
      return result;
   }
   else if (n == 0) {
      return 1L;
   }
 
   return factoriel_terminal (n - 1, n * result);
}

Nous remarquons ici que nous avons pris un argument supplémentaire, ceci est un passage obligatoire pour créer une récursivité terminale ; de cette manière, la dernière instruction est bel et bien la fin de l'appel courant de notre fonction et donc l'appel suivant peut prendre la place de la précédente, car le résultat se trouve dans notre second argument.

Comme à l'accoutumée, observons un petit schéma pour mieux nous représenter le parcours de la fonction :

Le schéma nous prouve bel et bien qu'il n'y a qu'une phase de descente, mais pas de remontée. De cette manière nous économisons l'utilisation de la pile du programme, et nous gagnons également du temps en exécution, c'est prodigieux !

Les fonctions récursives étant un moyen assez puissant pour résoudre certains problèmes de façon élégante, elles n'en restent pas moins dangereuses, et ce pour plusieurs raisons.

IV-A. Dépassement de capacité▲

IV-B. Débordement de pile (Stack Overflow)▲

IV-C. Forme itérative▲

unsigned long factoriel_iterative (unsigned int n)
{
   unsigned long ret = 1;
   unsigned int i = 1;
 
   for (i = 1; i <= n; i++)
   {
      ret *= i;
   }
 
   return ret;
}

Ici, vous pouvez télécharger le code source complet avec le programme d'exemple et un projet Code::Blocks version Windows : recursivite.zip

#include <stdio.h>
#include <stdlib.h>
 
 
/*
 * Fonction recursive simple.
 */
unsigned long factoriel (int n)
{
   if (n < 0) {
      exit (EXIT_FAILURE);
   }
   else if (n == 1 || n == 0) {
      return 1L;
   }
 
   return n * factoriel (n - 1);
}
 
 
/*
 * Fonction recursive terminale.
 */
unsigned long factoriel_terminal (int n, unsigned long result)
{
   if (n < 0) {
      exit (EXIT_FAILURE);
   }
 
   if (n == 1) {
      return result;
   }
   else if (n == 0) {
      return 1L;
   }
 
   return factoriel_terminal (n - 1, n * result);
}
 
 
/*
 * Fonction iterative.
 */
unsigned long factoriel_iterative (unsigned int n)
{
   unsigned long ret = 1;
   unsigned int i = 1;
 
   for (i = 1; i <= n; i++)
   {
      ret *= i;
   }
 
   return ret;
}
 
 
int main (void)
{
   unsigned long ret = 0;
 
 
   /*
    * Recursivite simple.
    */
   ret = factoriel (6);
   printf ("6! = %ld\n", ret);
 
 
   /*
    * Recursivite terminale.
    */
   ret = 0;
   ret = factoriel_terminal (6, 1);
   printf ("6! = %ld\n", ret);
 
 
   /*
    * Fonction iterative.
    */
   ret = 0;
   ret = factoriel_iterative (6);
   printf ("6! = %ld\n", ret);
 
 
   return EXIT_SUCCESS;
}

Un grand merci à farscape, PRomu@ld, gl et gorgonite pour leurs avis, remarques, conseils et précisions. Également un gros merci à wichtounet pour sa relecture et correction !