# 🧠 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 itération.
## 📌 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 :**
```python
def factorielle(x):
if x == 0:
return 1
else:
return x * factorielle(x - 1)
print(factorielle(6)) # Affiche 720
```
### 🔁 Explication visuelle
![[Récursivité.svg]]
L'appel `factorielle(6)` suit ce schéma :
```
factorielle(6)
=> 6 * factorielle(5)
=> 6 * 5 * factorielle(4)
=> 6 * 5 * 4 * ...
=> ... * 1 * factorielle(0)
=> ... * 1 * 1
=> 720
```
> 💡 Le **cas de base** (`x == 0`) est indispensable pour éviter une boucle infinie.
## ⚠️ 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 None
elif 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.
## ✅ 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 récursivité peut être remplacée par une boucle (parfois moins élégante) :
```python
def factorielle(x):
if x == 0:
return 1
else:
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
```
### 🔁 Version itérative (moins évidente)
```python
def fibonacci(x):
if x <= 1:
return x
else:
a, b = 0, 1
for i in range(2, x + 1):
a, b = b, a + b
return b
for i in range(12):
print(fibonacci(i), end=" ") # Même résultat
```
## 🧠 À retenir
- Une fonction récursive s'appelle elle-même.
- Elle doit toujours comporter une **condition d’arrêt**.
- Elle permet une **écriture élégante** de certaines fonctions (comme `factorielle`, `fibonacci`, parcours d’arbre, etc.).
## 🗓️ Historique
> **Dernière mise à jour :** `19 juillet 2025`
> **Rédigé par :** [[Julien DUQUENNOY]]