Rekursive Algorithmen in Python: Laufzeitanalyse & Implementierung (2026)

Einführung in Rekursive Algorithmen

Rekursive Algorithmen sind ein zentrales Thema in der Datenstrukturen und Algorithmen Vorlesung (z.B. CS-UY 1134). Sie lösen Probleme, indem sie sich selbst aufrufen – oft mit einer reduzierten Problemgröße. Im Frühjahr 2024 beschäftigte sich ein bekanntes Homework mit genau diesen Konzepten. Auch 2026, im Zeitalter von generativer KI und Echtzeit-Finanzdashboards, ist das Verständnis von Rekursion essenziell. Ob du einen Algorithmus für eine Trading-App optimierst oder ein Spiel wie "Wordle" nachbaust – Rekursion hilft dir, komplexe Aufgaben elegant zu lösen.

Rekursive Summenberechnung: Zwei Varianten im Vergleich

Betrachten wir zwei Implementierungen zur Summe einer Liste. Die erste Version sum_lst1(lst) ruft sich mit einem Teillisten-Slice auf: rest = sum_lst1(lst[1:]). Die zweite Version sum_lst2(lst, low, high) arbeitet mit Indizes und vermeidet das Kopieren der Liste. Schauen wir uns die Laufzeitanalyse an.

Rekursionsbaum von sum_lst1

Bei sum_lst1 wird bei jedem Aufruf eine neue Liste (Slice) erstellt. Das kostet O(n) pro Aufruf, da die restlichen Elemente kopiert werden. Der Rekursionsbaum hat n Aufrufe, jeder mit lokalen Kosten O(n), O(n-1), … , O(1). Summiert ergibt das O(n²).

sum_lst1([1,2,3,4])
├─ sum_lst1([2,3,4])  (Kopie von 3 Elementen)
│  ├─ sum_lst1([3,4]) (Kopie von 2)
│  │  ├─ sum_lst1([4]) (Kopie von 1)
│  │  │  └─ return 4
│  │  └─ return 3+4
│  └─ return 2+7
└─ return 1+9
Gesamtkosten: O(4)+O(3)+O(2)+O(1) = O(n²)

Rekursionsbaum von sum_lst2

Bei sum_lst2 werden keine Listen kopiert. Jeder Aufruf addiert nur lst[low] + rest in O(1). Der Baum hat n Aufrufe, jeder mit O(1). Gesamt: O(n).

sum_lst2([1,2,3,4], 0, 3)
├─ sum_lst2([1,2,3,4], 1, 3)
│  ├─ sum_lst2([1,2,3,4], 2, 3)
│  │  ├─ sum_lst2([1,2,3,4], 3, 3) → return 4
│  │  └─ return 3+4
│  └─ return 2+7
└─ return 1+9
Jeder Aufruf: O(1), n Aufrufe → O(n)

Asymptotisch ist sum_lst2 schneller: O(n) vs. O(n²). Die Index-basierte Version ist daher vorzuziehen – ein wichtiger Tipp für deine Algorithmen-Hausaufgabe.

Laufzeitanalyse weiterer rekursiver Funktionen

Im Assignment werden Funktionen wie fun1, fun2 und fun3 analysiert. Sehen wir uns die Rekursionsbäume an.

fun1: Zwei rekursive Aufrufe pro Ebene

fun1(n) ruft fun1(n-1) zweimal auf. Der Rekursionsbaum ist ein voller Binärbaum der Tiefe n. Jeder Knoten hat O(1) Kosten. Anzahl Knoten: 2^n – 1. Also O(2^n) – exponentiell! Das erinnert an die Fibonacci-Folge ohne Memoization.

fun2: Halbierung der Problemgröße

fun2(n) ruft sich mit n//2 auf. Der Baum hat log₂(n) Ebenen, jeder Aufruf O(1). Gesamt: O(log n). Das ist super effizient – ähnlich wie die binäre Suche in einer sortierten Liste.

fun3: Halbierung + Schleife

