La récursivité est une méthode de résolution où une fonction s'appelle elle-même pour traiter une version réduite du même problème. C'est une manière élégante et parfois naturelle de penser certains problèmes… à condition de bien poser les bases.
Comprendre la récursivité : Une fonction récursive se décompose toujours en un cas de base qui arrête la récursion et un appel récursif qui traite une version simplifiée du problème. Sans cas de base bien défini, la fonction s'appellera indéfiniment jusqu'à provoquer un débordement de pile (stack overflow).
1. Le principe
Une fonction récursive se compose de deux parties essentielles :
| Composant | Description | Importance |
|---|---|---|
| Cas de base | Condition qui arrête la récursion | Sans lui, la fonction s'appelle indéfiniment (stack overflow) |
| Appel récursif | La fonction s'appelle avec une donnée plus simple | Doit se rapprocher du cas de base à chaque appel |
Exemple : calcul de la factorielle (n!)
fonction factorielle(n)
SI n == 0 ALORS retourner 1
SINON retourner n * factorielle(n - 1)
Trace d'exécution : factorielle(4)
Pile d'appels en mémoire
2. Avantages et limites
| Récursif | Itératif | |
|---|---|---|
| Lisibilité | ++ | + |
| Performance | - | ++ |
| Utilisation mémoire | -- | ++ |
| Complexité du code | + | - |
| Idéal pour | Arbres, fractales, problèmes naturellement récursifs | Calculs simples, boucles, parcours linéaires |
Comparaison récursif vs itératif
Avantages de la récursivité :
- Code plus lisible pour certains problèmes (ex: arbres)
- Moins de lignes de code
- Solution élégante pour les problèmes divisibles en sous-problèmes identiques
Inconvénients de la récursivité :
- Empilement des appels récursifs en mémoire
- Risque de boucle infinie sans cas de base
- Moins performant que l'itératif dans certains cas
- Limité par la taille maximale de la pile d'appels (stack size)
3. Vers l'itératif
Certains algorithmes peuvent être réécrits en version itérative pour économiser la mémoire. Cela demande d'utiliser des structures comme les piles, vues au chapitre suivant.
Version récursive
fonction factorielle(n)
SI n == 0 ALORS
retourner 1
SINON
retourner n * factorielle(n - 1)
FIN SI
FIN fonction
Version itérative
fonction factorielle(n)
resultat = 1
POUR i DE 1 À n FAIRE
resultat = resultat * i
FIN POUR
retourner resultat
FIN fonction
Temps d'exécution comparé (exemple typique)
| Taille (n) | Récursif | Itératif | Ratio |
|---|---|---|---|
| 10 | 0.02 ms | 0.01 ms | 2× |
| 100 | 0.2 ms | 0.05 ms | 4× |
| 1000 | 2.5 ms | 0.5 ms | 5× |
| 10000 | Stack Overflow | 5 ms | ∞ |
4. Exemples concrets d'utilisation
Fibonacci
fonction fibonacci(n)
SI n <= 1 ALORS
retourner n
SINON
retourner fibonacci(n-1) + fibonacci(n-2)
FIN SI
FIN fonction
Note: version naïve, très inefficace pour de grandes valeurs
Parcours d'arbre
fonction parcourir(noeud)
SI noeud EST NULL ALORS
retourner
FIN SI
parcourir(noeud.gauche)
visiter(noeud)
parcourir(noeud.droite)
FIN fonction
Recherche dichotomique
fonction recherche(tableau, valeur, debut, fin)
SI debut > fin ALORS
retourner -1
FIN SI
milieu = (debut + fin) / 2
SI tableau[milieu] == valeur ALORS
retourner milieu
SINON SI tableau[milieu] > valeur ALORS
retourner recherche(tableau, valeur, debut, milieu-1)
SINON
retourner recherche(tableau, valeur, milieu+1, fin)
FIN SI
FIN fonction
Tour de Hanoï
fonction hanoi(n, debut, fin, intermediaire)
SI n == 1 ALORS
déplacer(debut, fin)
SINON
hanoi(n-1, debut, intermediaire, fin)
déplacer(debut, fin)
hanoi(n-1, intermediaire, fin, debut)
FIN SI
FIN fonction
À retenir
Toujours définir un cas de base pour arrêter la récursion
Chaque appel récursif doit rapprocher du cas de base
Attention à la profondeur de récursion et aux limites de la pile
- La récursivité repose toujours sur un cas de base et un appel récursif
- C'est utile pour les structures comme les arbres, les fractales, les algorithmes de tri ou de recherche
- Elle doit être utilisée avec précaution pour éviter les débordements de pile
- Une fonction récursive peut être transformée en version itérative (souvent plus performante)
- L'optimisation par queue de récursion (tail recursion) peut améliorer les performances