%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %%
> [!nav]
> ↩ [[Code et Développement/Programmation/Récursivité/Récursivité|Accueil · Récursivité]]
%% nav-fin %%
# 🧠 La récursivité
> *Objectif : Comprendre et implémenter une fonction récursive simple pour résoudre un problème algorithmique.*
## 🔍 Qu’est-ce que la récursivité ?
Une **fonction récursive** est une fonction qui **s’appelle elle-même** dans son propre corps.
Cette technique permet de résoudre des problèmes complexes en les **divisant en sous-problèmes plus simples**, similaires à l’original.
Pour qu’une fonction récursive fonctionne correctement, deux éléments sont essentiels :
1. Une **condition d’arrêt** claire, qui met fin à la récursion.
2. Un **appel récursif** qui rapproche l’argument de la condition d’arrêt à chaque appel.
## 📌 Exemple 1 — La factorielle d’un nombre
La factorielle d’un entier naturel `n`, notée `n!`, est le produit de tous les entiers de 1 à `n`.
**Définition mathématique :**
- `0! = 1` (cas de base)
- `n! = n × (n - 1)!` (cas général)
**Version récursive, pas à pas :** choisissez `n`, puis suivez chaque appel dans le code, la pile d'appels et le développement du calcul.
```sq-recursion
n: 4
```
## ⚠️ Exemple d’erreur sans condition d’arrêt
```python
def factorielle(x):
return x * factorielle(x - 1)
print(factorielle(6))
```
➡️ Cette fonction ne s’arrête jamais car elle **n’a pas de condition d’arrêt**.
## ⚠️ Autre piège — Une condition d’arrêt insuffisante
Même avec une condition d’arrêt présente, il faut s’assurer que les **valeurs anormales** soient bien gérées.
Voici un exemple où l’appel récursif avec une valeur négative entraîne une boucle infinie :
```python
def factorielle(x):
if x == 0:
return 1
else:
return x * factorielle(x - 1)
print(factorielle(-3))
```
➡️ Dans ce cas, `x` devient de plus en plus négatif et **n’atteindra jamais 0**.
Il faut donc gérer explicitement les entrées négatives dans notre fonction.
**À manipuler :** suivez les appels de `factorielle(-3)`. La pile grandit jusqu’à l’erreur `RecursionError`, que Python lève au bout d’environ 1000 appels.
```sq-recursion
n: -3
```
## ✅ Ajout d’une condition d’arrêt correcte
```python
def factorielle(x):
if x < 0:
return None
elif x == 0:
return 1
else:
return x * factorielle(x - 1)
print(factorielle(-3)) # Affiche None
print(factorielle(6)) # Affiche 720
```
> 🎯 Toujours vérifier que votre fonction **rejoint la condition d’arrêt** en un nombre fini d’étapes.
## 🔁 Équivalent itératif
Toute fonction récursive peut être réécrite avec une boucle :
```python
def factorielle(x):
f = 1
for i in range(2, x + 1):
f *= i
return f
print(factorielle(6)) # Affiche 720
```
## 📌 Exemple 2 — La suite de Fibonacci
La suite de Fibonacci est définie par :
- `F(0) = 0`
- `F(1) = 1`
- `F(n) = F(n-1) + F(n-2)` pour `n ≥ 2`
### 🔄 Version récursive
```python
def fibonacci(x):
if x <= 1:
return x
else:
return fibonacci(x - 1) + fibonacci(x - 2)
for i in range(12):
print(fibonacci(i), end=" ") # Affiche les 12 premiers termes de la suite de Fibonacci
```
**Arbre d'appels :** chaque appel de `fibonacci` en déclenche deux autres. Suivez les appels et comptez les calculs répétés.
```sq-fibonacci
n: 5
```
### 🔁 Version itérative
```python
def fibonacci(x):
a, b = 0, 1
for i in range(x):
a, b = b, a + b
return a
for i in range(12):
print(fibonacci(i), end=" ") # Même résultat
```
La boucle utilise une affectation simultanée : `a, b = b, a + b` calcule d’abord `b` et `a + b` avec les anciennes valeurs, puis les range dans `a` et `b`.
**À manipuler :** suivez les valeurs de `a` et `b` pour `x = 6`.
```sq-trace
x = 6
a, b = 0, 1
for i in range(x):
a, b = b, a + b
print(a)
---
1 | x = 6 |
2 | a = 0, b = 1 |
3 | i = 0 |
4 | a = 1, b = 1 |
3 | i = 1 |
4 | a = 1, b = 2 |
3 | i = 2 |
4 | a = 2, b = 3 |
3 | i = 3 |
4 | a = 3, b = 5 |
3 | i = 4 |
4 | a = 5, b = 8 |
3 | i = 5 |
4 | a = 8, b = 13 |
5 | | 8
```
## 🧠 À retenir
- Une fonction récursive s’appelle elle-même.
- Elle doit toujours comporter une **condition d’arrêt**.
- Elle donne une écriture courte de certaines fonctions (`factorielle`, `fibonacci`, parcours d’arbre).
- Chaque appel occupe une place dans la pile d’appels : Python lève `RecursionError` au-delà d’environ 1000 appels imbriqués.
%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %%
> [!nav]
> ↩ [[Code et Développement/Programmation/Récursivité/Récursivité|Accueil · Récursivité]]
%% nav-fin %%
---
🗓️ Historique
Dernière mise à jour : `8 novembre 2026`
Rédigé par : [[Julien DUQUENNOY]]