Einordnung
Betrachten wir die Struktur der bereits bekannten rekursiven Funktionen genauer. Was ist charakteristisch für ihren Aufbau und Ablauf?
Wir haben bereits gesehen, dass Rekursion bedeutet, ein Problem so oft auf eine kleinere Version des selben Problems zurückzuführen, bis wir einen Basisfall erreichen. Danach werden dann die Teilergebnis zum Gesamtergebnis kombiniert. Dieser Prozess lässt sich in zwei Phasen unterteilen: den rekursiven Abstieg und den rekursiven Aufstieg.
Rekursiver Abstieg: Das ist die Phase, in der wir uns dem Basisfall nähern. Bei jedem rekursiven Aufruf wird das Problem kleiner gemacht (z. B. wird
n in factorial(n) zu n - 1, oder eine Liste wird kürzer). Im Recursion Tutor siehst du das daran, dass neue Funktionsaufrufe (neue Knoten im Diagramm) mit veränderten Argumenten erzeugt werden. Die Funktion "steigt" sozusagen in die Tiefe der Rekursion hinab.
Rekursiver Aufstieg: Das ist die Phase, nachdem der Basisfall erreicht wurde. Die Ergebnisse der kleineren Problem-Instanzen werden zurückgegeben und dazu verwendet, das Ergebnis für die nächstgrößere Instanz zu berechnen. Die Ergebnisse "steigen" sozusagen aus der Tiefe der Rekursion wieder auf und werden Schritt für Schritt zum Endergebnis kombiniert. Im RecursionTutor siehst du das, wenn die Fragezeichen in den Knoten (die für das Ergebnis eines noch nicht abgeschlossenen rekursiven Aufrufs stehen) durch tatsächliche Werte ersetzt werden und sich ihre Hintergrundfarbe von gelb auf blau ändert.
Zusammengefasst visualisiert das Tool also:
- Jeden einzelnen Funktionsaufruf – vom initialen Aufruf bis zu jedem rekursiven Aufruf – als separaten Knoten in einem Diagramm.
- Die Argumente, die bei jedem Aufruf an die Funktion übergeben werden.
- Den Weg der Funktion durch ihren Code, also den rekursiven Abstieg sowie den Wechsel zum rekursiven Aufstieg beim Basisfall.
