Was ist ein Rekursionsbaum?
Ein Rekursionsbaum ist eine visuelle Darstellung jedes Aufrufs, den eine rekursive Funktion macht. Jeder Knoten zeigt die übergebenen Argumente und den zurückgegebenen Wert. Eltern-Kind-Kanten repräsentieren, welcher Aufruf welchen Unteraufruf erzeugt hat. Durch das Lesen des Baums von oben nach unten kannst du die genaue Ausführungsreihenfolge nachvollziehen und verstehen, wie das Problem in kleinere Teilprobleme zerlegt wird.
Warum Memoization wichtig ist
Viele rekursive Algorithmen besuchen dieselben Teilprobleme mehrfach; Fibonacci ist das klassische Beispiel, bei dem fib(3) mehr als einmal berechnet wird. Memoization speichert die Ergebnisse bereits gelöster Teilprobleme, damit sie bei Wiederholungsaufrufen sofort zurückgegeben werden. Diese Technik wandelt exponentielle Zeitkomplexität in polynomiale oder lineare Komplexität um – das ist der Kerngedanke der dynamischen Programmierung.
Den Aufrufstapel lesen
Der Aufrufstapel ist die Kette aktiver Funktionsaufrufe zu einem beliebigen Zeitpunkt während der Ausführung. In diesem Visualisierer entspricht die Tiefe eines Knotens seiner Position im Stapel. Tiefe Bäume bedeuten mehr Stack-Frames, was in echten Programmen zu Stack-Overflow-Fehlern führen kann. Das Beobachten der Stapeltiefe hilft dir, den Speicherverbrauch zu verstehen und zu erkennen, wann ein iterativer Ansatz sicherer wäre.
Häufige Rekursionsmuster
Lineare Rekursion ruft sich einmal pro Aufruf selbst auf; Beispiele sind Fakultät und Durchlauf von verketteten Listen. Binäre Rekursion macht zwei Aufrufe pro Aufruf; Fibonacci und Mergesort folgen diesem Muster. Baumrekursion verallgemeinert auf drei oder mehr Zweige, wie bei den Türmen von Hanoi. Das Verstehen dieser Muster hilft dir, die Zeitkomplexität vorherzusagen, bevor du Code schreibst.