Leçon 17 - Récursivité

25 minutes Avancé P3 - Algorithmes

Découvrez la récursivité : quand une fonction s'appelle elle-même pour résoudre un problème.

Qu'est-ce que la récursivité ?

La récursivité, c'est quand une fonction s'appelle elle-même. Comme des poupées russes : pour ouvrir une grande poupée, on ouvre une plus petite, puis une encore plus petite, jusqu'à la dernière.

💡 Deux éléments essentiels :

Cas de base : Condition d'arrêt (sinon boucle infinie !)
Cas récursif : La fonction s'appelle avec un problème plus simple

Exemple 1 : La factorielle

Calculer 5! = 5 × 4 × 3 × 2 × 1 = 120

static int Factorielle(int n)
{
    // CAS DE BASE : arrêt de la récursion
    if (n <= 1)
    {
        return 1;
    }

    // CAS RÉCURSIF : on appelle la fonction avec n-1
    return n * Factorielle(n - 1);
}

// Utilisation
int resultat = Factorielle(5);
Console.WriteLine($"5! = {resultat}");  // Affiche: 5! = 120

Exemple 2 : Suite de Fibonacci

La suite : 0, 1, 1, 2, 3, 5, 8, 13, 21... (chaque nombre = somme des 2 précédents)

static int Fibonacci(int n)
{
    // CAS DE BASE
    if (n <= 1)
    {
        return n;
    }

    // CAS RÉCURSIF : fib(n) = fib(n-1) + fib(n-2)
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

// Afficher les 10 premiers nombres de Fibonacci
for (int i = 0; i < 10; i++)
{
    Console.Write($"{Fibonacci(i)} ");
}
// Affiche: 0 1 1 2 3 5 8 13 21 34

Exemple 3 : Puissance

Calculer 2^5 = 2 × 2 × 2 × 2 × 2 = 32

static double Puissance(double nombre, int exposant)
{
    // CAS DE BASE
    if (exposant == 0)
    {
        return 1;
    }

    if (exposant == 1)
    {
        return nombre;
    }

    // CAS RÉCURSIF
    return nombre * Puissance(nombre, exposant - 1);
}

// Test
Console.WriteLine($"2^5 = {Puissance(2, 5)}");  // Affiche: 2^5 = 32

Exemple 4 : Compter les fichiers dans un dossier

Parcourir récursivement une structure de dossiers (simulation) :

class Dossier
{
    public string Nom { get; set; }
    public List<Dossier> SousDossiers { get; set; } = new List<Dossier>();
    public int NombreFichiers { get; set; }
}

static int CompterTousFichiers(Dossier dossier)
{
    // Compter les fichiers dans ce dossier
    int total = dossier.NombreFichiers;

    // RÉCURSION : ajouter les fichiers des sous-dossiers
    foreach (var sousDossier in dossier.SousDossiers)
    {
        total += CompterTousFichiers(sousDossier);
    }

    return total;
}

// Création d'une structure de test
var racine = new Dossier
{
    Nom = "Projet",
    NombreFichiers = 2,
    SousDossiers = new List<Dossier>
    {
        new Dossier { Nom = "src", NombreFichiers = 5 },
        new Dossier { Nom = "tests", NombreFichiers = 3 }
    }
};

int total = CompterTousFichiers(racine);
Console.WriteLine($"Total de fichiers: {total}");  // Affiche: 10

⚠️ Attention aux pièges :

Oublier le cas de base → boucle infinie (stack overflow)
Trop de récursions → ralentit le programme
Alternative : Parfois une boucle for est plus simple et rapide

Exercice pratique

Créez une fonction récursive qui inverse une chaîne de caractères :
Exemple : "hello" → "olleh"