En informatique, la récursivité est une technique élégante et puissante dans laquelle une fonction s'appelle elle-même pour résoudre un problème en le décomposant en sous-problèmes identiques de taille plus réduite.

De nombreux algorithmes classiques (parcours d'arbres, recherche dichotomique, tri rapide QuickSort, fractales) s'expriment avec une clarté mathématique éblouissante grâce à la récursivité.

---

1. Les deux règles d'or de la récursivité

Pour qu'une fonction récursive s'exécute correctement sans bloquer votre machine, elle doit impérativement respecter deux composantes :

flowchart TD
    Appel[Appel de la fonction récursive] --> Test{Sommes-nous sur le Cas de Base ?}
    Test -- Oui --> Base["CAS DE BASE (Arrêt)\nRenvoie directement une valeur sans nouvel appel"]
    Test -- Non --> Rec["CAS RÉCURSIF (Réduction)\nAppelle la fonction avec un argument strictement plus petit (n - 1)"]
    Rec --> Test

1. Le cas de base (Base Case) : C'est la condition d'arrêt immédiate qui renvoie un résultat sans effectuer de nouvel appel récursif.
2. Le cas récursif (Recursive Step) : C'est l'appel de la fonction sur une version simplifiée du problème qui doit infailliblement converger vers le cas de base.

[!WARNING] Si vous omettez le cas de base ou si votre condition ne converge jamais, la fonction s'appellera indéfiniment jusqu'à saturer la mémoire allouée à la pile d'exécution : c'est le redouté débordement de pile (Stack Overflow).

---

2. Exemple fondamental : Le calcul de la factorielle

Par définition mathématique : $\(n! = \begin{cases} 1 & \text{si } n = 0 \quad \text{(Cas de base)} \\ n \times (n-1)! & \text{si } n \ge 1 \quad \text{(Cas récursif)} \end{cases}\)$

Implémentation en C

factorielle_recursive.c

#include <stdio.h>

long long Factorielle(int n)
{
    // 1. CAS DE BASE : 0! = 1
    if (n <= 0)
    {
        return 1;
    }

    // 2. CAS RÉCURSIF : n * (n - 1)!
    return n * Factorielle(n - 1);
}

int main(void)
{
    int valeur = 5;
    printf("%d! = %lld\n", valeur, Factorielle(valeur)); // Affiche 120
    return 0;
}

---

3. Ce qui se passe en mémoire : La pile d'appels (Call Stack)

Lors de l'appel Factorielle(3), l'ordinateur empile successivement chaque appel en mémoire, puis dépile les résultats une fois le cas de base atteint :

sequenceDiagram
    autonumber
    actor Main as main()
    participant F3 as Factorielle(3)
    participant F2 as Factorielle(2)
    participant F1 as Factorielle(1)
    participant F0 as Factorielle(0)

    Main->>F3: Appel Factorielle(3)
    F3->>F2: Attend 3 * Factorielle(2)
    F2->>F1: Attend 2 * Factorielle(1)
    F1->>F0: Attend 1 * Factorielle(0)
    Note over F0: CAS DE BASE atteint ! Renvoie 1
    F0-->>F1: Renvoie 1 -> Calcule 1 * 1 = 1
    F1-->>F2: Renvoie 1 -> Calcule 2 * 1 = 2
    F2-->>F3: Renvoie 2 -> Calcule 3 * 2 = 6
    F3-->>Main: Renvoie 6

---

4. Exemple 2 : La suite de Fibonacci

La suite de Fibonacci modélise la croissance d'une population : $\(F(0) = 0, \quad F(1) = 1, \quad F(n) = F(n-1) + F(n-2) \quad \text{pour } n \ge 2\)$

fibonacci.c

#include <stdio.h>

int Fibonacci(int n)
{
    // Cas de base multiples
    if (n == 0) return 0;
    if (n == 1) return 1;

    // Double appel récursif
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

int main(void)
{
    printf("Les 8 premiers termes de Fibonacci :\n");
    for (int i = 0; i < 8; i++)
    {
        printf("%d ", Fibonacci(i)); // Affiche : 0 1 1 2 3 5 8 13
    }
    printf("\n");
    return 0;
}

[!NOTE] La version récursive naïve de Fibonacci engendre un arbre d'appels binaire exponentiel de complexité \(\mathcal{O}(2^n)\), recalculant de multiples fois les mêmes valeurs (ex: \(F(3)\) est recalculé plusieurs fois). Pour des grands \(n\), une approche itérative en \(\mathcal{O}(n)\) est bien plus économe.

---

5. Exemple 3 : Algorithme d'Euclide pour le PGCD

L'algorithme séculaire d'Euclide pour déterminer le Plus Grand Commun Diviseur (PGCD) de deux entiers \(a\) et \(b\) s'exprime de façon saisissante en récursif :

\[\text{pgcd}(a, b) = \begin{cases} a & \text{si } b = 0 \\ \text{pgcd}(b, a \pmod b) & \text{sinon} \end{cases}\]

pgcd.c

#include <stdio.h>

int PGCD(int a, int b)
{
    // Cas de base : si b est nul, le PGCD est a
    if (b == 0)
    {
        return a;
    }

    // Cas récursif : PGCD de b et du reste a % b
    return PGCD(b, a % b);
}

int main(void)
{
    int a = 60, b = 24;
    printf("PGCD(%d, %d) = %d\n", a, b, PGCD(a, b)); // Affiche 12
    return 0;
}

---

6. Récursivité vs Itération : Tableau comparatif

Critère	Récursivité	Itération (Boucles for, while)
Lisibilité mathématique	Très naturelle pour les structures inductives (arbres, fractales).	Parfois verbeuse avec variables d'état temporaires.
Consommation mémoire	Élevée (chaque appel réserve un cadre sur la pile RAM).	Constante \(\mathcal{O}(1)\) en mémoire.
Vitesse d'exécution	Légèrement plus lente (coût d'appel de fonction et empilement).	Vitesse maximale (sauts d'instructions directs en assembleur).
Risque majeur	Débordement de pile (Stack Overflow).	Boucle infinie saturant le CPU.

---

7. Mise en pratique : Calcul récursif de la puissance (\(x^n\))

Énoncé : Implémentez une fonction récursive double Puissance(double x, int n) qui calcule \(x^n\) pour tout entier \(n \ge 0\), sachant que \(x^0 = 1\) et \(x^n = x \times x^{n-1}\).

??? tip "Solution complète"

#include <stdio.h>

double Puissance(double x, int n)
{
    // 1. Cas de base : tout nombre à la puissance 0 vaut 1
    if (n == 0)
    {
        return 1.0;
    }

    // 2. Cas récursif : x * x^(n-1)
    return x * Puissance(x, n - 1);
}

int main(void)
{
    double base = 2.0;
    int exposant = 8;

    printf("%.1f puissance %d = %.1f\n", base, exposant, Puissance(base, exposant)); // Affiche 256.0
    return 0;
}

---

Vous maîtrisez désormais les fonctions simples et récursives. Découvrons comment séparer notre code en modules multifichiers avec les en-têtes .h et les fichiers sources .c.

Partagez sur les réseaux sociaux

Commentaires