Maîtriser la récursivité en C : Bonnes pratiques et conditions de sortie

La récursivité est le processus de répétition d'éléments de manière auto-similaire. En programmation, si un programme permet d'appeler une fonction à l'intérieur de cette même fonction, on parle d'appel récursif.

void recursivite() {
  recursivite(); /* la fonction s'appelle elle-même */
}
int main() {
  recursivite();
}

Le langage C supporte la récursivité, c'est-à-dire qu'une fonction peut s'appeler elle-même. Mais en utilisant la récursivité, les programmeurs doivent faire attention à définir une condition de sortie de la fonction, sinon elle entrera dans une boucle infinie.

Les fonctions récursives sont très utiles pour résoudre de nombreux problèmes mathématiques, comme le calcul du factoriel d'un nombre, la génération de la suite de Fibonacci, etc.

Factoriel d'un nombre

L'exemple suivant calcule le factoriel d'un nombre donné en utilisant une fonction récursive :

Démonstration en direct

#include <stdio.h>
unsigned long long int factoriel(unsigned int i) {
  if (i <= 1) {
    return 1;
  }
  return i * factoriel(i - 1);
}
int main() {
  int i = 12;
  printf("Factoriel de %d est %llu\n", i, factoriel(i));
  return 0;
}

Lorsque le code ci-dessus est compilé et exécuté, il produit le résultat suivant :

Factoriel de 12 est 479001600

Suite de Fibonacci

L'exemple suivant génère la suite de Fibonacci pour un nombre donné en utilisant une fonction récursive :

Démonstration en direct

#include <stdio.h>
int fibonacci(int i) {
  if (i == 0) {
    return 0;
  }
  if (i == 1) {
    return 1;
  }
  return fibonacci(i-1) + fibonacci(i-2);
}
int main() {
  int i;
  for (i = 0; i < 10; i++) {
    printf("%d\t\n", fibonacci(i));
  }
  return 0;
}

Lorsque le code ci-dessus est compilé et exécuté, il produit le résultat suivant :

0
1
1
2
3
5
8
13
21
34