Rekursion in Python: Konzepte, Beispiele und Tipps

Die Rekursion ist ein grundlegendes Konzept in der Programmierung und hat in Python eine besondere Bedeutung. Sie bezieht sich auf die Technik, bei der eine Funktion sich selbst aufruft, um ein Problem zu lösen, und es in kleinere, handhabbare Teilprobleme zerlegt. 

Diese Methode ermöglicht elegante und prägnante Lösungen, insbesondere bei Problemen, die sich wiederholende Aufgaben oder hierarchische Strukturen beinhalten. In Python wird die Rekursion in einer Vielzahl von Anwendungen eingesetzt, von Sortier Algorithmen bis hin zu komplexen Datentransversalen.

Rekursive Lösungen spiegeln oft die mathematischen Definitionen von Problemen wider, sodass sie für diejenigen, die mit mathematischem Denken vertraut sind, intuitiv sind. Die Schönheit der Rekursion liegt in ihrer Fähigkeit, komplexe Algorithmen in nur wenigen Zeilen Code auszudrücken und so Lösungen zu schaffen, die sowohl elegant als auch lesbar sind. Die Beherrschung der Rekursion erfordert jedoch ein Umdenken gegenüber den üblichen iterativen Ansätzen.

In diesem Artikel gehe ich auf das Konzept der Rekursion, ihre Funktionsweise in Python und ihre praktischen Anwendungen ein und erörtere allgemeine Probleme und Vergleiche zur Iteration. Wenn du Python noch nicht kennst, solltest du einen unserer Kurse besuchen, zum Beispiel Einführung in Python, Programmierparadigma-Konzepteoder Grundlagen der Python-Programmierung.

Was ist Rekursion in Python?

In Python bedeutet Rekursion, dass eine Funktion sich selbst aufruft, um ein Problem zu lösen. Sie umfasst zwei entscheidende Komponenten:

• Basisfall: Dies ist die Bedingung, die die Rekursion beendet. Ohne sie würden die rekursiven Aufrufe ewig weitergehen und schließlich zum Absturz der Funktion führen oder den verfügbaren Speicher erschöpfen.
• Rekursiver Fall: Bei diesem Teil der Funktion wird das Problem in kleinere Teile zerlegt und die Funktion mit diesen kleineren Teilen erneut aufgerufen.

Hier ist eine einfache Art, über Rekursion nachzudenken: Stell dir eine Funktion vor, die ein komplexes Problem löst, indem sie kleinere Versionen desselben Problems löst und schließlich zu einer Lösung gelangt, die eine weitere Rekursion erfordert.

Der rekursive Ansatz folgt der "Teile und Herrsche"-Strategie, bei der komplexe Probleme in einfachere Versionen zerlegt werden, bis ein trivialer Fall erreicht wird. Dieser Ansatz spiegelt oft die Art und Weise wider, wie wir von Natur aus über die Lösung von Problemen denken. Wenn wir zum Beispiel einen Kartensatz sortieren, können wir natürlich kleinere Gruppen sortieren und diese dann kombinieren. Mischsortierung funktionieren.

Jede rekursive Funktion muss mindestens einen Basisfall und mindestens einen rekursiven Fall haben. Der Basisfall verhindert eine unendliche Rekursion, indem er eine Bedingung stellt, die keine weiteren Funktionsaufrufe erfordert. Der rekursive Fall reduziert die Problemgröße mit jedem Aufruf und stellt sicher, dass der Basisfall schließlich erreicht wird.

Wie funktioniert die Rekursion in Python?

Rekursion funktioniert, indem eine Funktion sich selbst mit geänderten Argumenten aufruft und so das Problem nach und nach in kleineren Schritten löst. Um dies konkreter zu verstehen, betrachte die Aufgabe, die Summe der Zahlen von 1 bis num zu berechnen.

Hier ist ein einfacher rekursiver Ansatz, um die Summe zu berechnen:

