Rekursion

Wenn wir Programme schreiben, rufen wir normalerweise verschiedene Funktionen auf, die eine bestimmte Aufgabe erfüllen. Wir rufen zum Beispiel sqrt auf, um die Quadratwurzel einer Zahl zu berechnen, oder wir rufen max oder min auf, um das Maximum oder Minimum einer Menge von Zahlen zu finden. Beim Begriff „Rekursion“ geht es darum, dieselbe Funktion wieder aus sich selbst heraus aufzurufen. Wenn wir also eine Funktion mit dem Namen f definiert haben und irgendwo im Rumpf von f die Funktion f erneut aufrufen (oft mit anderen Argumenten), dann handelt es sich um einen rekursiven Aufruf:

def f(n):                                   # Definiert eine Funktion namens f
    print(f'f() called with argument {n}')  # Wird bei jedem Aufruf ausgegeben (zur Demonstration)
    if n <= 0:                              # Beenden, falls n negativ ist
        print('Let\'s stop here...')
    else:                                   # Andernfalls f mit einer kleineren Zahl aufrufen
        f(n - 1)

f(10)

This is what the program would print

f() called with argument 10
f() called with argument 9
f() called with argument 8
f() called with argument 7
f() called with argument 6
f() called with argument 5
f() called with argument 4
f() called with argument 3
f() called with argument 2
f() called with argument 1
f() called with argument 0
Let's stop here...

Dies ist ein kleines Beispiel dafür, wie man eine sehr grundlegende rekursive Funktion implementieren kann. In realeren Fällen führen wir in Funktionen normalerweise Berechnungen durch und geben anschließend die Ergebnisse zurück, anstatt nur Meldungen auszugeben.

In algorithmischen Aufgaben kann Rekursion sehr hilfreich sein, insbesondere wenn es um Graphen, fortgeschrittene Sortieralgorithmen oder Backtracking geht, auf die wir später im Kurs noch näher eingehen werden. Rekursive Aufgaben sind sehr verbreitet, und oft ist es einfacher, eine rekursive Lösung zu schreiben, als eine Schleifen-basierte.

Video preview — Ein Video von Reducible – 5 Simple Steps for Solving Any Recursive Problem

Der Prozess, ein großes Problem rekursiv in kleinere Teilprobleme zu zerlegen, bis man beim kleinsten bzw. einfachsten Teil angelangt ist, lässt sich am besten durch das Prinzip des sogenannten “recursive leap of faith” (rekursiver Vertrauensvorschuss) verdeutlichen.

Recursive Leap of Faith

Wenn man eine rekursive Lösung für ein Problem implementiert, schreibt man meistens eine Funktion, die sich an einer Stelle selbst aufruft. Dieser Teil, in dem die Funktion sich selbst aufruft, wird als rekursiver Aufruf bezeichnet.

Der große Vorteil rekursiver Lösungen liegt darin, dass man davon ausgehen kann, dass die Funktion bei einfacheren Argumenten korrekt funktioniert, und dann das richtige Verhalten für kompliziertere Fälle implementiert. Ähnlich wie beim Aufruf anderer Funktionen wie sqrt, max oder abs kann man sich darauf verlassen, dass die Funktion für einfachere Argumente bereits korrekt arbeitet, und baut das aktuelle Ergebnis darauf auf.

💡

Die einzige Voraussetzung ist, dass die Funktion irgendwann den Basisfall (das einfachste Szenario) erreicht. Ansonsten würde die Funktion endlos laufen und könnte einen StackOverflow verursachen!

Als Beispiel für eine Berechnung in einer rekursiven Funktion können wir die Summe aller Zahlen von 0, 1, 2, …, n für ein gegebenes n berechnen.

Schauen wir uns Schritt für Schritt an, wie wir die Funktion sum implementieren können. Zuerst muss sichergestellt sein, dass die Funktion für den einfachsten Fall korrekt funktioniert (d. h. richtig für n = 0 oder 1 rechnet):

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:         # Falls n gleich 0 ist => Summe ist 0
        return 0       # Funktion hier beenden
    if n == 1:         # Falls n gleich 1 ist => Summe ist 1
        return 1       # Funktion hier beenden

