Récursivité
Dernière mise à jour
La récursion, c'est une fonction qui s'appelle elle-même sur une version plus petite du même problème, jusqu'à atteindre un cas assez petit pour être résolu directement. Ce cas directement résoluble est le cas de base, et toute fonction récursive en a besoin : fib(n) continue de se diviser en fib(n - 1) et fib(n - 2) jusqu'à atteindre fib(1) ou fib(0), qui se renvoient simplement eux-mêmes. Le visualiseur ci-dessus fait exactement cela : lancez la lecture et regardez les appels se ramifier en arbre, atteindre les cas de base au niveau des feuilles, puis renvoyer leurs valeurs vers le haut en se combinant à chaque niveau.
La deuxième chose que montre l'animation, c'est la pile d'appels : tout appel qui a commencé mais n'a pas encore renvoyé son résultat. La pile grandit à mesure que les appels s'enfoncent, culmine à la profondeur de récursion, puis se vide au fur et à mesure que les résultats remontent ; c'est pourquoi une récursion profonde peut provoquer un débordement de pile alors qu'une boucle itérative ne fait jamais grossir la pile. La même forme d'appels est au cœur du parcours en profondeur, du tri fusion et de la plupart des opérations sur un arbre binaire.
Complexité en temps et en espace
Pour le Fibonacci récursif naïf montré ci-dessus, et ses deux corrections classiques :
| Approche | Temps | Espace | Remarques |
|---|---|---|---|
| Récursion naïve | O(2^n) | O(n) | L'arbre d'appels double à chaque niveau ; l'espace correspond à la pile la plus profonde, pas à l'arbre entier. |
| Avec mémoïsation | O(n) | O(n) | Chaque fib(k) n'est calculé qu'une fois puis mis en cache ; les sous-arbres répétés se réduisent à de simples lectures. |
| Boucle itérative | O(n) | O(1) | Deux variables tournantes remplacent entièrement la pile. |
| Toute récursion, en général | appels × travail par appel | O(max depth) | La pile contient un cadre par appel commencé et pas encore terminé. |
Étape par étape
| Étape | Ce qui se passe |
|---|---|
| 1 | Le premier appel fib(n) est empilé sur la pile d'appels. |
| 2 | Il a besoin de fib(n - 1), cet appel est donc empilé à son tour ; l'appel parent attend. |
| 3 | Les appels continuent de s'imbriquer jusqu'à ce que l'un d'eux teste n <= 1 : le cas de base répond immédiatement, sans appel plus profond. |
| 4 | La valeur du cas de base remonte au parent, qui peut alors lancer son second appel, fib(n - 2). |
| 5 | Quand les deux enfants ont renvoyé leur valeur, le parent les additionne et renvoie à son tour ; son cadre quitte la pile. |
| 6 | Les retours se répètent en remontant l'arbre jusqu'à ce que le cadre du premier appel soit dépilé avec la réponse finale et que la pile soit vide. |
Exemple détaillé
Évaluation de fib(4) dans l'ordre exact des appels, tel que l'animation le déroule :
| Appel | Pile à cet instant | Renvoie |
|---|---|---|
fib(4) | fib(4) | attend ses enfants |
fib(3) | fib(4) > fib(3) | attend ses enfants |
fib(2) | fib(4) > fib(3) > fib(2) | attend ses enfants |
fib(1) | fib(4) > fib(3) > fib(2) > fib(1) | 1 (cas de base) |
fib(0) | fib(4) > fib(3) > fib(2) > fib(0) | 0 (cas de base) |
fib(2) combine | fib(4) > fib(3) > fib(2) | 1 + 0 = 1 |
fib(1) | fib(4) > fib(3) > fib(1) | 1 (cas de base) |
fib(3) combine | fib(4) > fib(3) | 1 + 1 = 2 |
fib(2) à nouveau | fib(4) > fib(2) | 1, recalculé de zéro |
fib(4) combine | fib(4) | 2 + 1 = 3 |
Quand utiliser la récursion
| À utiliser quand | À éviter quand |
|---|---|
| Le problème est auto-similaire : arbres, structures imbriquées, diviser pour régner | Une simple boucle exprime la même chose sans cadres de pile |
La profondeur est bornée et modérée, comme O(log n) dans le tri fusion | La profondeur peut atteindre la taille de l'entrée sur de très grandes entrées, au risque d'un débordement de pile |
| Le retour arrière a besoin de la pile pour se souvenir où reprendre | Les mêmes sous-problèmes reviennent et vous ne les mettez pas en cache |
| La version récursive est nettement plus facile à lire et à vérifier | Vous êtes dans une boucle critique où le coût d'un appel se mesure vraiment |
Code de Recursion
Une implémentation propre et exécutable de Recursion en Python, JavaScript, Java, C++, C. Choisissez un langage, copiez le code ou ouvrez-le préchargé dans le Playground Coddy.
Code de Recursion en Python
Python
1calls = 02
3def fib(n, depth=0):4 global calls5 calls += 16 # Print the call with its depth so the recursion is visible7 print(" " * depth + f"fib({n})")8 if n <= 1:9 return n10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1)11
12
13print("fib(5) =", fib(5))14print("calls made:", calls)Code de Recursion en JavaScript
JavaScript
1let calls = 0;2
3function fib(n, depth = 0) {4 calls += 1;5 // Print the call with its depth so the recursion is visible6 console.log(' '.repeat(depth) + `fib(${n})`);7 if (n <= 1) return n;8 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);9}10
11console.log('fib(5) =', fib(5));12console.log('calls made:', calls);Code de Recursion en Java
Java
1public class Main {2 static int calls = 0;3
4 static int fib(int n, int depth) {5 calls++;6 // Print the call with its depth so the recursion is visible7 System.out.println(" ".repeat(depth) + "fib(" + n + ")");8 if (n <= 1) return n;9 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);10 }11
12 public static void main(String[] args) {13 System.out.println("fib(5) = " + fib(5, 0));14 System.out.println("calls made: " + calls);15 }16}Code de Recursion en C++
C++
1#include <iostream>2#include <string>3
4int calls = 0;5
6int fib(int n, int depth) {7 calls++;8 // Print the call with its depth so the recursion is visible9 std::cout << std::string(depth * 2, ' ') << "fib(" << n << ")\n";10 if (n <= 1) return n;11 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);12}13
14int main() {15 int result = fib(5, 0);16 std::cout << "fib(5) = " << result << "\n";17 std::cout << "calls made: " << calls << "\n";18 return 0;19}Code de Recursion en C
C
1#include <stdio.h>2
3int calls = 0;4
5int fib(int n, int depth) {6 calls++;7 /* Print the call with its depth so the recursion is visible */8 printf("%*sfib(%d)\n", depth * 2, "", n);9 if (n <= 1) return n;10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);11}12
13int main(void) {14 printf("fib(5) = %d\n", fib(5, 0));15 printf("calls made: %d\n", calls);16 return 0;17}FAQ sur la récursion
Qu'est-ce qu'un cas de base en récursion ?
C'est l'entrée assez petite pour être traitée sans nouvel appel récursif. Pour
fib(n), c'est n <= 1, qui renvoie n directement. Sans cas de base atteignable, les appels ne s'arrêtent jamais, la pile grandit sans fin et le programme plante avec un débordement de pile.Qu'est-ce que la pile d'appels et pourquoi est-elle importante ?
L'environnement d'exécution conserve un cadre par appel commencé mais pas encore terminé, contenant ses arguments et ses variables locales. La profondeur de récursion est égale à la hauteur de la pile : une récursion qui descend de
n niveaux consomme donc O(n) de mémoire, même si chaque appel ne fait presque rien. La rangée de pastilles sous l'animation montre précisément cette pile qui grandit puis se vide.Pourquoi le Fibonacci récursif prend-il un temps exponentiel ?
Parce que les mêmes sous-problèmes sont recalculés encore et encore : dans l'exemple détaillé ci-dessus,
fib(2) est évalué deux fois à l'intérieur de fib(4), et cette duplication double à peu près à chaque niveau, ce qui donne O(2^n) appels. Mettre chaque résultat en cache dès son premier calcul, ce qu'on appelle la mémoïsation, ramène l'arbre à O(n).La récursion est-elle meilleure que l'itération ?
Aucune des deux n'est meilleure en toutes circonstances. Toute récursion peut se réécrire en boucle avec une pile explicite, et toute boucle en récursion. La récursion gagne en lisibilité sur les problèmes auto-similaires, comme le parcours d'arbre ou le parcours en profondeur ; l'itération gagne en mémoire et en coût d'appel pour les parcours linéaires.
Qu'est-ce qui provoque un débordement de pile dans une fonction récursive ?
Soit un cas de base absent ou inatteignable, si bien que les appels ne s'arrêtent jamais, soit une récursion correcte dont la profondeur dépasse simplement la limite de pile de l'environnement d'exécution, comme un appel récursif par élément sur une entrée de plusieurs millions. Les remèdes sont de garantir le cas de base, de borner la profondeur ou de convertir en itération.
Quels algorithmes sont naturellement récursifs ?
Les tris de type diviser pour régner comme le tri fusion et le tri rapide, les parcours d'un arbre binaire et de graphes, la recherche dichotomique, les casse-tête à retour arrière comme les N reines, et tout ce qui se définit sur une structure imbriquée, comme JSON ou un système de fichiers.
Ressources associées
Plus de visualisations
