Fachkonzept
Der 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 Berechnen der Fakultät von n beispielsweise wird die Funktion rekursiv mit n-1 aufgerufen. Die Zahl, deren Fakultät berechnet werden soll, wird also immer kleiner, und die Problemlösung "steigt" sozusagen zu den kleineren Zahlen hinab. Wir wollen dabei dem Basisfall näher kommen.
Bei anderen Problemen wie der Berechnung der Fibonacci-Zahlen (Reduktion auf fib(n-1) und fib(n-2)) oder dem Aufsummieren aller Elemente einer Liste (Verkürzung der Liste) wird das Problem ebenfalls schrittweise verkleinert, bis der Basisfall erreicht ist.
Rekursiver Aufstieg
Das ist die Phase, nachdem der Basisfall erreicht wurde. Die Information oder das Ergebnis des Basisfalls (z.B. "Fakultät von 0 ist 1" oder "die 0-te Fibonacci-Zahl ist 0" und "die 1-te Fibonacci-Zahl ist 1") wird zurückgegeben. Bei komplexeren rekursiven Problemen werden die Ergebnisse der kleineren Problem-Instanzen dann verwendet, um das Ergebnis für die nächstgrößere Instanz zu berechnen. Die Ergebnisse "steigen" sozusagen aus der Tiefe wieder auf. Bei der Fakultätsberechnung wird das Ergebnis von fac(n-1) "nach oben" gemeldet. Bei den Fibonacci-Zahlen werden die Ergebnisse von fib(n-1) und fib(n-2) "nach oben" gemeldet.
Bei der Fakultätsfunktion multiplizieren wir also das Ergebnis des rekursiven Aufrufs (z.B. fac(n-1)) mit der aktuellen Zahl (n), um auf die Fakultät der ursprünglichen Zahl zu kommen. Beim Aufsummieren der Elemente einer Liste addieren wir das erste Element der Liste mit dem Ergebnis des rekursiven Aufrufs für die Restliste, um auf die Summe aller Elemente der ursprünglichen Liste zu kommen. Für Fibonacci-Zahlen addieren wir die Ergebnisse der beiden rekursiven Aufrufe, um die Fibonacci-Zahl für n zu erhalten.
Die "Magie der Rekursion"
Diese Überlegungen können uns beim Programmieren rekursiver Funktionen helfen. Wenn wir eine rekursive Funktion schreiben, können wir gedanklich annehmen, dass unsere Funktion das um eins kleinere Problem "wie durch Zauberhand" bereits lösen kann. Deshalb nennen wir das auch die Magie der Rekursion. Dann überlegen wir uns, was wir mit dem Ergebnis des kleineren Problems noch machen müssen, um auf das Endergebnis zu kommen.
Für das Fakultätsbeispiel: Um die Fakultät fac(n) zu berechnen, nehmen wir an, dass unsere Funktion "wie durch Zauberhand" bereits fac(n-1) lösen kann. Wir vertrauen darauf, dass der rekursive Aufruf uns das korrekte Ergebnis für das kleinere Problem liefert. Dann müssen wir dieses Ergebnis nur noch mit n multiplizieren, um fac(n) zu erhalten.
Ähnlich bei den Fibonacci-Zahlen: Um die n-te Fibonacci-Zahl fib(n) zu berechnen, gehen wir davon aus, dass unsere Funktion bereits fib(n-1) und fib(n-2) korrekt berechnen kann. Unsere Aufgabe ist es dann nur noch, diese beiden "magisch" erhaltenen Ergebnisse zu addieren.
Genauso können wir auch bei allen anderen Problemen vorgehen, die wir bereits gelöst haben. Wenn wir wie im vorherigen Kapitel eine Liste umkehren wollen, gehen wir davon aus, dass wir die um eins kürzere Liste bereits umkehren können und müssen uns dann nur noch überlegen, dass wir das übrige Element dann "nur noch" hinten an die Liste anhängen müssen.
Zusammengefasst müssen uns also beim rekursiven Lösen von Problemen die folgenden Schritte überlegen:
- Wie reduziere ich das Problem?
- Was mache ich mit dem Ergebnis des kleineren Problems unter der Annahme, dass die Funktion das kleinere Problem bereits lösen kann?
- Was ist die kleinste Instanz des Problems bzw. was ist der Basisfall (oder die Basisfälle)?
- Was ist die Lösung des Basisfalls?
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 Endeffekt sind das die selben Überlegungen wie die die du bei Aufgabe 3 im vorherigen Kapitel gemacht hast.