def sum_recursive(num):
    if num == 1:  # Base case
        return num
    return num + sum_recursive(num - 1)  # Recursive case

print(sum_recursive(3)) # 3 + 2 + 1 

6

Bei dieser Funktion ist der Basisfall, dass num == 1 die Rekursion beendet. Ansonsten ruft die Funktion sich selbst mit num - 1 auf, bis sie den Basisfall erreicht.

So funktioniert es Schritt für Schritt:

1. sum_recursive(3) ruft sum_recursive(2) auf.
2. sum_recursive(2) ruft sum_recursive(1) auf.
3. sum_recursive(1) ergibt 1 (Basisfall).
4. Jetzt kann sum_recursive(2) 2 + 1 = 3 zurückgeben, und sum_recursive(3) kann 3 + 3 = 6 zurückgeben.

Ein anderes Beispiel wäre eine rekursive Funktion zur Berechnung der Potenz einer Zahl:

def power(base, exponent):
    if exponent == 0:  # Base case
        return 1
    else:
        return base * power(base, exponent - 1)  # Recursive case

print(power(2, 3))

8

Schritt-für-Schritt-Erklärung dieser Leistungsfunktion:

• power(2, 3) ruft power(2, 2) auf.
• power(2, 2) ruft power(2, 1) auf.
• power(2, 1) ruft power(2, 0) auf.
• power(2, 0) ergibt 1 (Basisfall).
• Jetzt arbeiten wir rückwärts: power(2, 1) gibt 2 * 1 = 2 zurück.
• Dann gibt power(2, 2) 2 * 2 = 4 zurück.
• Schließlich gibt power(2, 3) 2 * 4 = 8 zurück.

Wenn eine rekursive Funktion aufgerufen wird, erzeugt jeder rekursive Aufruf einen neuen Eintrag auf dem Aufrufstapel. Auf diesem Lernpfad werden alle Funktionsaufrufe und ihre Variablen gespeichert. Wenn der Basisfall erreicht ist, beginnt der Stapel, jeden Aufruf in umgekehrter Reihenfolge aufzulösen und das Endergebnis Schritt für Schritt zu berechnen.

Das Verständnis dieses Stack-Verhaltens ist wichtig, weil es sowohl die Möglichkeiten als auch die Grenzen der Rekursion in Python erklärt. Sie bewahrt den Kontext auf elegante Weise, kann aber bei tiefen Rekursionen auch zu Speicherproblemen führen.

Implementierung der Fakultät in Python mit Rekursion

Die Fakultät ist ein klassisches Beispiel, um die Rekursion zu demonstrieren. Die Fakultät einer Zahl n, bezeichnet mit n!, ist das Produkt aller positiven ganzen Zahlen, die kleiner oder gleich n sind. Mathematisch gesehen:

n! = n × (n − 1) × (n − 2) × … × 1

Rekursiv kann die Fakultät wie folgt definiert werden:

n! = n × (n − 1)!

Lass uns das in Python implementieren:

def compute_factorial(num):
    if num == 0:  # Base case
        return 1
    return num * compute_factorial(num - 1)  # Recursive case

print(compute_factorial(4)) # 4 * 3 * 2 * 1

24

Schritt-für-Schritt-Erklärung des Codes:

• Die Funktion compute_factorial(num) prüft, ob num == 0 und gibt in diesem Fall 1 zurück.
• Andernfalls gibt sie num * compute_factorial(num - 1) zurück, wobei die Funktion sich selbst mit einem kleineren Wert von num aufruft.

Die faktorielle Funktion veranschaulicht perfekt die Eleganz der Rekursion. Die mathematische Definition selbst ist rekursiv, wodurch die Code-Implementierung intuitiv und eng an das mathematische Konzept angelehnt ist. Das ist eine der Stärken der Rekursion: Sie ermöglicht es dem Code, mathematische Definitionen direkt auszudrücken.

