Rekursion verstehen: Basisfall und Aufrufstapel

Rekursion bedeutet, dass eine Funktion ein Problem löst, indem sie sich mit einem kleineren Problem selbst aufruft. Sie brauchen dafür nur zwei Dinge: einen Fall, der sich direkt lösen lässt, und einen Schritt, der das Problem kleiner macht.

Die Größe eines Ordners auf der Festplatte ist die Summe seiner Dateien plus die Größe jedes Unterordners. Für den Unterordner gilt derselbe Satz.

Die Fakultät von 4 ist 4 mal 3 mal 2 mal 1. Das ist 4 mal die Fakultät von 3. So erhalten Sie die Regel: n Fakultät ist n mal (n minus 1) Fakultät.

Der Basisfall ist die Fakultät von 1, und sie ist 1. Der rekursive Fall ruft die Funktion mit n minus 1 auf. Jeder Aufruf macht die Zahl kleiner, bis der Basisfall kommt.

# Die Fakultaet: 4! = 4 * 3 * 2 * 1.
def fakultaet(n):
    print("Aufruf mit n =", n)
    if n <= 1:
        return 1  # Basisfall: hier hoert die Rekursion auf
    ergebnis = n * fakultaet(n - 1)  # rekursiver Fall: ein kleineres Problem
    print("Rueckgabe", ergebnis, "fuer n =", n)
    return ergebnis

print(fakultaet(4))
# Aendern Sie 4 auf 6. Wie viele Aufrufe sehen Sie?

Ruft eine Funktion sich selbst auf, muss der erste Aufruf warten. Python merkt sich das auf dem Aufrufstapel: Oben liegt der neueste Aufruf, und nur der oberste arbeitet.

Hat der Basisfall ein Ergebnis, wird der Stapel von oben nach unten abgebaut. Jeder Aufruf rechnet mit dem Ergebnis des Aufrufs über ihm weiter.

Der Stapel ist nicht unendlich groß. Python erlaubt nur eine feste Zahl offener Aufrufe und meldet danach einen Fehler. Der erste Befehl zeigt diese Grenze.

Der zweite und dritte rechnen mit der Fakultät aus der Standardbibliothek. Sie sehen, dass 6 Fakultät genau 6 mal 5 Fakultät ist.

python3 -c "import sys; print(sys.getrecursionlimit())"

python3 -c "import math; print(math.factorial(10))"

python3 -c "import math; print(math.factorial(5), math.factorial(6) // math.factorial(5))"

Eine Fibonacci-Zahl ist die Summe der beiden davor: 0, 1, 1, 2, 3, 5, 8. Die Funktion fib ruft sich deshalb zweimal auf, mit n minus 1 und mit n minus 2.

Der Basisfall sind die Zahlen unter 2. Ein Aufruf erzeugt zwei neue, jeder von ihnen wieder zwei. Die Zahl der Aufrufe wächst darum rasant.

# Die Fibonacci-Zahlen: jede ist die Summe der beiden davor.
aufrufe = [0]

def fib(n):
    aufrufe[0] = aufrufe[0] + 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

for n in [5, 10, 20]:
    aufrufe[0] = 0
    print("fib(", n, ") =", fib(n), "Aufrufe:", aufrufe[0])
# Probieren Sie 25. Warten Sie auf die Ausgabe und lesen Sie die Zahl der Aufrufe.

Schreiben Sie potenz(basis, exponent) rekursiv. Der Basisfall ist der Exponent 0 mit dem Ergebnis 1. Sonst gilt: basis mal potenz(basis, exponent - 1).

Wie viele Aufrufe macht potenz(2, 10)? Vergleichen Sie mit python3 -c "print(2 ** 10)" im Lab.