Einordnung Recursion Tutor

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. Solange die Knoten noch gelb sind, ist der rekursive Abstieg noch nicht abgeschlossen.

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.

Das Diagramm des RecursionTutors nicht aber nicht einfach nur eine Visualisierung des Programmcodes, sondern spiegelt auch die grundlegende Strategie zur Lösung rekursiver Probleme wider. Du siehst direkt, wie das ursprüngliche Problem (der erste Knoten) schrittweise in kleinere, einfachere Teilprobleme zerlegt wird (rekursiver Abstieg und neue Knoten). Jeder Knoten repräsentiert eine Instanz des Problems. Der Basisfall, also die einfachste Problem-Instanz, die direkt gelöst werden kann, wird ebenso deutlich wie der anschließende rekursive Aufstieg, bei dem die Lösungen der Teilprobleme kombiniert werden, um die Gesamtlösung zu bilden. Das Diagramm ist somit eine Landkarte für den rekursiven Denkprozesses. Wenn du diese Dualität verinnerlichst, kann dir die Vorstellung, wie das Diagramm zu einem Problem aussehen würde, dabei helfen, rekursive Programme zu lösen.

Genau das wollen wir in der folgenden Aufgabe nochmal praktisch anwenden.

Aufgabe 3

        >>> reverse([1, 2, 3, 4, 5])
        [5, 4, 3, 2, 1]

        >>> reverse([4711])
        [4711]
        
        >>> reverse(['a', 'b', 'c'])
        ['c', 'b', 'a']
        
        >>> reverse([True, False, False])
        [False, False, True]
    

Als nächstes wollen wir uns nochmal an die Funktion erinnern, die die n+1-te Fibonacci-Zahl bestimmt hat. Zur Erinnerung siehst du die Funktion nochmal unten.

Aufgabe 4