My IT Utilities

Rekursion visualisiert

Schritt für Schritt sehen, wie eine rekursive C++-Funktion sich selbst aufruft: der Aufrufstapel der Fakultät und der Aufrufbaum von Fibonacci.

Alles wird in diesem Browser simuliert; nichts wird an einen Server gesendet.

factorial(4) wird aufgerufen

Aufrufe: 1 · factorial(4) = 24

factorial(4) wird aufgerufen

Aufrufstapel

factorial(4)?
  • Läuft
  • Wartet
  • Aufgelöst

Schritt 1 / 16

Code

#include <iostream>
using namespace std;
long factorial(int n) { // Berechnet n! rekursiv
if (n == 0) return 1; // Basisfall: 0! ist 1 und es folgen keine weiteren Aufrufe
long r = n * factorial(n - 1); // Rekursiver Fall: mit n - 1 aufrufen und multiplizieren
return r; // Gibt das Ergebnis an den Aufrufer zurück
}
int main() {
int n = 4; // Das ist der Wert des Schiebereglers
long resultado = factorial(n); // Erster Aufruf, aus main
cout << resultado << endl; // Endergebnis
return 0;
}

Dieses Tool erklärt Rekursion anschaulich an zwei klassischen C++-Beispielen. Bei der Fakultät sehen Sie den Aufrufstapel: Jeder Aufruf von factorial(n) wird als Frame abgelegt, bis der Basisfall erreicht ist, und dann lösen sich die Frames nacheinander auf und geben ihren Wert an den Aufrufer zurück. Bei Fibonacci sehen Sie den Aufrufbaum: Jedes fib(n) verzweigt sich in fib(n-1) und fib(n-2), und wiederholte Aufrufe werden hervorgehoben, um zu zeigen, warum diese rekursive Version so viel doppelte Arbeit leistet. Sie wählen n per Schieberegler, spielen die Animation schrittweise ab und verfolgen die jeweils ausgeführte Codezeile. Alles wird in Ihrem Browser simuliert.

So funktioniert es

  1. Wählen Sie je nach Beispiel den Tab Fakultät oder Fibonacci.
  2. Stellen Sie n mit dem Schieberegler ein. Die Animation springt zum ersten Schritt zurück.
  3. Drücken Sie Abspielen oder bewegen Sie sich mit den Schaltflächen für vorigen und nächsten Schritt und ändern Sie bei Bedarf die Geschwindigkeit.
  4. Beobachten Sie Aufrufstapel oder Aufrufbaum, den Aufrufzähler und die hervorgehobene Zeile des C++-Codes.

Häufig gestellte Fragen

Was ist Rekursion?
Eine Technik, bei der eine Funktion sich selbst mit einem kleineren Problem aufruft, bis sie einen direkt lösbaren Fall erreicht, und dann die Ergebnisse kombiniert.
Was ist der Basisfall?
Die Bedingung, die die Aufrufe stoppt: Bei der Fakultät liefert n gleich 0 den Wert 1, bei Fibonacci liefert n kleiner als 2 den Wert n. Ohne Basisfall endet die Rekursion nie.
Was ist der Aufrufstapel?
Die Struktur, in der das Programm jeden laufenden Aufruf hält. Jeder Aufruf wird beim Start abgelegt und beim Rückgabewert entfernt, in LIFO-Reihenfolge.
Warum wiederholt das rekursive Fibonacci Arbeit?
Weil fib(n) fib(n-1) und fib(n-2) aufruft und diese Aufrufe dieselben Werte mehrfach neu berechnen. Deshalb wächst der Baum so schnell, und wiederholte Aufrufe werden hervorgehoben.

Verwandte Tools