Rekursion und die Rekursionsbaum-Methode
Verfolgen Sie rekursive Aufrufe in Bäumen, wenden Sie den Master-Theorem an und leiten Sie die Zeitkomplexität für Merge Sort, Fakultät und Fibonacci-Varianten her.
Rekursion und die Rekursionsbaum-Methode ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Rekursion und der Aufruf-Stack
Wenn eine Funktion sich selbst aufruft, fügt jeder Aufruf einen Stack-Frame hinzu. Diese stapeln sich, bis ein Basisfall erreicht ist und die Aufrufe abgewickelt werden. Sich das vorzustellen, ist der erste Schritt zur Analyse von Rekursion.
def factorial(n):
if n == 0: # base case
return 1
return n * factorial(n - 1) # recursive call
# Call chain: factorial(4)
# 4 * factorial(3)
# 3 * factorial(2)
# 2 * factorial(1)
# 1 * factorial(0) -> 1
# Unwinds: 1, 2, 6, 24
print(factorial(5)) # 120Der Rekursionsbaum für Fibonacci
Ein Rekursionsbaum erweitert jeden Aufruf um seine Unteraufrufe. Naives Fibonacci teilt sich jedes Mal in zwei Aufrufe auf und erzeugt einen Baum mit ungefähr 2^n Knoten — das ist O(2^n). Sehen Sie sich den Code an.
call_count = [0]
def fib_naive(n):
call_count[0] += 1
if n <= 1:
return n
return fib_naive(n-1) + fib_naive(n-2)
for n in [5, 10, 15, 20]:
call_count[0] = 0
result = fib_naive(n)
print(f'fib({n})={result}, calls={call_count[0]}')
# Calls roughly double each time n increases by 1Wiederholte Teilprobleme erkennen
In diesem Baum werden dieselben Aufrufe wie fib(3) über mehrere Zweige hinweg wiederholt. Diese überlappenden Teilprobleme sind ein Hinweis auf Memoization, die O(2^n) auf O(n) reduziert.
# Memoised: each unique sub-problem computed once
def fib_memo(n, memo={}):
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
call_count2 = [0]
def fib_counted(n, memo={}):
call_count2[0] += 1
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib_counted(n-1, memo) + fib_counted(n-2, memo)
return memo[n]
fib_counted(20)
print(f'calls with memo: {call_count2[0]}') # only 21Der Rekursionsbaum von Merge Sort
Der Baum von Merge Sort hat log n Ebenen, und auf jeder Ebene fällt insgesamt Arbeit von O(n) an — jedes Element wird einmal verarbeitet. Multipliziert man beides, ergibt sich O(n log n). Sehen Sie sich den Code an.
# Merge sort: at each level, n total elements are merged
# Level 0: 1 merge of n elements -> n work
# Level 1: 2 merges of n/2 each -> n work
# Level 2: 4 merges of n/4 each -> n work
# ...log(n) levels...
# Total: n * log(n)
# Verify with operation counter:
def merge_sort_counted(arr):
ops = [0]
def _sort(a):
if len(a) <= 1: return a
m = len(a) // 2
l, r = _sort(a[:m]), _sort(a[m:])
result, i, j = [], 0, 0
while i < len(l) and j < len(r):
ops[0] += 1
if l[i] <= r[j]: result.append(l[i]); i+=1
else: result.append(r[j]); j+=1
return result + l[i:] + r[j:]
return _sort(arr), ops[0]
_, c = merge_sort_counted(list(range(64, 0, -1)))
print(f'Merge ops: {c}') # ~384 ~ 64*log2(64)=384Das Master-Theorem
Das Master-Theorem löst T(n) = a*T(n/b) + O(n^d) mit drei Fällen. Für Merge Sort (a=2, b=2, d=1) ergibt sich O(n log n). Prägen Sie sich die drei Fälle für die Prüfung ein.
# Merge sort: T(n) = 2*T(n/2) + O(n)
# a=2, b=2, d=1, log_b(a)=log2(2)=1=d => O(n log n)
# Binary search: T(n) = 1*T(n/2) + O(1)
# a=1, b=2, d=0, log2(1)=0=d => O(log n)
# Strassen matrix mult: T(n) = 7*T(n/2) + O(n^2)
# a=7, b=2, d=2, log2(7)~2.81 > 2 => O(n^log2(7)) ~ O(n^2.81)
import math
print('log2(7) =', math.log2(7)) # 2.807...Rekursionsbäume zeichnen: Schritt für Schritt
Um einen Rekursionsbaum zu zeichnen: Schreiben Sie oben T(n) hin, erweitern Sie jeden Aufruf, summieren Sie die Arbeit auf jeder Ebene und multiplizieren Sie anschließend mit der Anzahl der Ebenen. Üben Sie, bis es automatisch geht.
# Factorial: T(n) = T(n-1) + O(1)
# Tree is a chain: n levels, O(1) each -> O(n)
# Fibonacci: T(n) = T(n-1) + T(n-2) + O(1)
# Binary tree of depth n, ~2^n nodes -> O(2^n)
# Merge sort: T(n) = 2*T(n/2) + O(n)
# Log levels, n work each -> O(n log n)
def count_recursive_calls(n, results=[]):
if n <= 1:
results.append(n)
return n
return count_recursive_calls(n-1, results) + count_recursive_calls(n-2, results)
results = []
count_recursive_calls(8, results)
print(f'fib(8) leaf calls: {len(results)}')Exponentielle Rekursion: Teilmengen
Alle Teilmengen zu erzeugen ist O(2^n) — es gibt genau 2^n davon, daher können Sie es nicht schneller machen. Jedes Element ist entweder enthalten oder nicht enthalten, wodurch ein binärer Entscheidungsbaum entsteht. Sehen Sie sich den Code an.
def subsets(nums):
result = []
def backtrack(start, current):
result.append(list(current)) # O(n) copy
for i in range(start, len(nums)):
current.append(nums[i])
backtrack(i + 1, current)
current.pop()
backtrack(0, [])
return result
nums = [1, 2, 3]
ss = subsets(nums)
print(len(ss)) # 8 = 2^3
print(ss)Endrekursion und Optimierung
Endrekursion liegt vor, wenn der rekursive Aufruf der allerletzte Schritt ist. Manche Sprachen verwenden dafür denselben Frame wieder, Python jedoch nicht — tiefe Rekursionen führen daher weiterhin zu einem Überlauf. Verwenden Sie stattdessen eine Schleife.
# Tail-recursive factorial (accumulator pattern)
def fact_tail(n, acc=1):
if n == 0:
return acc
return fact_tail(n - 1, n * acc) # tail call
# Python does NOT TCO, so this overflows for large n
# Instead, convert to iterative:
def fact_iter(n):
acc = 1
while n > 0:
acc *= n
n -= 1
return acc
print(fact_tail(10)) # 3628800
print(fact_iter(10)) # 3628800Speicherkomplexität von Rekursion
Jeder rekursive Aufruf hält einen Frame, daher benötigt Rekursion Speicher von O(depth). Lineare Rekursion benötigt O(n); die Tiefensuche in einem balancierten Baum O(log n). Gehen Sie zu tief, erhalten Sie einen RecursionError.
import sys
print(sys.getrecursionlimit()) # default 1000
# Increase limit for deep problems
sys.setrecursionlimit(10000)
# Track max depth manually
def max_depth_tracker(n, depth=0, max_seen=[0]):
max_seen[0] = max(max_seen[0], depth)
if n <= 0:
return
max_depth_tracker(n - 1, depth + 1, max_seen)
return max_seen[0]
print(max_depth_tracker(50)) # 50 => O(n) stack framesRekursionsbaum für Quick Sort
Quick Sort ist bei einem guten Pivot O(n log n), verschlechtert sich bei einem schlechten Pivot und sortierter Eingabe jedoch auf O(n^2). Deshalb ist es wichtig, den Pivot zufällig zu wählen. Sehen Sie sich den Code an.
import random
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = random.choice(arr) # randomised -> O(n log n) expected
less = [x for x in arr if x < pivot]
equal = [x for x in arr if x == pivot]
greater = [x for x in arr if x > pivot]
return quick_sort(less) + equal + quick_sort(greater)
print(quick_sort([3, 6, 8, 10, 1, 2, 1])) # sortedPotenzfunktion: Rekursion mit log n
Naives x^n benötigt O(n) Multiplikationen, aber durch Quadrieren wird die Arbeit in jedem Schritt halbiert: x^n = (x^(n/2))^2. Das ergibt ein klares O(log n) — Halbieren in der Praxis. Sehen Sie sich den Code an.
def fast_pow(x, n):
if n == 0: return 1
if n < 0: return 1 / fast_pow(x, -n)
if n % 2 == 0:
half = fast_pow(x, n // 2)
return half * half # O(log n) calls
return x * fast_pow(x, n - 1)
print(fast_pow(2, 10)) # 1024
print(fast_pow(3, 5)) # 243
# Only log2(10)=3-4 recursive calls for n=10Schnelltest
Schnelltest — zeigen Sie, was Ihnen die Methode mit dem Rekursionsbaum vermittelt hat. Eine Frage, lassen Sie sich Zeit. 🌳
Zusammenfassung der Lektion
Zusammenfassung: Ein Rekursionsbaum macht die gesamte Arbeit sichtbar, das Master-Theorem löst Rekurrenzen nach dem Teile-und-herrsche-Prinzip, und Rekursion benötigt O(depth) Stack-Speicher.
Häufig gestellte Fragen
Ist die Lektion „Rekursion und die Rekursionsbaum-Methode“ kostenlos?
Ja — der vollständige Text von „Rekursion und die Rekursionsbaum-Methode“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Rekursion und die Rekursionsbaum-Methode“?
Verfolgen Sie rekursive Aufrufe in Bäumen, wenden Sie den Master-Theorem an und leiten Sie die Zeitkomplexität für Merge Sort, Fakultät und Fibonacci-Varianten her. Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Rekursion und die Rekursionsbaum-Methode“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Big-O-Notation von Grund auf
- Schleifen und verschachtelte Schleifen analysieren
- Rekursion und die Rekursionsbaum-Methode
- Platzkomplexität und Abwägungen