Récursivité

Une fonction est dite récursive lorsqu’elle s’appelle elle-même, ce qui est parfaitement autorisé :

void baoum(void){     baoum();}

Si nous avons emprunté à Balzac l’interjection « baoum » (voyez le début du « Colonel Chabert »), c’est pour bien montrer que l’appel d’une telle fonction provoquera un plantage du programme ; en effet, la fonction s’appelle elle-même indéfiniment, jusqu’à ce que la pile déborde, provoquant des effets variés (dans le genre horrible).

En pratique, une fonction récursive aura toujours au moins une instruction conditionnelle if ou switch, afin que dans certains cas au moins, il n’y ait pas d’appel récursif.

Un exemple traditionnel de fonction récursive est la fonction factorielle. Cette fonction calcule la factorielle d’un entier n, c’est-à-dire le produit de tous les nombres de 1 à n. Comme visiblement la factorielle de n est n fois la factorielle de n-1, il est tentant d’écrire :

double fact(int n){     if (n > 1) return n*fact(n-1);     else return 1;}

Nous avons utilisé le type double car les factorielles sont des nombres entiers très grands.

Il s’agit d’un très mauvais exemple d’utilisation de la récursivité, car la même fonction se calcule visiblement bien plus facilement avec une simple boucle :

double fact(int n){     double f = 1;     while (n > 1) f *= n--;     return f;}

D’une façon générale, les fonctions récursives de la forme :

if (condition) appel-récursif;else pas_d’appel_récursif;

seront bien mieux écrites sans récursivité par une simple boucle de la forme while (condition) (par exemple).

Il existe même des cas de récursivité catastrophique. Un exemple frappant est donné avec les nombres de Fibonacci. Il s’agit d’une suite de nombres, les premiers égaux à 0 et 1, et chacun des autres égal à la somme des deux précédents :

0 1 1 2 3 5 8 13 21 34 ...

Il est alors tentant d’écrire :

long fib(unsigned n){     if (n > 1) return fib(n-1) + fib(n-2);     else return n;}

Grave erreur, car le temps d’exécution de cette fonction devient vite prohibitif, surtout comparé à une version non récursive.

Exercice 5.3	Écrire une version non récursive de la fonction fib.
Voir solution

En effet, chaque appel de fib se répercute en deux appels, si bien que pour calculer fib(26), par exemple, il faut environ 2²⁵ = 33 554 432 appels, et plus de 6 secondes sur la machine de test, tandis qu’il ne faut que 0.016 seconde, soit 400 fois moins, à la version non récursive (solution de l’exercice). De plus, la version non récursive est parfaitement capable de calculer fib(60) = 1 820 529 360 en moins d’une seconde, tandis qu’il faudrait sensiblement... 3 000 ans à la version récursive pour faire le calcul, et une pile de onze milliards de giga-octets !

De cette leçon, on retiendra que la récursivité ne doit pas être employée de façon irréfléchie. De très nombreux algorithmes sont présentés sous forme récursive ; mais il est souvent bien préférable, et parfois bien plus simple, de les programmer sans récursivité.

Dans certains cas cependant la récursivité est pratique. On ne doit pas hésiter à l’utiliser si l’on sait que seul un petit nombre d’appels récursifs seront faits. C’est le cas par exemple lorsqu’une fonction de lecture de fichier échoue. Elle peut alors afficher un message et, si l’utilisateur souhaite essayer à nouveau, se rappeler récursivement pour reprendre ; il est alors entendu qu’au bout de trois ou quatre essais, on abandonne.

Un cas intéressant est celui de la récursivité croisée. Il s’agit d’un groupe de fonctions qui s’appellent les unes les autres cycliquement. Par exemple, deux fonctions :

void fonction2(void);				void fonction1(void){     ...     fonction2();     ...}void fonction2(void){     ...     fonction1();     ...}

On notera que l’emploi d’un prototype est ici obligatoire, puisque aucune des deux fonctions ne peut être définie avant l’autre, sous peine de provoquer une erreur de compilation. De plus, comme dans le cas de la récursivité simple, il doit y avoir des instructions de branchement dans les fonctions.

Précédent

Sommaire

Suivant