Rekursion und Backtracking
Rekursionsgrundlagen
Eine rekursive Funktion ruft sich selbst mit einer kleineren Version des Problems auf, bis sie auf einen Basisfall trifft, der die Kette stoppt.
Jede Rekursion benötigt zwei Dinge:
- Basisfall – die einfachste Eingabe, bei der Sie direkt zurückkehren.
- Rekursiver Fall – brechen Sie das Problem auf und rufen Sie sich selbst an.
def factorial(n):
if n <= 1: # base case
return 1
return n * factorial(n - 1) # recursive case
Der Aufrufstapel – visualisiert
Jeder rekursive Aufruf schiebt einen Frame auf den Aufrufstapel. Wenn der Basisfall zurückkehrt, werden die Frames in umgekehrter Reihenfolge angezeigt.
factorial(4)
→ factorial(3)
→ factorial(2)
→ factorial(1) → returns 1
← returns 2
← returns 6
← returns 24
Wenn kein Basisfall vorliegt, läuft der Stapel über. Das Standard-Rekursionslimit von Python beträgt 1.000 Frames.
Fibonacci – Die klassische Falle
Das naive rekursive Fibonacci ist O(2ⁿ), weil es dieselben Teilprobleme neu berechnet. Durch Auswendiglernen wird dies in O(n) Zeit und Raum behoben.
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
Backtracking – Alles ausprobieren und dann rückgängig machen
Backtracking ist eine Rekursion mit einer Wendung: Sie treffen eine Wahl, rekursieren und machen dann die Wahl rückgängig, bevor Sie die nächste Option ausprobieren. Stellen Sie sich vor, Sie erkunden ein Labyrinth: Gehen Sie vorwärts, geraten Sie in eine Sackgasse, gehen Sie zurück, versuchen Sie den nächsten Weg.
Die Backtracking-Vorlage
def backtrack(state, choices):
if is_solution(state):
result.append(state.copy())
return
for choice in choices:
if is_valid(choice):
state.add(choice) # choose
backtrack(state, ...) # explore
state.remove(choice) # un-choose
Diskussion
Anmelden an der Diskussion teilnehmen