Fachkonzept
Dieser Prozess der rekursiven Problemlösung, den du in den letzten Zwei Kapiteln vertieft hast, lässt sich oft in zwei Phasen unterteilen:
Rekursiver Abstieg
Das ist die Phase, in der wir uns dem Basisfall nähern. Bei jedem rekursiven Schritt wird das Problem kleiner gemacht. Beim Dateisuchbeispiel ist das das wiederholte "Betreten" eines Unterordners und das Fokussieren der Suche auf diesen kleineren Bereich. Die Problemlösung "steigt" sozusagen in die Tiefe der Ordnerstruktur hinab.
Rekursiver Aufstieg
Das ist die Phase, nachdem der Basisfall erreicht wurde. Die Information oder das Ergebnis des Basisfalls (z.B. "Datei gefunden an Pfad X" oder "Datei in diesem Ordner/Unterordner nicht gefunden") wird zurückgegeben. Bei komplexeren rekursiven Problemen werden die Ergebnisse der kleineren Problem-Instanzen dann oft verwendet, um das Ergebnis für die nächstgrößere Instanz zu berechnen. Die Ergebnisse "steigen" sozusagen aus der Tiefe wieder auf. Wenn die Datei gefunden wurde, wird diese Information "nach oben" durch die Ordnerhierarchie gemeldet.
Die "Magie der Rekursion"
Dieses Schema kann uns beim Programmieren rekursiver Funktionen helfen. Wenn wir eine rekursive Funktion schreiben, nehmen wir gedanklich an, dass unsere Funktion das um eins kleinere Problem bereits lösen kann. Das nennen das auch die "Magie der Rekursion".
Für das Dateisuchbeispiel: Um herauszufinden, ob die Datei in einem aktuellen Ordner (oder dessen Unterordnern) ist, prüfen wir erst die Dateien direkt im aktuellen Ordner. Finden wir sie nicht, und es gibt Unterordner, sagen wir uns für jeden Unterordner: "Ich vertraue darauf, dass meine Suchmethode schon weiß, wie sie diese Datei in diesem Unterordner findet und mir das Ergebnis liefert."
Wir müssen uns also überlegen:
- Wie reduziere ich das Problem (z.B. zum nächsten Unterordner übergehen)?
- Was mache ich mit dem Ergebnis des kleineren Problems (wenn die Datei im Unterordner gefunden wurde, dann ist sie insgesamt gefunden)?
- Was ist der Basisfall (oder die Basisfälle), bei dem ich direkt eine Lösung habe (z.B. Datei im aktuellen Ordner gefunden; aktueller Ordner hat keine Unterordner und Datei nicht direkt darin)?
Um die zweite Überlegung zu treffen, hilft es oft, sich zu überlegen, was die Lösung des ursprünglichen Problems ist - sofern das möglich ist. Im Folgenden schauen wir uns die obigen Überlegungen nochmal an konkreten Beispielen an.
Aufgabe 2
Im folgenden Block ist die Funktion reverse(liste) geladen, die versucht, eine Liste rekursiv umzukehren. Schau dir zunächst ein paar Beispielausgaben an.
reverse([1, 2, 3, 4, 5])
> [5, 4, 3, 2, 1]
reverse([4711])
> [4711]
reverse(['a', 'b', 'c'])
> ['c', 'b', 'a']
reverse([True, False, True])
> [True, False, True]
Beantworte nun die folgenden Fragen:
- Was ist die kleinste Instanz des Problems und was sollte die Funktion in diesem Fall zurückgeben?
- Wie kann man das Problem im rekursiven Schritt verkleinern?
- Wie wird das Ergebnis des rekursiven Aufrufs verwendet, um das Endergebnis zu erzeugen?
- Die Aufrufe oben sind mit verschiedenen Arten von Listen gemacht. Was fällt dir auf?
Aufgabe 3
Versuche nun, die Funktion reverse(liste) zu implementieren. Denk dabei an deine Antworten von der letzten Aufgabe. Schreibe die Funktion in das folgende Code-Fenster und teste sie mit verschiedenen Beispielen.
def reverse(liste):
# Dein Code hier
...
print(reverse([4,7,1,1]))
print(reverse(["Hallo", "Welt"]))
print(reverse([True, False, True]))
print(reverse([10]))