Es ist wichtig zu erwähnen, dass es Randfälle gibt, die berücksichtigt werden müssen. Die Fakultät ist zum Beispiel normalerweise nur für nichtnegative ganze Zahlen definiert. Eine robuste Implementierung könnte eine Fehlerbehandlung für negative Eingaben oder eine Typüberprüfung beinhalten. 

Außerdem kann die rekursive Lösung bei großen Werten von num zu einem Stack Overflow führen, eine Einschränkung, auf die ich noch näher eingehen werde.

Gemeinsame Probleme: Wie man Rekursionsfehler in Python behebt

Die Rekursion kann zwar ein mächtiges Werkzeug sein, aber sie ist auch anfällig für ein paar häufige Probleme:

Überschreiten der maximalen Rekursionstiefe

Python hat eine Standardrekursionsgrenze von 1000 Aufrufen. Wenn eine rekursive Funktion sich selbst zu oft aufruft, wird eine RecursionError ausgelöst.

Hier ist, wie du es reparierst:

Du kannst die Rekursionstiefe mit sys.setrecursionlimit() erhöhen. Dies wird jedoch nicht empfohlen, es sei denn, es ist notwendig, da es zu einem Stapelüberlauf kommen kann.

import sys  

# Get the current recursion limit
current_limit = sys.getrecursionlimit()
print(f'Current limit: {current_limit}')  

# Set a new recursion limit to 200
new_limit = 200
sys.setrecursionlimit(new_limit)  

# Get the new recursion limit
changed_current_limit = sys.getrecursionlimit()
print(f'Current limit after change: {changed_current_limit}')  

Current limit: 1000
Current limit after change: 200

Fehlender Basisfall

Ein fehlender oder falscher Basisfall führt dazu, dass die Funktion unendlich rekursiert, was zu einem Stapelüberlauf führt.

Um das Problem zu beheben, musst du sicherstellen, dass dein Basisfall gut definiert und erreichbar ist.

Wie man die Rekursion in Python beendet

Der Schlüssel zum Stoppen von Rekursionen in Python ist die Definition eines geeigneten Basisfalls. Ohne sie wird die Rekursion nie enden und zu einem Fehler führen.

Bei der Faktor-Funktion, die ich vorhin implementiert habe, war zum Beispiel der Basisfall if num == 0, was die Rekursion beendet. Im Allgemeinen musst du sicherstellen, dass jede rekursive Funktion eine Bedingung hat, unter der sie beendet wird.

Die Entwicklung effektiver Basisfälle erfordert sorgfältige Überlegungen. Einige Richtlinien sind:

• Finde die einfachste Version des Problems, die direkt gelöst werden kann.
• Stelle sicher, dass alle rekursiven Pfade schließlich einen Basisfall erreichen.
• Teste Randfälle separat, um sicherzustellen, dass sie richtig behandelt werden.
• Berücksichtige mehrere Basisfälle, wenn das Problem dies erfordert.

Manchmal sind defensive Programmiertechniken hilfreich, indem sie Schutzmechanismen gegen ungültige Eingaben oder Laufzeitprüfungen hinzufügen, um eine zu große Rekursionstiefe zu verhindern. Zum Beispiel:

def safe_factorial(num, depth=0, max_depth=100):
    # Check if recursion is too deep
    if depth > max_depth:
        raise ValueError("Maximum recursion depth exceeded")
   
    # Base case
    if num <= 0:
        return 1
   
    # Recursive case with depth tracking
    return num * safe_factorial(num - 1, depth + 1, max_depth)

# Calculate factorial of 5 with default depth limits
result = safe_factorial(5)

print(result) 

120

# Calculate factorial of 5 with depth > max_depth
result = safe_factorial(5, depth=20, max_depth=10)

print(result) 

ValueError: Maximum recursion depth exceeded

Mit diesem Ansatz kannst du benutzerdefinierte Grenzwerte festlegen und aussagekräftigere Fehlermeldungen als die Standardvorgabe RecursionError bereitstellen.

