Récursivité
NSI Terminale
Définition
La récursivité est une technique de programmation où une fonction s'appelle elle-même pour résoudre un problème en le ramenant à un sous-problème plus petit. Toute fonction récursive doit comporter au moins un cas de base (qui arrête les appels) et un cas récursif (qui rapproche du cas de base). Sans cas de base correct, les appels s'enchaînent indéfiniment et provoquent un débordement de pile (*stack overflow*). Elle traduit naturellement les définitions mathématiques par récurrence.
Formule
$$n! = \begin{cases} 1 & \text{si } n = 0 \\ n \times (n-1)! & \text{si } n > 0 \end{cases}$$
Exemple corrigé
Énoncé
Écrire une fonction récursive `factorielle(n)` calculant $n!$, puis dérouler les appels pour `factorielle(4)`.
Solution
On traduit directement la définition par récurrence : le cas de base est $0! = 1$, le cas récursif est $n! = n \times (n-1)!$.
```python
def factorielle(n):
if n == 0: # cas de base
return 1
return n * factorielle(n - 1) # cas récursif
print(factorielle(4)) # 24
```
Déroulé des appels :
- `factorielle(4) = 4 * factorielle(3)`
- `factorielle(3) = 3 * factorielle(2)`
- `factorielle(2) = 2 * factorielle(1)`
- `factorielle(1) = 1 * factorielle(0)`
- `factorielle(0) = 1` (cas de base)
On remonte ensuite la pile d'appels :
$$1 \times 1 = 1,\ 2 \times 1 = 2,\ 3 \times 2 = 6,\ 4 \times 6 = 24$$
$$\boxed{4! = 24}$$
Erreurs classiques
- Oublier le cas de base, ce qui provoque une récursion infinie et l'erreur `RecursionError` en Python.
- Écrire un cas récursif qui ne se rapproche pas du cas de base (par exemple appeler `factorielle(n)` au lieu de `factorielle(n-1)`).
Pour aller plus loin : le chapitre « Langages et programmation » (cours et exercices corrigés).