Einordnung

Beim Suchen der Datei "Lösungen_Klassenarbeit_Informatik.pdf" hast du wahrscheinlich eine rekursive Strategie entwickelt, die sich immer wiederholt hat: Ordner öffnen, Inhalt prüfen. Wenn ein Unterordner auftaucht, wendest du genau dieselbe Suchstrategie auf diesen neuen, "kleineren" Suchbereich (den Unterordner) an. Du hast also das Prinzip der Rekursion angewendet, indem du das Problem auf eine kleinere Version seiner selbst zurückgeführt hast.

Das Schema der rekursiven Problemlösung

Die Strategie, ein Problem zu lösen, indem man es auf eine kleinere Version seiner selbst zurückführt, bis man bei einem einfachen, direkt lösbaren Fall ankommt, nennen wir rekursive Problemlösung. Das hast du auch im ersten Kapitel schon gelernt. Jetzt wollen wir diese Strategie nochmal etwas abstrakter darstellen.

Wenn wir ein Problem haben, welches wir nicht direkt lösen können, z.B. "Ist 'Lösungen_Klassenarbeit_Informatik.pdf' irgendwo im riesigen Ordner 'Dokumente'?", können wir das Problem reduzieren (Rekursionsschritt): "Öffne 'Dokumente'. Ah, ein Unterordner 'Bilder'! Jetzt lautet das Problem: Ist die Datei irgendwo im Unterordner 'Bilder'?". Wenn wir ein Problem versuchen direkt zu lösen, sagen wir dazu ad-hoc (quasi "spontan"). Das kleinere Problem gehen wir mit derselben Logik an. Die Lösung dieses kleineren Problems erweitern wir dann zu der Lösung des ursprünlgichen Problems. Im Fall des Dateisuchens, bei dem die Lösung des Problems einfach ein schlichtes "Ja" oder "Nein" ist, ist das noch relativ simpel. Wenn wir an die Probleme aus dem ersten Kapitel denken, wie beispielswiese die Fakultät, dann müssen wir mit dem Ergebnis des rekursiven Aufrufs bzw. des kleineren Problems noch etwas tun, um auf die Lösung des ursprünglichen Problems zu kommen. Das Diagramm im Folgenden soll das alles nochmal visualisieren.

Dieses Zerlegen in immer kleinere, gleichartige bzw. strukturgleiche Probleme geschieht so lange, bis wir auf den Basisfall stoßen – das Problem, das so klein ist, dass wir es direkt, also ad-hoc, lösen können. In unserem Beispiel wäre entweder die Datei im aktuell betrachteten Ordner, oder der aktuell betrachtete Ordner enthält keine weiteren Unterordner und die Datei ist auch nicht unter den direkten Dateien. Diese Lösung wird dann an die nächstgrößere Instanz weitergegeben, die damit dann weiter arbeitet bzw. weiter rechnet.

Im RecursionTutor kannst du dieses Schema auch gut sehen. Hier werden so lange neue Knoten generiert, bis der Basisfall erreicht ist. Dieser Basisfall kann dann ad-hoc gelöst werden und das Ergebnis an die nächstgrößere Instanz weitergegeben werden. Dort kann dann ein neues Ergebnis berechnet und wieder an die nächstgrößere Instanz weitergegeben werden. Schau dir das folgende Diagramm von der Fakultätsfunktion (englisch und kurz "fac") nochmal genauer an versuche die Rekursionsschritte und den Basisfall zu finden.

Das Diagramm des RecursionTutors ist einerseits eine Visualisierung des Programmcodes, spiegelt aber 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 2

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

        >>> reverse([4711]) # Aufgepasst, die Liste hier hat nur ein Element!
        [4711]
        
        >>> reverse(['a', 'b', 'c'])
        ['c', 'b', 'a']
        
        >>> reverse([True, False, False])
        [False, False, True]