Hier ist ein weiteres Beispiel, das eine andere Art der Definition von Grundfällen zeigt: das Finden des größten gemeinsamen Teilers (GCD) von zwei Zahlen mithilfe einer Rekursion.

Der GCD von zwei Zahlen x und y kann mit dem Euklidschen Algorithmus berechnet werden, wobei der Modulo-Operator %:

• Basisfall: Wenn y == 0, ist der GCD x.
• Rekursiver Fall: Ansonsten ist der GCD von x und y derselbe wie der GCD von y und x % y.

def find_gcd(x, y):
    # Base case: if y is 0, the GCD is x
    if y == 0:
        return x
    # Recursive case: GCD of y and x % y
    return find_gcd(y, x % y)

print(find_gcd(48, 18))  

6

Rekursion vs. Iteration in Python

Sowohl Rekursion als auch Iteration können viele der gleichen Probleme lösen, aber beide haben ihre Vor- und Nachteile:

• Rekursion ist oft eleganter und leichter zu verstehen, vor allem bei Problemen, die eine natürliche rekursive Struktur haben (z. B., BaumüberquerungenFaktorzahlen, Fibonacci-Zahlen).
• Die Iteration kann effizienter sein, weil sie nicht den Overhead mehrerer Funktionsaufrufe mit sich bringt und Probleme im Zusammenhang mit einem Stack Overflow vermeiden kann. Iterative Lösungen sind in der Regel speichereffizienter.

Wann man Rekursion verwendet:

• Wenn das Problem auf natürliche Weise in kleinere Teilprobleme unterteilt werden kann.
• Für Probleme mit hierarchischen Datenstrukturen, wie Bäumen.
• Wenn die Lösung in rekursiver Form vorliegt, ist sie intuitiver und führt zu saubererem Code.
• Wenn die Lesbarkeit des Codes Vorrang vor der Leistungsoptimierung hat.
• Wenn du mit Daten von unbekannter Tiefe arbeitest (z. B. beim Parsen von verschachteltem JSON oder XML).

Wann man Iteration verwendet:

• Bei Problemen, die sich wiederholende Aufgaben erfordern, ohne das Problem in kleinere Teilprobleme zu unterteilen.
• Für leistungskritische Aufgaben, bei denen tiefe Rekursionen zu einem hohen Speicherverbrauch führen können.
• Bei der Arbeit mit großen Datensätzen, die die Rekursionsgrenze überschreiten könnten.
• Wenn die Speichernutzung ein Hauptanliegen ist.
• Für Probleme, die von Natur aus eher sequentiell als hierarchisch sind.

Vergleichen wir die rekursive und die iterative Umsetzung desselben Problems, nämlich die Berechnung der Summe der Zahlen von 1 bis num:

Rekursiv:

def sum_recursive(num):
    if num == 1:
        return 1
    else:
        return num + sum_recursive(num - 1)

Iterativ:

def iterative_sum(num):
    total = 0
    for i in range(1, num + 1):
        total += i
    return total

Die iterative Version verwendet eine Schleife, um die Summe zu akkumulieren, während die rekursive Version das Problem in die Addition von n zur Summe der Zahlen von 1 bis num - 1 auflöst. Obwohl beide Lösungen funktionieren, ist die iterative Version bei großen Werten von num effizienter, da sie nicht den Overhead mehrerer Funktionsaufrufe mit sich bringt.

Einige Probleme, die von Natur aus rekursiv sind, können in iterative Lösungen umgewandelt werden, indem ein Stapel oder eine Warteschlange verwendet wird, um die rekursiven Aufrufe zu simulieren. Diese Technik ist besonders nützlich, wenn es um Baum- oder Graphenüberquerungen geht.

Praktische Beispiele für Rekursion in Python

Die Rekursion kann auf eine Vielzahl interessanter Probleme angewendet werden:

1. Berechnung der Fibonacci-Zahlen

Die Fibonacci-Folge ist rekursiv definiert als:

• F(0) = 0
• F(1) = 1
• F(n) = F(n − 1) + F(n − 2)

