EMZETT.
Login

Emzett Wiki

Python: Rekursion

Properties1
tagsprogrammiersprachen, python

3 Min. Lesezeit

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

Teil des Kurses Python

Kapitel 25 von 44 im Kurs Python. Mit Fortschritt, Quiz und Zertifikat auf der Lernseite.

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))

Ausgabe:

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)

Ausgabe:

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)])

Ausgabe:

[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))

Ausgabe:

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)

Fehlermeldung:

Traceback (most recent call last):
  ...
RecursionError: maximum recursion depth exceeded
import sys
print(sys.getrecursionlimit())

Ausgabe:

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]]]))

Ausgabe:

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

Merke

  • Rekursion = eine Funktion ruft sich selbst auf
  • Es braucht immer einen Basisfall, sonst gibt es einen RecursionError
  • Jeder Aufruf muss das Problem verkleinern
  • Doppelte Berechnungen vermeidest du mit functools.cache
  • Ideal für verschachtelte Strukturen wie Bäume

Übungsaufgabe

Schreibe eine rekursive Funktion potenz(basis, exponent), die ohne ** auskommt, und eine, die die Quersumme einer Zahl berechnet.

Quiz zur Selbstkontrolle

Weiter im Kurs

Zurück: Lambda, map, filter und Co.

Weiter: Iteratoren und Generatoren

Alle Kapitel: Python im Überblick

Graphansicht

Backlinks