14. Introduction à la Récursivité

La récursivité est une technique où une fonction s'appelle elle-même, directement ou indirectement.

Elle est essentielle pour certains algorithmes (comme les parcours d'arbre, Quick Sort et Merge Sort).

Deux Règles Essentielles de la Récursivité

1. Cas de Base (Base Case) : Une condition qui arrête la récursivité. Sans cas de base, la fonction s'appellera elle-même à l'infini, entraînant une erreur de Stack Overflow.
2. Étape Récursive (Recursive Step) : La partie où la fonction s'appelle elle-même, généralement sur une version plus petite ou plus simple du problème original.

Exemple : Calcul de la Factorielle

La factorielle de 5 (5!) est 5 * 4 * 3 * 2 * 1. Remarquez que 5! = 5 * (4!). Cette auto-référence définit l'étape récursive.

python def factorial(n): # 1. Base Case: Stops when n is 0 or 1 if n <= 1: return 1 # 2. Recursive Step: Calls itself with a smaller input return n * factorial(n - 1)