Dies ergibt die folgende Reihenfolge:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...

Hier ist, wie du es umsetzen kannst:

def compute_fibonacci(num):
    if num <= 0:
        return 0
    elif num == 1:
        return 1
    return compute_fibonacci(num - 1) + compute_fibonacci(num - 2)

print(compute_fibonacci(6))

8

Bei dieser naiven Implementierung werden die Werte jedoch mehrfach neu berechnet. Ein effizienterer Ansatz ist die Memoisierung, bei der bereits berechnete Ergebnisse gespeichert werden (Caching), um redundante Berechnungen zu vermeiden und die Berechnungszeit deutlich zu verkürzen:

def optimized_fibonacci(num, cache=None):
    if cache is None:
        cache = {}
    if num in cache:
        return cache[num]
    if num <= 1:
        return num
    cache[num] = optimized_fibonacci(num - 1, cache) + optimized_fibonacci(num - 2, cache)
    return cache[num]

Dies kann mit dem lru_cache() Dekorator aus dem functools Modul weiter vereinfacht werden:

from functools import lru_cache

@lru_cache(maxsize=None)  # Cache all computed values
def cached_fibonacci(num):
    if num <= 1:
        return num
    return cached_fibonacci(num - 1) + cached_fibonacci(num - 2)

2. Durchlaufen von verschachtelten Datenstrukturen

Rekursion ist auch praktisch für die Arbeit mit verschachtelten Datenstrukturen wie Listen von Listen oder JSON-Objekten. Zum Beispiel das Durchlaufen einer Verzeichnisbaumstruktur oder das rekursive Verflachen einer verschachtelten Liste.

def flatten(nested):
    result = []
    for element in nested:
        if isinstance(element, list):
            result.extend(flatten(element))
        else:
            result.append(element)
    return result

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

print(flatten(nested_structure))  

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

3. Sortieralgorithmen (z. B. Quick Sort oder Merge Sort) 

Sortieralgorithmen wie Quick Sort und Mischsortierung verlassen sich stark auf Rekursion. Bei diesen Algorithmen wird das Problem in kleinere Teilprobleme zerlegt, die rekursiv sortiert werden.

Hier ist eine einfache Implementierung von Quicksort:

def quicksort_algo(array):
    if len(array) <= 1:
        return array
    pivot = array[len(array) // 2]
    lower = [item for item in array if item < pivot]
    equal = [item for item in array if item == pivot]
    greater = [item for item in array if item > pivot]
    return quicksort_algo(lower) + equal + quicksort_algo(greater)

array = [220, 33, 400, 150, 16]

print(quicksort_algo(array))

[16, 33, 150, 220, 400]

Fazit

Rekursion ist ein mächtiges Konzept in Python, das dabei hilft, komplexe Probleme zu lösen, indem es sie in einfachere Teilprobleme zerlegt. Wenn sie richtig eingesetzt wird, führt Rekursion zu sauberem, übersichtlichem Code, der leicht zu verstehen ist. 

Es ist jedoch wichtig, die richtigen Basisfälle zu definieren und auf die Rekursionstiefe zu achten, um häufige Fehler zu vermeiden. 

Obwohl die Rekursion manchmal weniger effizient ist als die Iteration, ist sie ein unschätzbares Werkzeug für die Lösung bestimmter Problemtypen, vor allem bei hierarchischen Daten oder bei Problemen, die sich von Natur aus für rekursive Lösungen eignen.

Wenn du die Rekursion verstehst und anhand von Beispielen wie Faktorzahlen, Fibonacci-Folgen und Sortieralgorithmen übst, bist du gut gerüstet, um die Rekursion in deinen Python-Projekten zu nutzen.

Wenn du dich für fortgeschrittenere Python-Themen interessierst, bei denen du Rekursionen einsetzen kannst, schau dir die folgenden Lernpfade an: Python Programmierung, Datenanalyst in Pythonund Assoziierte/r Datenwissenschaftler/in in Python