Note : codes disponibles uniquement en C.

Les exemples d'utilisation des fonctions récursives que nous avons vus jusqu'à présent avaient tous une nature récursive, car ils mettaient en oeuvre des éléments imbriqués les uns dans les autres. Comme nous allons le voir, il aurait tout à fait été possible de programmer ces exemples sans utiliser de fonctions récursives. De la même manière, il n'est pas nécessaire qu'un problème ait en lui-même une nature récursive, pour qu'il soit possible de le résoudre très simplement avec une fonction récursive.

Prenons par exemple le calcul de la factorielle d'un nombre, une fonction mathématique qui pour une valeur entière positive, retourne le produit de tous les entiers entre 1 et cette valeur. Pour une valeur nulle, la fonction retourne 1. Par exemple, la factorielle de 5, que l'on note "5!", vaut 1*2*3*4*5 = 120.

On peut écrire la fonction factorielle sous la forme d'une simple boucle, de la manière suivante :

int factorielle(int valeur)
{
   int total = 1;
   int curValeur;
   for (curValeur = 1; curValeur <= valeur; curValeur++)
      total *= curValeur;
   return total;
}

Il est cependant possible de donner une définition récursive de la fonction factorielle :

La factorielle d'un nombre N vaut 1 si N est égal à 0, et N multiplié par la factorielle de N - 1 sinon.

Cette définition est parfaitement équivalente à la précédente, et peut se traduire en code par une fonction récursive :

int factorielle(int valeur)
{
   if (valeur == 0)
      return 1;
   else
      return valeur * factorielle(valeur - 1);
}

On peut remarquer que le code de cette deuxième version est plus simple que la version avec une boucle, et qu'il peut se lire quasiment comme une définition.

La première version, qui utilise une boucle, est ce que l'on appelle une implémentation itérative de la fonction factorielle : on effectue un certain nombre d'itérations d'une boucle. La deuxième version s'appelle tout simplement l'implémentation récursive.

Une grande partie des problèmes peut se résoudre avec une implémentation récursive, comme avec une implémentation itérative. L'une ou l'autre peut paraître plus ou moins naturelle suivant le problème, ou suivant les habitudes du programmeur. Avec un peu d'habitude, utiliser l'implémentation récursive permet souvent d'avoir un programme plus simple, plus facile à comprendre, donc à débugger.

L'implémentation récursive a cependant deux principaux inconvénients, qui peuvent être gênants dans certains cas :

• Un appel de fonction prend plus de temps qu'une simple itération de boucle.
• Un appel de fonction utilise une petite quantité de mémoire.

Le premier inconvénient fait que des programmes implémentés avec une fonction récursive seront souvent légèrement plus lents que leurs équivalents itératifs. Si le moindre gain de vitesse pour cette partie de votre programme est important, il peut donc être préférable d'utiliser une implémentation itérative. Dans le cas contraire, la perte de performances peut être largement compensée par le gain en clarté du code, donc en réduction de risques de laisser des bugs.

Le deuxième inconvénient peut être très gênant si le nombre d'appels imbriqués est très important. Chaque appel de fonction imbriqué utilise une certaine quantité de mémoire, plus ou moins importante selon le nombre de paramètres et de variables de votre fonction. Cette mémoire est libérée dès que l'exécution de la fonction se termine, mais dans le cas d'une fonction récursive, cette quantité de mémoire est multipliée par le nombre d'appels imbriqués à un moment donné. Si ce nombre d'appels imbriqués peut atteindre des centaines de milliers, voire des millions, on peut facilement atteindre des méga-octets de mémoire, pour un calcul qui ne prendrait aucune mémoire avec une fonction itérative.

Dans le cas du calcul de la factorielle, le nombre d'appels récursifs imbriqués est égal à la valeur passée en paramètre. En pratique, on ne peut pas dépasser 12, car 13! vaut plus de 4 milliards, donc que le résultat du calcul ne peut être stocké dans un entier 32 bits. La mémoire utilisée est alors négligeable.

Dans certains cas, le compilateur est capable d'éviter de lui-même ces deux inconvénients, en transformant automatiquement votre fonction récursive en un programme itératif. Ceci reste cependant assez rare, et il ne faut donc pas trop compter dessus avec les compilateurs actuels.

Un programme itératif se base sur des boucles pour traiter un certain nombre d'éléments. Un programme itératif simple peut donc ressembler à l'exemple suivant, qui affiche un certain nombre de fois un caractère :

void afficheLigne(int nbAffichages, char caractere)
{
   int affichages;
   for (affichages = 0; affichages < nbAffichages; affichages++)
      printf("%c", caractere);
   printf("\n");
}

Pour écrire une version récursive de ce programme, on commence par se demander dans quel cas la boucle n'est pas du tout utilisée. En l'occurence, il s'agit du cas où le paramètre nbAffichages vaut 0, donc qu'on ne fait qu'afficher le retour à la ligne. On peut alors commencer à écrire une fonction qui gère ce cas :

void afficheLigne(int nbAffichages, char caractere)
{
   if (nbAffichages == 0)
      printf("\n");
}

Reste à gérer le cas où il y a des choses à afficher. Le principe de la fonction récursive est qu'elle s'occupe d'une seule étape, et laisse les étapes suivantes pour les appels imbriqués. Dans le cas où il y a des caractères à afficher, la fonction doit donc afficher un caractère, puis se rappeler, avec comme paramètre le nombre de caractères restant à afficher. Il s'agit de la valeur qu'on lui a transmise, diminuée de 1 :

void afficheLigne(int nbAffichages, char caractere)
{
   if (nbAffichages == 0)
      printf("\n");
   else
   {
      printf("%c", caractere);
      afficheLigne(nbAffichages-1, caractere);
   }
}

Cette fonction réalise exactement la même chose que la version itérative. On peut ainsi dire en français : pour afficher une ligne de N caractères, il faut afficher un caractère, puis afficher une ligne de N-1 caractères.