Rekursive Funktionen

Rekursive Funktionen#

Rekursive Funktionen sind Funktionen, die sich selbst aufrufen. Als Rekursion (lateinisch recurrere ‘zurücklaufen’) wird ein unendlicher Vorgang, der sich selbst als Teil enthält oder mithilfe von sich selbst definierbar ist, bezeichnet.

Rekursionen werden insbesondere bei Divide-and-Conquer-Algorithmen oder bei kombinatorischen Problemen verwendet.

Um in Python eine rekursive Funktion zu definieren, brauchen wir nur eine Funktion, die sich selbst aufruft.

def rekursive_funktion():
	# Statement
	rekursive_funktion() # Wir rufen uns selbst (als funktion) nocheinmal auf

Mit rekursiven Funktionen lassen sich zum Beispiel Schleifen implementieren.

def while_loop(n): # n als die maximale tiefe der rekursion
	if n > 0:
		print(f"Die Funktion wird rekursiv ausgeführt bis die Bedingung am Anfang der Schleife {n} > 0 wahr ist")
		while_loop(n - 1) # wir zählen die variable n runter

Die rekursive Funktion wird 3-mal ausgeführt da die Bedingung wahr ist und wir bis 0 runter zählen. Genauso wie bei der While-Schleife.

while_loop(3)

Die Funktion wird rekursiv ausgeführt bis die Bedingung am Anfang der Schleife 3 > 0 wahr ist
Die Funktion wird rekursiv ausgeführt bis die Bedingung am Anfang der Schleife 2 > 0 wahr ist
Die Funktion wird rekursiv ausgeführt bis die Bedingung am Anfang der Schleife 1 > 0 wahr ist

Damit zeigt sich, dass sich Schleifen sich immer als Rekursion implementieren lassen. Etwas was funktionsorientierte Programmiersprachen nutzen, die nur Funktionen kennen.

Beispiel Rekursiver Funktion - Fakultät#

Das Standardbeispiel einer rekursiven Funktion ist die Berechnung der Fakultät einer Zahl. Sie ist definiert als Produkt der natürlichen Zahlen von 1 bis \(n\).

\(n! = 1 \cdot 2 \cdot 3 \cdots n = \prod_{k=1}^n k\)

def factorial_recursiv(x):
    if x > 1:
        return x * factorial_recursiv(x-1)
    else:
        return 1

Die Fakultät der Zahl 10 ist definiert als:

10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

3628800

was identisch ist mit dem Ergebnis unserer Funktion

factorial_recursiv(10)

3628800

Wenn wir die Funktion aufrufen, so ruft diese sich wiederholt selbst auf und zählt dabei von x=10 runter bis zu 1. Jeder Funktionsaufruf kann dabei als Klammer gesehen werden, so dass am Ende die folgende Berechnung durchgeführt ist, die mit der obigen Berechnung übereinstimmt.

10 * (9 * (8 * (7 * (6 * (5 * (4 * (3 * (2 * (1)))))))))

3628800

Dieses einfache Beispiel kann auch durch eine Schleife implementiert werden.

def factorial_schleife(x):
    res = x
    i = x - 1
    while i > 1:
        res *= i
        i -= 1
    return res

factorial_schleife(10)

3628800

Dies ist meist performanter, da Funktionen grundsätzlich etwas länger zum Ausführen brauchen, da sie ja z.B. ihr eigenen Variablenbereich haben und auf dem Stack laufen (siehe nächsten Abschnitt).

Wir machen einmal einen Laufzeitvergleich mit der timeit Funktion des Jupyter Notebooks. Dies ruft die Funktion mehrmals auf und berechnet die durchschnittliche Ausführzeit.

%timeit factorial_recursiv(1000)

283 μs ± 1.26 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

%timeit factorial_schleife(1000)

178 μs ± 281 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

Wir sehen, dass die Schleifenvariante etwas schneller ist als die rekursive Variante.

Allerdings sind rekursive Funktionen meist lesbarer und können nicht immer in Schleifen aufgelöst werden, wenn z.B. mehrere Variablen manipuliert werden.

Endlosrekursion, Stack und Heap#

Warning

Da rekursive Funktionen den Schleifen konzeptionell ähneln, gibt es hier auch dasselbe Problem von Endlosrekursionen. Wie bei while-Schleifen können rekursive Funktionen sich theoretisch endlos verzweigen!

Deshalb muss mindestens ein Pfad in der Funktion nicht rekursiv sein.

Praktisch kommt es allerdings bei endloser Rekursion zu Stack-Overflow-Fehlern. Das liegt daran, dass Python nachvollziehen muss, welche Funktion welche andere aufgerufen hat, um beim Beenden in die richtige Funktion und Position zurückzukehren. Das geschieht über eine Liste, die sich Stack nennt.

Der Stack ist eine LIFO-Liste (Last In First Out) bei der das letzte Element das hinzugefügt wird (die neu aufgerufene Funktion) auch das erste sein muss, was entfernt wird (wenn die neu aufgerufene Funktion wird beendet). Quasi wie ein Bücherstapel. Der Stack wird bei endloser Rekursion so groß, dass er nicht mehr in den vorgesehenen Speicher passt, was der Stack-Overflow-Fehler ist.

Nebenbei, die Variablen werden nicht im Stack abgespeichert, sondern liegen im Heap. Dieser kann im Vergleich zum Stack so groß werden wie der Arbeitsspeicher und gleicht mehr einer FIFO-Liste (First In First Out), da Speicher von alten Variablen, die nicht mehr Gültigkeit haben frei gegeben werden.

Ein Stack-Overflow-Fehler ist ein kritischer Programmfehler, der nicht abgefangen werden kann, sondern immer zum Beenden des Programmes führt. Als Beispiel rufen wir unser als erste definierte rekursive Funktion auf und sehen die Fehlermeldung vom Absturz des Python-Kernels.

# Wenn wir die folgende Funktion ausführen erhalten wir die darunter stehende Fehlermeldung

#rekursive_funktion()

Canceled future for execute_request message before replies were done

Der Kernel ist beim Ausführen von Code in der aktuellen Zelle oder einer vorherigen Zelle abgestürzt. Bitte überprüfen Sie den Code in der/den Zelle(n), um eine mögliche Fehlerursache zu identifizieren. Klicken Sie hier, um weitere Informationen zu erhalten. Weitere Details finden Sie in Jupyter log.

Contents