Introduction à la récursivité

Fait partie de la section Logique et Flux du Journey C++ de Coddy — leçon 45 sur 56.

La récursion est une technique de programmation dans laquelle une fonction s'appelle elle-même pour résoudre un problème. Au lieu d'utiliser des boucles, les fonctions récursives décomposent des problèmes complexes en sous-problèmes plus petits et similaires jusqu'à ce qu'elles atteignent un cas simple qui peut être résolu directement.

Chaque fonction récursive doit avoir deux composants essentiels. Le cas de base est une condition qui arrête la récursion - sans lui, la fonction s'appellerait indéfiniment. L'étape récursive est le moment où la fonction s'appelle elle-même avec des paramètres modifiés, se rapprochant du cas de base à chaque appel.

Voici un exemple simple de compte à rebours qui illustre la récursivité :

void countdown(int n) {
    if (n <= 0) {           // Cas de base : s'arrêter quand n atteint 0
        std::cout << "Done!" << std::endl;
        return;
    }
    
    std::cout << n << std::endl;
    countdown(n - 1);       // Étape récursive : appeler avec n-1
}

Lorsque vous appelez countdown(3), il affiche 3, puis appelle countdown(2), qui affiche 2, puis appelle countdown(1), et ainsi de suite jusqu'à ce qu'il atteigne le cas de base. Chaque appel de fonction attend que le suivant se termine avant de finir, créant une chaîne d'appels qui finit par se défaire pour revenir à l'appelant d'origine.

Aide-mémoire

La récursion se produit lorsqu'une fonction s'appelle elle-même pour résoudre un problème en le divisant en sous-problèmes plus petits.

Chaque fonction récursive a besoin de :

Cas de base : condition qui arrête la récursion
Étape récursive : la fonction s'appelle elle-même avec des paramètres modifiés

Exemple de fonction de compte à rebours :

void countdown(int n) {
    if (n <= 0) {           // Cas de base
        std::cout << "Done!" << std::endl;
        return;
    }
    
    std::cout << n << std::endl;
    countdown(n - 1);       // Étape récursive
}

Essayez vous-même

Cette leçon ne comprend pas de défi de code.