La récursivité : un algorithme qui s'appelle lui-même
Objectif : définir une chose à partir d'elle-même sans tourner en rond
L’essentiel
Un algorithme RÉCURSIF résout un problème en s'appelant lui-même sur un problème PLUS PETIT. Cela paraît circulaire, et ce ne l'est pas — à deux conditions strictes, faute desquelles le raisonnement tourne effectivement en rond et le programme avec lui. PREMIÈRE CONDITION : un CAS DE BASE, un cas assez petit pour être résolu sans appel.
À retenir
- Un algorithme récursif s'appelle sur un problème strictement plus petit
- Il lui faut un cas de base, sinon la descente ne s'arrête jamais
- La descente empile les appels, la remontée calcule les résultats en sens inverse
- La récursivité s'impose sur les structures récursives, pas partout : elle peut coûter très cher
Le tableau à connaître
| La factorielle de n | La version itérative | La version récursive |
|---|---|---|
| Le principe | Multiplier de 1 jusqu'à n dans une boucle | n fois la factorielle de n moins 1 |
| Le cas de base | Le résultat part à 1 | factorielle(0) vaut 1, sans appel |
| Ce qui décroît | Le compteur monte vers n | L'argument descend vers 0 |
| Ce qu'on lit | Comment on calcule | CE QU'EST le résultat |
⚠ Attention, piège
- Récursif ne veut pas dire efficace. La suite de Fibonacci définie récursivement recalcule les mêmes valeurs un nombre exponentiel de fois : fibonacci(50) écrit naïvement demande des milliards d'appels, là où une boucle de cinquante tours suffit.
Exemples
- Calculons factorielle(4).
Le plan de la leçon
- Se définir soi-même, légalement
- Deux définitions du même calcul
- Dérouler une descente et une remontée
- Quand elle s'impose vraiment
Je me teste
Que manque-t-il à « factorielle(n) vaut n fois factorielle(n moins 1) » ?
- Un compteur pour les tours de boucle
- Le cas de base pour arrêter la descente
- Une variable pour stocker le total
Dans le calcul de factorielle(4), quand le premier produit est-il effectué ?
- À la remontée, après le cas de base
- Avant tout appel, au départ
- À la descente, dès le premier appel
Le mot d’Oscar — Définissez-moi « ancêtre ».
Réponses : 1. B · 2. A