Notebook associé — Récursivité
Ouvrez le cours interactif au format Jupyter (.ipynb) pour exécuter le code pas à pas.
Télécharger le .ipynb
Voir la version HTML
Ouvrez le cours interactif au format Jupyter (.ipynb) pour exécuter le code pas à pas.
1. Pourquoi la récursivité ?
Une fonction récursive s’appelle elle‑même pour résoudre un problème en le réduisant à des sous‑problèmes de même nature. C’est utile quand la structure du problème est naturellement répétitive (décomposition d’un entier, parcours d’un dossier, arbres, fractales…).
- Exprimer un problème complexe en deux règles simples : un cas de base + une règle de réduction.
- Écrire un code court, proche de la définition mathématique.
- Préparer des preuves de correction par récurrence et raisonner sur la terminaison.
2. Caractérisation minimale
Deux ingrédients obligatoires
- Cas de base : une entrée simple où la réponse est immédiate.
- Appel récursif : on résout un cas plus grand en appelant la fonction sur un cas plus petit.