Simulic
Deutsch

Rekursion – Aufrufstapel und Aufrufbaum

InformatikAlgorithmen und ProblemlösenAlter 17–18

Wird geladen …

Mit meiner Klasse nutzen ✨ Mit KI anpassen Problem melden

Führen Sie rekursive Funktionen Schritt für Schritt aus – Fakultät, Fibonacci, Summe einer Liste, binäre Suche, das Scheiben-Turm-Rätsel und Mergesort – und beobachten Sie, wie der Aufrufstapel wächst und wieder abgebaut wird, während ein Aufrufbaum jeden Aufruf, jeden Basisfall und jeden Rückgabewert festhält. Vergleichen Sie naives rekursives Fibonacci mit Memoisation und mit einer Schleife, entfernen Sie den Basisfall für einen Stapelüberlauf und lesen Sie den Code in Python oder Pseudocode.

Lektion: Rekursion: Basisfall, Aufrufstapel, Teile und herrsche, Memoisation, Rekursion und Iteration

Was sie zeigt

Eine rekursive Funktion löst ein Problem, indem sie sich selbst mit einer kleineren Version desselben Problems aufruft. Jeder Aufruf legt einen neuen Rahmen auf den Aufrufstapel; der Basisfall gibt einen Wert zurück, ohne sich erneut aufzurufen, danach werden die Rahmen wieder abgebaut und die Werte nach oben gereicht. Der Aufrufbaum zeigt alle Aufrufe: Fakultät und Listensumme bilden eine einzige Kette, Fibonacci, Mergesort und der Turm verzweigen sich. Naives Fibonacci wiederholt dieselben Aufrufe, ihre Zahl wächst exponentiell; Memoisation speichert Ergebnisse. Ohne Basisfall läuft der Stapel über.

So funktioniert es

Wählen Sie eine Funktion und stellen Sie n ein (bei der binären Suche das Ziel). Klicken Sie auf Schritt für einen Aufruf oder eine Rückgabe, auf Zurück, um einen Schritt rückgängig zu machen, oder auf Abspielen mit der gewählten Geschwindigkeit. Beobachten Sie Code, Stapel und Baum; tippen Sie auf einen Knoten für Details. Aktivieren Sie Memo bei Fibonacci oder deaktivieren Sie Mit Basisfall.

Einstellbare Parameter

  • Rekursive Funktion Fakultät n!, Fibonacci-Zahlen, Summe einer Liste, Binäre Suche, Scheiben-Turm (Rätsel), Mergesort
  • n (Größe des Problems) 0–8
  • Gesuchter Wert (binäre Suche) 0–100
  • Memoisation (Fibonacci)
  • Basisfall einbeziehen
  • Sprache Python, Pseudocode
  • Geschwindigkeit 0,5–10 Schritte/s

Fragen zum Erkunden

  1. Wie oft wird fib(2) bei der Berechnung von fib(6) ohne Memoisation aufgerufen, und wie oft mit Memoisation?
  2. Wie groß ist die maximale Stapeltiefe für factorial(5), und wie viel Stapel braucht die Schleifenversion?
  3. Warum führt das Entfernen des Basisfalls zu einem Stapelüberlauf und nicht zu einem falschen Ergebnis?

Ähnliche Simulationen