Rekursion ist, wenn eine Funktion sich selbst aufruft, um eine kleinere Version desselben Problems zu lösen. Jede Rekursion benötigt einen Basisfall (base case), der sie stoppt, und einen rekursiven Fall (recursive case), der sich dem Basisfall annähert.
Teilen Sie ein Problem in kleinere identische Unterproblem auf. Jeder Aufruf legt einen Frame auf dem Call Stack ab; Rückgaben entfernen sie wieder.
def factorial(n):
if n <= 1: # base case: stop recursing
return 1
return n * factorial(n - 1) # recursive case: smaller problem
factorial(4) # 4 * 3 * 2 * 1 -> 24
factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * 3 * 2 * 1 = 24
Hier O(n) Zeit und O(n) Stack-Speicher (ein Frame pro Aufruf).
Rekursion drückt natürlicherweise selbstähnliche Probleme aus — Bäume, Graphen, Divide and Conquer — viel sauberer als Schleifen.
Sie ist das gedankliche Modell hinter Merge Sort, Backtracking und dynamischer Programmierung.
Das Verständnis des Call Stack macht Sie auch besser beim Debuggen und beim Denken über Speicher.
Eine Sammlung von IT-Interviewfragen mit ausführlichen Antworten — vom Junior bis zum Senior.
Spenden