Rekursion in Python

Problem

Wie viele Anordnungen gibt es?

Im Regal stehen 5 Bücher. Auf wie viele Arten kannst du sie anordnen? Für den ersten Platz gibt es 5 Möglichkeiten, für den zweiten 4, dann 3, 2 und 1: 5 · 4 · 3 · 2 · 1 = 120. Das ist die Fakultät, geschrieben 5!.

Mit einer Schleife kannst du das schon:

def factorial_loop(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result


print(factorial_loop(5))

Sieh es auch so: 5! = 5 · 4!. Und 4! = 4 · 3!. Die Aufgabe wird über dieselbe Aufgabe, nur kleiner gelöst. Kann die Funktion genau das sagen?

Die Idee

Eine Funktion, die sich selbst aufruft

Sie kann. Eine Funktion, die sich selbst aufruft, nennt man rekursiv, und das Vorgehen Rekursion.

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)


print(factorial(5))

Zwei Dinge sorgen dafür, dass es funktioniert:

Ein Basisfall. Ein Fall, der direkt gelöst wird, ohne neuen Aufruf. Hier: 1! = 1.
Eine kleinere Aufgabe. Jeder Aufruf ruft sich selbst mit einer Zahl auf, die näher am Basisfall liegt: n - 1.

Sieh es dir an

Der Stapel der Aufrufe

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)


print(factorial(3))  # 6

Schritt für Schritt, in Worten

Das Programm ruft factorial(3) auf.
Neuer Speicher für factorial mit n = 3.
3 ist nicht 1, also ruft die Funktion factorial(2) auf und wartet auf die Antwort.
Dasselbe noch einmal: factorial(2) ruft factorial(1) auf. Jeder Aufruf hat sein eigenes n.
n ist 1: Das ist der Basisfall. Er gibt 1 zurück, ohne sich noch einmal aufzurufen.
Die Antwort geht nach unten zurück: 2 * 1 = 2.
Und noch einmal: 3 * 2 = 6.
factorial(3) gibt 6 zurück, und das Programm gibt es aus.

Jeder Aufruf bekommt seinen eigenen Speicher mit seinem eigenen n. Sie stapeln sich übereinander und warten. Diesen Stapel nennt man Aufrufstapel (call stack). Wenn der Basisfall 1 zurückgibt, gehen die Antworten eine nach der anderen nach unten zurück, und der Stapel löst sich auf.

Probier es aus

Runter und wieder rauf

Was gibt das Programm aus?

def steps(n):
    if n == 0:
        return
    print(f"runter {n}")
    steps(n - 1)
    print(f"rauf {n}")


steps(2)

Antwort

runter 2
runter 1
rauf 1
rauf 2

runter 2
runter 1
rauf 2
rauf 1

runter 2
rauf 2
runter 1
rauf 1

Probier es aus

Finde den Fehler

sum_to(4) soll 1 + 2 + 3 + 4 = 10 zurückgeben. Stattdessen bricht das Programm mit RecursionError: maximum recursion depth exceeded ab. In welcher Zeile ist der Fehler?

Wähle die Zeile mit dem Fehler.

Die Idee

Rekursion oder Schleife?

Die Fakultät lässt sich mit einer Schleife oder mit Rekursion schreiben. Hier ist die Schleife die bessere Wahl: Sie häuft nicht für jeden Aufruf Speicher an. Und Python setzt dem Stapel eine Grenze: Bei etwa 1000 verschachtelten Aufrufen bricht es das Programm mit einem RecursionError ab. Schon factorial(1100) kommt nicht durch, während die Schleife auch das ausrechnet.

Rekursion ist dort natürlich, wo eine Sache kleinere Sachen derselben Art enthält: ein Ordner mit Ordnern darin, eine Kategorie mit Unterkategorien, ein Ast mit Ästen. Solchen Aufgaben begegnest du später im Kurs. Dort wird eine Schleife umständlich, während die rekursive Funktion kurz bleibt.

Genauer, für Neugierige

Die Fakultät schreibt man oft mit dem Basisfall 0! = 1 (if n == 0:). Dann funktioniert sie auch für 0.

Ganze Zahlen haben in Python keine Grenze: Wie groß das Ergebnis auch ist, so viele Ziffern hat es. 30! kommt genau heraus:

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)


print(factorial(30))

265252859812191058636308480000000

Die Grenze des Stapels kannst du mit sys.setrecursionlimit() anheben, aber das ist selten eine gute Idee: Für tiefe Berechnungen schreib eine Schleife.

Probier es aus

Bring die Zeilen in die richtige Reihenfolge

Die Funktion soll eine Potenz berechnen: power(2, 10) ist 1024. Bring ihre Zeilen in die richtige Reihenfolge.

def power(base, exp):
return 1
return base * power(base, exp - 1)
if exp == 0:

Übung

Rekursive Aufgaben

1. Fakultät auf zwei Arten. Schreib factorial_loop(n) mit einer for-Schleife und factorial(n) mit Rekursion. Lies eine Zahl ein und gib das Ergebnis beider Funktionen aus.

Die Fakultät von 5 ist 120
Die Fakultät von 5 ist 120

2. Quersumme. sum_digits(n): die letzte Ziffer (n % 10) plus die Quersumme des Rests (n // 10). Der Basisfall ist eine einstellige Zahl.

3. Fibonacci. Jede Zahl ist die Summe der zwei davor: 0, 1, 1, 2, 3, 5, 8… fib(n) gibt die n-te Zahl zurück. Probier es mit 10 und dann mit 35. Warum ist es so langsam? Hinweis: Wie oft wird jede Zahl ausgerechnet?

4. Palindrom. is_palindrome(s): Der erste und der letzte Buchstabe sind gleich, und die Mitte ist ein Palindrom. Der Basisfall ist ein Wort mit 0 oder 1 Buchstaben.

sum_digits(2024)
fib(10)
is_palindrome("neben")
is_palindrome("ABCDE")

8
55
True
False

Test

Teste dich

1. Was ist Rekursion?Eine Funktion, die sich selbst aufruftEine Schleife in einer FunktionZwei Funktionen mit demselben Namen

2. Warum braucht eine rekursive Funktion einen Basisfall?Damit sie aufhört, sich selbst aufzurufenDamit sie ein Ergebnis zurückgeben kannDamit sie schneller läuft

3. factorial(3) ruft factorial(2) auf, und das ruft factorial(1) auf. Wie viele Variablen n sind im Speicher, kurz bevor factorial(1) zurückkehrt?KeineDreiEine

4. Was passiert, wenn der Basisfall nie erreicht wird?Der Stapel läuft über, und das Programm bricht mit einem RecursionError abDie Funktion gibt 0 zurückDas Programm läuft ewig, ohne Fehler

Rekursion

Cookies