Rekursion

Idee der Rekursion

Ein Programm besteht aus Anweisungen, die man in Funktionen zusammenfassen kann. Funktionen rufen andere Funktionen auf, um ihre Arbeit zu verrichten. All das haben wir bisher bereits gesehen und angewendet.

Interessante Möglichkeiten ergeben sich, wenn man Funktionen sich selbst aufrufen lässt. Natürlich muss man etwas Gehirnschmalz in die Frage stecken, wie das genau erfolgen sollte, weil man sonst einfach eine Endlosschleife baut, die zu einem Programmabsturz führt:

def f():
    f()

f() # Fehler!
# RecursionError: maximum recursion depth exceeded

Wieso kommt es zu einem Absturz und nicht nur zu einer Endlosschleife? Der Python-Interpreter muss für jeden Funktionsaufruf Speicher auf dem sogenannten Stack reservieren. Wenn eine Funktion sich unkontrolliert selbst aufruft, wird dieser Stack-Speicher schnell erschöpft und das Programm stürzt ab.

Es gibt aber Fälle, in denen es die Programmierung vereinfacht, wenn Funktionen sich selbst aufrufen und um diese geht es, wenn man Rekursion einsetzt.

Rekursion (recursion) Algorithmus, bei dem sich eine Methode selbst aufruft

• Erlaubt elegante Lösung vieler Probleme, die sich mit Schleifen (iterativ) nur kompliziert lösen lassen
• Kann immer auch in einen iterativen Algorithmus umgewandelt werden

Rekursion haftet nichts Magisches an, da man jeden rekursiven Algorithmus auch in eine iterativen umwandeln kann und umgekehrt. Deswegen setzt man Rekursion dann ein, wenn es die Problemlösung eleganter, besser verständlich oder schneller macht.

Ein klassisches Beispiel für einen Algorithmus, den man gut rekursiv formulieren kann, ist die Berechnung der Fakultät.

def fak(n):
    return n * fak(n - 1) if n > 1 else 1

def fak(n):
    ergebnis = 1

    for i in range(2, n + 1):
        ergebnis *= i;

    return ergebnis

Man sieht hier, dass die rekursive Variante deutlich einfacher aussieht und leichter zu verstehen ist. Schneller ist sie nicht, weil ein Funktionsaufruf immer etwas zusätzliche Zeit kostet.

Aufbau rekursiver Funktionen

Damit rekursive Funktionen nicht in einer Endlosschleife enden, haben sie immer zwei Teile.

Rekursive Funktionen bestehen aus zwei Teilen

• Rekursionsanfang: Einfacher Fall, der am Ende der Rekursion erreicht wird (n = 1: 1)
• Rekursionsschritt: Bringt einen näher an den Rekursionsanfang und ruft die Funktion selbst n > 1: f(n-1) + f(n-2)

What? Der Rekursionsanfang wird am Ende der Rekursion erreicht, das ist doch total unlogisch. Nein ist es nicht, weil rekursive Funktionen das Pferd von hinten aufzäumen: Sie werden mit einem Wert aufgerufen, verarbeiten diesen und bewegen sich dann einen Schritt näher auf den Rekursionsanfang hin, bevor sie sich selbst aufrufen. Damit wird der Rekursionsanfang am Ende der Rekursion erreicht. Trotzdem ist er, wenn man die rekursive Funktion mathematisch formuliert, der Anfang der Rekursion.

Schauen wir uns das Ganze bei einer bekannten Formel an: der Berechnung einer Fibonacci-Zahl. Vielleicht kennen Sie diese Zahlen noch aus der Schule; es sind die mit den Kaninchen.

Mathematisch ist die Fibonacci-Zahl wie folgt definiert:

In der Formel sehen wir schon die Elemente der Rekursion:

• Rekursionsanfang: wenn \( n < 3 \) gilt, dann ist das Ergebnis 1
• Rekursionsschritt: wenn \( n > 2 \) gilt, dann \( f(n-1) + f(n-2) \)

Diese Formel kann man sehr einfach in einer rekursiven Funktion darstellen:

def fib(n):
    """ Rekursive Berechnung der Fibonacci-Zahl zu n. """
    return fib(n - 1) + fib(n - 2) if n > 2 else 1

Im Beispiel wird ein ternäres if verwendet, um die Funktion möglichst kompakt darzustellen. Man könnte auch schreiben:

def fib(n):
    """ Rekursive Berechnung der Fibonacci-Zahl zu n. """
    if n <= 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

Die Fibonacci-Funktion ist ein klassisches Beispiel für eine Funktion, die man ohne Rekursion nur sehr umständlich formulieren kann. Der Grund liegt darin, dass sie sich selbst sogar zweimal pro Iterationsschritt aufruft. In der iterativen Formulierung benötigt man deswegen zwei Zwischenvariablen:

def fib(n):
    """ Iterative Berechnung der Fibonacci-Zahl zu n. """

    n2 = 1
    n1 = 1
    n0 = 1

    for i in range(3, n + 1):
        n0 = n1 + n2
        n2 = n1
        n1 = n0

    return n0