Rekursion

Bei der Rekursion ruft sich eine Funktion selbst auf, um ein Problem in kleinere Teile zu zerlegen. Jede rekursive Funktion braucht zwei Dinge:

1. einen Basisfall, bei dem sie ohne weiteren Selbstaufruf aufhört,
2. einen rekursiven Fall, der das Problem verkleinert und sich selbst aufruft.

Beispiel: Fakultät

Die Fakultät n! ist das Produkt aller Zahlen von 1 bis n. Es gilt n! = n · (n-1)! und 0! = 1.

def fakultaet(n):
    if n <= 1:                    # Basisfall
        return 1
    return n * fakultaet(n - 1)   # rekursiver Fall

print(fakultaet(5))
print(fakultaet(10))

120
3628800

So läuft fakultaet(3) ab: 3 * fakultaet(2) → 3 * (2 * fakultaet(1)) → 3 * (2 * 1) = 6.

Beispiel: Summe einer Liste und Countdown

def summe(liste):
    if not liste:
        return 0
    return liste[0] + summe(liste[1:])

def countdown(n):
    if n == 0:
        print("Start!")
        return
    print(n)
    countdown(n - 1)

print(summe([1, 2, 3, 4]))
countdown(3)

10
3
2
1
Start!

Fibonacci und das Problem der Mehrfachberechnung

Die Fibonacci-Folge beginnt mit 0 und 1, jede weitere Zahl ist die Summe der beiden vorigen: 0, 1, 1, 2, 3, 5, 8, ...

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print([fib(i) for i in range(10)])

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Diese Variante rechnet dieselben Werte immer wieder aus und wird für größere n extrem langsam. Mit Zwischenspeichern (Memoization) ist sie dagegen sofort fertig. Python bringt dafür functools.cache mit:

from functools import cache

@cache
def fib_schnell(n):
    if n < 2:
        return n
    return fib_schnell(n - 1) + fib_schnell(n - 2)

print(fib_schnell(80))

23416728348467685

Rekursionstiefe

Jeder Aufruf belegt Speicher. Python begrenzt die Tiefe (Standard: etwa 1000) und meldet sonst einen RecursionError. Das passiert auch, wenn der Basisfall fehlt:

def endlos(n):
    return endlos(n + 1)

endlos(0)

Traceback (most recent call last):
  ...
RecursionError: maximum recursion depth exceeded

import sys
print(sys.getrecursionlimit())

1000

Rekursion oder Schleife?

Alles, was rekursiv geht, geht auch mit einer Schleife. Rekursion lohnt sich vor allem bei Strukturen, die selbst verschachtelt sind: Ordnerbäume, verschachtelte Listen, Baumstrukturen.

def flach(liste):
    ergebnis = []
    for element in liste:
        if isinstance(element, list):
            ergebnis.extend(flach(element))
        else:
            ergebnis.append(element)
    return ergebnis

print(flach([1, [2, [3, 4]], 5, [[6]]]))

[1, 2, 3, 4, 5, 6]