NSI (Spé) — Langages et programmation
Récursivité et modularité
Fonctions récursives, modules, tests et documentation
Résumé synthétiqueFiche en 4 sectionsQuiz de 10 questionsGratuit, sans pub
Résumé
La récursivité est une technique où une fonction s'appelle elle-même pour résoudre un problème en le décomposant en sous-problèmes plus simples. Toute fonction récursive a un cas de base (condition d'arrêt) et un cas récursif (appel avec un problème réduit). Exemple : fact(n) = n × fact(n-1) avec fact(0) = 1. Sans cas de base, la récursion est infinie et lève une RecursionError. La modularité consiste à découper un programme en modules réutilisables, importés avec import. Les spécifications (docstrings, assertions, tests) garantissent la fiabilité du code. La bibliothèque standard de Python fournit de nombreux modules prêts à l'emploi comme math, random ou os.
Une fonction récursive résout un problème en s'appelant elle-même sur une version plus petite du problème. Deux ingrédients sont indispensables : un cas de base qui stoppe la descente, et un cas récursif qui s'en rapproche à chaque appel.
fact(3) descend jusqu'au cas de base fact(0)=1, puis remonte en multipliant : 1, 2, 6.
- Auto-appel : une fonction récursive s'appelle elle-même avec des paramètres réduits.
- Cas de base : condition d'arrêt indispensable pour stopper la récursion.
- Cas récursif : chaque appel doit se rapprocher du cas de base.
- Pile d'appels : chaque appel empile un contexte ; au retour, on dépile (remontée).
- Limite Python : la profondeur de récursion est plafonnée (environ 1000 appels).
Exemple
def fact(n):\n if n == 0:\n return 1\n return n * fact(n-1). Pour fact(3) : on descend jusqu'à fact(0) = 1, puis on remonte : $1, 1, 2, 6$, donc fact(3) vaut 6.
Piège à éviter
Sans cas de base, ou si le cas récursif ne s'en rapproche pas, la fonction s'appelle à l'infini : Python finit par lever une RecursionError. Le cas de base n'est jamais optionnel.
Beaucoup de calculs s'expriment naturellement de façon récursive : factorielle, puissance, somme d'une liste, suite de Fibonacci. Écrire leur définition récursive aide à comprendre, mais attention : toutes ne sont pas aussi efficaces.
- Factorielle : def fact(n): return 1 if n == 0 else n * fact(n-1).
- Puissance : def puissance(x, n): return 1 if n == 0 else x * puissance(x, n-1).
- Somme d'une liste : def somme(lst): return 0 if lst == [] else lst[0] + somme(lst[1:]).
- Fibonacci : def fib(n): return n if n <= 1 else fib(n-1) + fib(n-2).
- Outil : dessiner l'arbre des appels aide à suivre l'exécution.
Exemple
puissance(2, 5) calcule $2^5$ : il déroule 2 × puissance(2, 4) = 2 × 2 × puissance(2, 3) = ... = 32, en s'arrêtant à puissance(2, 0) = 1.
Piège à éviter
Le Fibonacci récursif naïf recalcule sans cesse les mêmes valeurs : sa complexité est exponentielle $O(2^n)$. Pour de grands n, il devient inutilisable — une version itérative ou mémoïsée est bien plus rapide.
Un gros programme se découpe en modules : des fichiers regroupant des fonctions réutilisables. On les charge avec import. Cette modularité facilite la maintenance, la lecture et le travail en équipe, et donne accès à la riche bibliothèque standard de Python.
- Module : un fichier Python contenant fonctions, variables et classes réutilisables.
- Import global : import math puis math.sqrt(2).
- Import ciblé : from math import sqrt puis sqrt(2) directement.
- Module maison : placer ses fonctions dans utils.py, puis import utils.
- Garde d'exécution : if __name__ == '__main__': évite d'exécuter du code à l'import.
Exemple
from random import randint puis randint(1, 6) simule un lancer de dé. Importer ainsi évite de réécrire un générateur aléatoire, déjà fourni par la bibliothèque standard.
Piège à éviter
import math.sqrt ne fonctionne pas : on écrit soit import math (puis math.sqrt), soit from math import sqrt (puis sqrt). Mélanger les deux syntaxes est une erreur fréquente.
Un code fiable est un code spécifié : on dit ce que la fonction attend en entrée et garantit en sortie, puis on le vérifie. Docstrings, préconditions, assertions et tests unitaires sont les outils qui transforment « ça a l'air de marcher » en « c'est prouvé sur des cas connus ».
- Docstring : documentation entre triple guillemets, juste après def, décrivant la fonction.
- Précondition : ce que les paramètres doivent respecter (ex. n >= 0 pour fact).
- Postcondition : ce que le résultat garantit si la précondition est respectée.
- assert : assert n >= 0 lève une AssertionError si la condition est fausse.
- Tests unitaires : vérifier la fonction sur des cas connus à résultat attendu.
Exemple
assert fact(0) == 1\nassert fact(5) == 120 : ces tests échouent bruyamment (AssertionError) si fact contient un bug, ce qui le signale immédiatement.
Piège à éviter
Une assertion sert à détecter une erreur, pas à gérer une entrée utilisateur : en production, les assert peuvent être désactivés. Pour une vraie validation d'entrée, utilise une condition explicite, pas seulement assert.
Quiz - Récursivité et modularité
10 questions
S'entraîner
Thème complet
Voir tous les chapitres « Algorithmique et programmation » de la Seconde à la Terminale
Ce thème dans une autre classe
Articles utiles
Questions fréquentes
Les points clés à retenir sur Récursivité et modularité, extraits du quiz de révision.
Qu'est-ce que le cas de base d'une fonction récursive ?
Réponse :
La condition d'arrêt qui ne fait pas d'appel récursif
Le cas de base arrête la récursion : sans lui, la fonction s'appellerait indéfiniment.
Que vaut fact(4) avec fact(0) = 1 et fact(n) = n × fact(n-1) ?
Réponse :
24
fact(4) = 4 × 3 × 2 × 1 × 1 = 24.
Que se passe-t-il si une fonction récursive n'a pas de cas de base ?
Réponse :
Elle provoque une RecursionError
Sans cas de base, la fonction s'appelle à l'infini : Python lève une RecursionError (vers 1000 appels).
Quelle est la complexité de la version récursive naïve de Fibonacci ?
Réponse :
$O(2^n)$ (exponentielle)
La version naïve recalcule sans cesse les mêmes valeurs, d'où une complexité exponentielle $O(2^n)$.