Récursivité en C simplifiée : Écrire et utiliser des fonctions récursives

Récursivité en C simplifiée

Ce tutoriel vous guide à travers les fondamentaux de la récursivité en C, du concept de base à un exemple pratique qui somme les nombres naturels.

Une fonction récursive est celle qui s'appelle elle-même. Cette technique auto-référentielle — la récursivité — vous permet de résoudre des problèmes en les décomposant en sous-problèmes plus petits et identiques.

---

Comment fonctionne la récursivité

void recurser() {
    /* pré-traitement */
    recurser();
    /* post-traitement */
}
int main() {
    /* configuration initiale */
    recurser();
    /* suivi */
}

La récursivité se répète jusqu'à ce qu'une condition d'arrêt — souvent appelée cas de base — soit atteinte. L'utilisation d'une garde if…else ou d'une construction similaire assure que la fonction se termine éventuellement et évite une boucle infinie.

---

Exemple : Somme des nombres naturels en utilisant la récursivité

#include <stdio.h>
int somme(int n);
int main() {
    int nombre, resultat;
    printf("Entrez un entier positif : ");
    scanf("%d", &nombre);
    resultat = somme(nombre);
    printf("somme = %d", resultat);
    return 0;
}
int somme(int n) {
    if (n != 0)
        return n + somme(n-1); // Appel récursif
    else
        return 0; // Cas de base
}

Sortie

Entrez un entier positif: 3 somme = 6

---

Dans cet exemple, somme() est invoquée depuis main() avec l'entrée de l'utilisateur. La fonction s'appelle elle-même avec une valeur décrémentée de n jusqu'à ce que n atteigne zéro. À ce moment, le cas de base retourne 0, et les appels récursifs se défont, ajoutant chaque valeur intermédiaire jusqu'à main().

---

Avantages et inconvénients de la récursivité

La récursivité produit souvent un code plus propre et plus lisible, surtout pour les problèmes qui s'alignent naturellement sur des structures récursives — tels que les parcours d'arbres, le calcul de factorielle ou la suite de Fibonacci. Cependant, la récursivité peut être plus lente que les boucles itératives en raison de la surcharge des appels de fonction et de l'utilisation accrue de la mémoire depuis la pile d'appels. Dans le code critique pour les performances, envisagez une solution itérative ou la mémoisation pour atténuer ces coûts.

Malgré ses inconvénients potentiels, la récursivité reste un concept fondamental en informatique, sous-tendant de nombreux algorithmes et opérations sur les structures de données. Maîtriser la récursivité vous équipe pour aborder des problèmes complexes avec élégance et précision.