Simulic
Français

Récursivité – pile d'appels et arbre des appels

InformatiqueAlgorithmique et résolution de problèmes17–18 ans

Chargement…

Utiliser avec ma classe ✨ Personnaliser avec l'IA Signaler un problème

Exécutez pas à pas des fonctions récursives – factorielle, Fibonacci, somme d'une liste, recherche dichotomique, le casse-tête de la tour de disques et le tri fusion – et regardez la pile d'appels grandir puis se vider pendant qu'un arbre enregistre chaque appel, chaque cas de base et chaque valeur renvoyée. Comparez Fibonacci récursif naïf avec la mémoïsation et avec une boucle, supprimez le cas de base pour provoquer un débordement de pile, et lisez le code en Python ou en pseudo-code.

Leçon : Récursivité : cas de base, pile d'appels, diviser pour régner, mémoïsation, récursif ou itératif

Ce qu’elle montre

Une fonction récursive résout un problème en s'appelant elle-même sur une version plus petite du même problème. Chaque appel empile un nouveau cadre sur la pile d'appels ; le cas de base renvoie une valeur sans nouvel appel, puis les cadres sont dépilés tandis que les valeurs remontent. L'arbre des appels montre tous les appels : factorielle et somme d'une liste forment une seule chaîne, alors que Fibonacci, le tri fusion et la tour se ramifient. Fibonacci naïf répète les mêmes appels, dont le nombre croît exponentiellement ; la mémoïsation garde les résultats. Sans cas de base, la pile déborde.

Mode d’emploi

Choisissez une Fonction et réglez n (ou la Cible pour la recherche dichotomique). Cliquez sur Pas pour faire un appel ou un retour à la fois, sur Retour pour annuler un pas, ou sur Exécuter pour dérouler à la Vitesse choisie. Observez le code, la pile et l'arbre ; touchez un nœud pour le détail. Cochez Mémo pour Fibonacci ou décochez Avec cas de base pour voir un débordement de pile.

Paramètres modifiables

  • Fonction récursive Factorielle n!, Nombres de Fibonacci, Somme d'une liste, Recherche dichotomique, Tour de disques (casse-tête), Tri fusion
  • n (taille du problème) 0–8
  • Valeur cherchée (recherche dichotomique) 0–100
  • Mémoïsation (Fibonacci)
  • Inclure le cas de base
  • Langage Python, Pseudo-code
  • Vitesse 0,5–10 pas/s

Questions à explorer

  1. Combien de fois fib(2) est-elle appelée pour calculer fib(6) sans mémoïsation, et combien avec ?
  2. Quelle est la profondeur maximale de la pile pour factorial(5), et de combien de pile la version avec boucle a-t-elle besoin ?
  3. Pourquoi supprimer le cas de base provoque-t-il un débordement de pile plutôt qu'une réponse fausse ?

Simulations associées