print(sum(1))          # sum(1) -> 1
print(sum(0))          # sum(0) -> 0
print(sum(2))          # sum(2) -> None (da dieser Teil noch nicht implementiert ist)

Mit diesem Teil der Funktion können wir bereits nutzen, dass sum(0) immer 0 und sum(1) immer 1 zurückgibt. Selbst wenn wir die Funktion sum von sich aus mit 0 oder 1 aufrufen, wird das Ergebnis korrekt sein.

Nun können wir einen Schritt weitergehen und die Funktion sum für n = 2 und n = 3 implementieren, indem wir die Ergebnisse von sum(1) und sum(0) verwenden:

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:             # Wenn n 2 ist, addieren wir 2 zum Ergebnis von sum(1)
        return n + sum(1)  # oder n + sum(n - 1)
    if n == 3:             # Wenn n 3 ist, addieren wir 3 zum Ergebnis von sum(2)
        return n + sum(2)  # oder n + sum(n - 1)

print(sum(1))          # sum(1) -> 1
print(sum(0))          # sum(0) -> 0
print(sum(2))          # sum(2) -> sum(1) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4))          # sum(4) -> None (für diesen Wert ist noch nichts definiert)

So ist klar, dass die Funktion sum für die kleinen Fälle (n = 0, 1, 2 oder 3) richtig funktioniert.

Auf dieser Grundlage können wir die Funktion für andere Werte von n größer als 3 erweitern. Die einzige Bedingung ist, dass wir letztendlich zu den kleineren n-Werten (0, 1, 2 oder 3) gelangen, wenn wir die Funktion sum wiederholt aus ihr selbst aufrufen. Für größere Werte wie 4, 5, 6 usw. können wir sum um den Ansatz ergänzen, dass man zur Berechnung von sum(4) einfach 4 zur bereits bekannten sum(3) addiert, und entsprechend für sum(5) 5 zu sum(4):

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return n + sum(1)
    if n == 3:
        return n + sum(2)
    # Für alle anderen Fälle (4, 5, 6, ...)
    return n + sum(n - 1)  

print(sum(2))          # sum(2) -> sum(1) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4))          # sum(4) -> sum(3) -> sum(2) -> sum(1) -> 10
# ...

Die wichtigsten Bestandteile einer rekursiven Funktion sind:

Basisfall: Eine Bedingung, die die Rekursion beendet. Ohne diese Bedingung würde sich die Funktion endlos selbst aufrufen und in einer Endlosschleife hängen. Hier sind das n == 0 und n == 1.

Rekursiver Schritt: Der Teil, in dem die Funktion sich selbst aufruft, meist mit einem anderen Argument. Hier ist das sum(n - 1).

Da die Fälle für n == 1, n == 2 und n == 3 identisch zu den Fällen für n == 4, n == 5 usw. sind, können wir die Funktion sum sogar so vereinfachen, dass wir nur einen einzigen Basisfall (für n == 0) haben:

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    return n + sum(n - 1)  

print(sum(2))          # sum(2) -> sum(1) -> sum(0) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> sum(0) -> 6
print(sum(4))          # sum(4) -> sum(3) -> sum(2) -> sum(1) -> sum(0) -> 10
# ...

Mit diesem „recursive leap of faith“ können wir davon ausgehen (bzw. wissen), dass die Funktion für kleinere/einfachere Fälle korrekt arbeitet, und darauf aufbauend den Rest der Funktion implementieren. Das erleichtert das Verständnis für rekursive Funktionen und deren Umsetzung.

💡

Der rekursive Funktionsaufruf verhält sich so, als würde eine völlig andere Funktion aufgerufen, von der Sie ganz sicher wissen, dass sie mit den übergebenen Argumenten korrekt funktioniert.

Challenge

Implementieren Sie eine rekursive Funktion, die das Ergebnis von n! modulo berechnet.

Eingabe

Die Eingabe besteht aus einer einzelnen ganzen Zahl n (1 ≤ n ≤ 1000).

Ausgabe

Das Programm soll das Ergebnis von n! modulo ausgeben.

Beispiele

Input	Output
5	120
10	3628800

Recursive Leap of Faith

Challenge

Eingabe

Ausgabe

Beispiele

Constraints

To check your solution you need to sign in

Sign in to continue