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.
- **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
Thème complet
Voir tous les chapitres « Algorithmique et programmation » de la Seconde à la Terminale
Ce thème dans une autre classe
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)$.