Sommaire

Exemples classiques de fonctions récursives

Voici un ensemble d’exemples souvent cités et bien intéressants pour s’approprier la récursivité et l’écriture de fonctions récursives.

1. Calculs

a. Afficher les chiffres d’un entier

Soit un entier de valeur 45671, il s’agit d’afficher successivement les caractères 4, 5, 6, 7, 1 et non plus la valeur de l’entier. Pour ce faire, tant que le résultat est supérieur à 0 on prend le modulo 10 qui donne le dernier chiffre, on divise par 10 et on recommence. En itératif cela donne :

void chiffreIter (int val) 
{ 
   while (val>0){ 
       printf("%d_", val%10); 
       val/=10; 
   } 
}

La version récursive est très simple, il suffit de remplacer la boucle par un appel récursif :

void chiffre(int val) 
{ 
   if (val>0){ 
      printf("%d_", val%10); 
      chiffre(val/10); 
   } 
}

b. Produit factoriel

Un produit factoriel c’est : n! = 1*2*3*...*n. La définition est :

n! = 1 si n=0

n! = n(n-1)! si n>0

Il s’agit d’une fonction de récurrence et on boucle sur n tant que n>0, voici une version de fonction itérative :

int factIter (int n) 
{ 
int res=1; 
   while (n>1) 
      res*=n--;  // attention décrémentation après multiplication 
   return res; 
}

D’une certaine façon, la version récursive peut sembler plus facile, plus proche ...