Fachkonzept

In den vorherigen Lernschritten haben wir die Idee der Rekursion erkundet und verschiedene Beispiele kennengelernt. In diesem Fachkonzept fassen wir die wichtigsten Begriffe nochmal zusammen.

Rekursion

Der Basisfall

Der Basisfall ist die kleinste Instanz oder einfachste Instanz des Problems, deren Lösung direkt bekannt ist und keinen weiteren rekursiven Aufruf erfordert. Gleichzeitig ist der Basisfall verantwortlich dafür, dass die Rekursion endet. Ohne einen Basisfall würde die Rekursion unendlich weiterlaufen.

Wir haben auch gesehen, dass eine Funktion mehr als einen Basisfall (wie bei Fibonacci mit fib(0) und fib(1)) haben kann.

Der Rekursionsschritt

Der Rekursionsschritt ist der Teil der Funktion, der das Problem in ein oder mehrere (wie bei Fibonacci mit fib(n-1) + fib(n-2)) kleinere Teilprobleme zerlegt und die Funktion rekursiv mit diesen kleineren Problemen aufruft. Das Ergebnis des rekursiven Aufrufs wird dann verwendet, um die Lösung für das ursprüngliche Problem zu konstruieren. Wichtig ist, dass jeder Rekursionsschritt das Problem dem Basisfall näherbringt.

Wie man dem Basisfall näher kommt, hängt immer von dem jeweiligen Problem ab. Der Type des Problem kann uns aber einen Hinweis bzw. eine Inuition dafür geben, wie das passieren könnte. Bei natürlich Zahlen müssen wir die Zahl in der Regel verkleinern. Entweder, indem wir von ihr etwas abziehen, oder indem wir sie durch eine andere Zahl teilen. Bei Listen müssen wir häufig die Liste um ein Element verkürzen, genauso müssen wir bei Strings oft den String um einen Buchstaben verkürzen. Es gibt natürlich noch viele andere Datentypen, die ebenfalls alle ihre eigene Weise haben, wie sie verkleinert werden können.

Im Diagramm vom RecursionTutor sehen wir, wie das Argument mit jedem rekursiven Aufruf kleiner wird, bis der Basisfall erreicht wird. Der Knoten des Baisfalls hat dann keinen Pfeil mehr nach rechts, weil das Problem nicht mehr weiter verkleinert werden kann. Stattdessen wird das Problem direkt gelöst und die Lösung an die nächstgrößere Instanz weitergegeben, die dann mit der Lösung des kleineren Problems ihre eigene Lösung berechnen kann. Das geht so lange weiter, bis die Lösung des ursprünglichen Problems gelöst werden kann.

Rekursive Funktionen

Rekursive Funktionen sind Funktionen, die sich selbst aufrufen. Das bedeutet, dass innerhalb der Funktion ein Aufruf der Funktion selbst stattfindet. In Python müssen wir die Funktion dafür nicht anders definieren, als wir es für andere Funktionen schon kennengelernt haben.