ULUMINE · Numérique et sciences informatiques (NSI) · Terminale
La récursivité
Une fonction récursive s’appelle elle-même sur une donnée plus petite, jusqu’à un cas de base qui arrête les appels.
Structure
- Cas de base : résultat direct, sans appel récursif.
- Appel récursif : sur un paramètre qui se rapproche du cas de base.
- Exemple : fact(0) = 1 et fact(n) = n × fact(n − 1).
Exécution
- Chaque appel est empilé dans la pile d’appels.
- Les calculs en attente se font à la remontée, une fois le cas de base atteint.
- Profondeur limitée (environ 1 000 en Python) : au-delà, RecursionError.
Terminaison et coût
- Terminaison : une quantité entière positive décroît strictement à chaque appel.
- Récursivité double (fib) : nombre d’appels exponentiel.
- Diviser n par 2 à chaque appel : environ log₂(n) appels.
Pièges à éviter
- Oublier le cas de base, ou écrire un cas de base jamais atteint (n − 2 avec n impair).
- Oublier le return devant l’appel récursif : la fonction renvoie alors None.
- Confondre l’ordre de la descente (appels) et de la remontée (calculs).