fun3(n) ruft fun3(n//2) und führt dann eine Schleife von 1 bis n aus. Der Rekursionsbaum hat log₂(n) Ebenen. Die Kosten pro Ebene sind: n, n/2, n/4, … ≈ 2n. Also O(n).

Diese Analyse hilft dir, die asymptotische Laufzeit jeder Funktion zu bestimmen – eine Schlüsselkompetenz für Prüfungen und für die Optimierung von KI-Modellen, wo Rekursion oft in Entscheidungsbäumen vorkommt.

Rekursive Implementierung von Dreiecken und Linealen

Das Drucken von Mustern ist ein Klassiker. Schauen wir uns print_triangle an: Für n=4 soll das Muster * ** *** **** erscheinen. Rekursive Idee: Drucke zuerst eine Zeile mit n Sternen, dann rufe die Funktion für n-1 auf. Oder umgekehrt. Hier eine Implementierung:

def print_triangle(n):
    if n == 0:
        return
    print_triangle(n-1)
    print('*' * n)

# Aufruf: print_triangle(4)
# Ausgabe:
# *
# **
# ***
# ****

Für print_opposite_triangles kombinierst du zwei rekursive Aufrufe: einen absteigend, einen aufsteigend. Das erinnert an Muster in der Musikvisualisierung oder an Wellenformen in Audio-Apps.

Rekursives Lineal (print_ruler)

Das Lineal für n=4 erzeugt 15 Zeilen mit unterschiedlich vielen Minuszeichen. Die rekursive Idee: print_ruler(n-1) druckt die obere Hälfte, dann eine Zeile mit n Strichen, dann wieder print_ruler(n-1). Das ist ein Paradebeispiel für Teile-und-Herrsche, ähnlich wie bei der Rekonstruktion von Binärbäumen in der Bioinformatik.

def print_ruler(n):
    if n == 0:
        return
    print_ruler(n-1)
    print('-' * n)
    print_ruler(n-1)

# Aufruf: print_ruler(3)
# Ausgabe (verkürzt):
# -
# --
# -
# ---
# -
# --
# -

Dieses Muster findest du in UI-Scrollbars oder in der Dynamischen Programmierung wieder.

Weitere rekursive Aufgaben: Minimum, Zeichen zählen, Dictionary, Vorzeichen sortieren

Das Assignment enthält weitere Aufgaben, die du mit Rekursion lösen kannst.

Minimum in einem Bereich (list_min)

Rekursiv: Vergleiche lst[low] mit dem Minimum des restlichen Bereichs. Laufzeit O(n).

def list_min(lst, low, high):
    if low == high:
        return lst[low]
    rest_min = list_min(lst, low+1, high)
    return min(lst[low], rest_min)

Kleinbuchstaben zählen (count_lowercase)

Ähnlich: Zähle, ob das aktuelle Zeichen klein ist, plus das Ergebnis des rekursiven Aufrufs.

Dictionary mit Zeichenhäufigkeiten (appearances)

Rekursiv: Rufe die Funktion für den Rest auf, aktualisiere das zurückgegebene Dictionary mit dem aktuellen Zeichen. So lernst du den Umgang mit veränderlichen Objekten in der Rekursion.

def appearances(s, low, high):
    if low > high:
        return {}
    rest_dict = appearances(s, low+1, high)
    if s[low] in rest_dict:
        rest_dict[s[low]] += 1
    else:
        rest_dict[s[low]] = 1
    return rest_dict

Vorzeichen sortieren (split_by_sign)

Rekursiv: Tausche negative Elemente nach vorne. Dies ist eine Variante der Quicksort-Partitionierung, die in vielen Datenanalyse-Pipelines verwendet wird.

Verschachtelte Listen glätten (flat_list)

Rekursiv: Durchlaufe die Liste, rufe für jedes Unterliste die Funktion auf. Das ist nützlich für JSON-Verarbeitung oder Baumstrukturen in der KI-Entwicklung.

Fazit: Rekursion meistern für Studium und Praxis

Rekursive Algorithmen sind nicht nur ein Prüfungsthema, sondern auch im Berufsalltag unverzichtbar. Ob du einen Algorithmus für eine Finanz-App schreibst, eine KI-gestützte Suchfunktion baust oder ein Gaming-Tool entwickelst – die Prinzipien der Rekursion und Laufzeitanalyse helfen dir, effiziente Lösungen zu finden. Nutze die hier gezeigten Techniken, um deine Hausaufgaben in Datenstrukturen zu lösen und dein Verständnis zu vertiefen.

Denk daran: Übung macht den Meister. Implementiere die Funktionen selbst, zeichne Rekursionsbäume und analysiere die Laufzeiten. So wirst du fit für Prüfungen und echte Projekte in Python.