Qu'est-ce qu'un arbre de récursion ?
Un arbre de récursion est une représentation visuelle de chaque appel effectué par une fonction récursive. Chaque nœud affiche les arguments reçus et la valeur retournée. Les arêtes parent-enfant représentent quel appel a engendré quel sous-appel. En lisant l'arbre de haut en bas, vous pouvez retracer l'ordre d'exécution exact et comprendre comment le problème se décompose en sous-problèmes plus petits.
Pourquoi la mémoïsation est importante
Beaucoup d'algorithmes récursifs revisitent les mêmes sous-problèmes plusieurs fois ; Fibonacci est l'exemple classique où fib(3) est calculé plus d'une fois. La mémoïsation stocke les résultats des sous-problèmes déjà résolus afin qu'ils soient retournés instantanément lors d'appels répétés. Cette technique transforme une complexité temporelle exponentielle en complexité polynomiale ou linéaire, ce qui est l'idée centrale de la programmation dynamique.
Lire la pile d'appels
La pile d'appels est la chaîne des appels de fonction actifs à tout moment pendant l'exécution. Dans ce visualiseur, la profondeur d'un nœud correspond à sa position dans la pile. Des arbres profonds signifient plus de cadres de pile, ce qui peut entraîner des erreurs de débordement de pile dans de vrais programmes. Observer la profondeur de la pile vous aide à comprendre l'utilisation de la mémoire et à identifier quand une approche itérative serait plus sûre.
Patterns de récursion courants
La récursion linéaire s'appelle elle-même une fois par invocation ; les exemples incluent la factorielle et le parcours de liste chaînée. La récursion binaire fait deux appels par invocation ; Fibonacci et le tri fusion suivent ce schéma. La récursion arborescente se généralise à trois branches ou plus, comme dans les Tours de Hanoï. Comprendre ces patterns vous aide à prédire la complexité temporelle avant même d'écrire le code.