Forberedelse til kodeinterviews · Lektion

Rekursion og rekursionstræmetoden

Følg rekursive kald i træer, anvend Master Theorem, og udled tidskompleksiteten for merge sort, fakultet og Fibonacci-varianter.

Lektion 3 af 413 trin

Rekursion og rekursionstræmetoden er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.

Rekursion og kaldestakken

Når en funktion kalder sig selv, tilføjer hvert kald en stakramme, som hober sig op, indtil et basistilfælde nås, hvorefter rammerne afvikles. At forestille sig dette er første trin i analysen af 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))  # 120

Rekursionstræet for Fibonacci

Et rekursionstræ udvider hvert kald til dets underkald. Naiv Fibonacci deler sig i to ved hvert kald, hvilket giver et træ med omkring 2^n noder — det er O(2^n). Se koden.

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 1

Genkend gentagne delproblemer

I træet gentages de samme kald, som fib(3), på tværs af grenene. Disse overlappende delproblemer er et tegn på, at du skal bruge memoisering, som reducerer O(2^n) til O(n).

# 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 21

Rekursionstræet for mergesort

Mergesorts træ har log n niveauer, og hvert niveau udfører samlet O(n) arbejde — hvert element berøres én gang. Gang dem sammen for at få O(n log n). Se koden.

# 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)=384

Mastersætningen

Mastersætningen løser T(n) = a*T(n/b) + O(n^d) med tre tilfælde. For mergesort (a=2, b=2, d=1) giver den O(n log n). Lær de tre tilfælde udenad til eksamen.

# 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...

Tegn rekursionstræer: trin for trin

Sådan tegner du et rekursionstræ: Anbring T(n) øverst, udvid hvert kald, læg arbejdet på hvert niveau sammen, og gang derefter med antallet af niveauer. Øv dig, indtil det sker automatisk.

# 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)}')

Eksponentiel rekursion: delmængder

At generere alle delmængder er O(2^n) — der findes præcis 2^n af dem, så det kan ikke gøres hurtigere. Hvert element er enten med eller ikke med, hvilket opbygger et binært valgtræ. Se koden.

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)

Halerekursion og optimering

Halerekursion er, når det rekursive kald er det allersidste trin. Nogle sprog genbruger stakrammen til det, men Python gør det ikke — så dybe rekursioner giver stadig stakoverløb. Brug en løkke i stedet.

# 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))  # 3628800

Pladskompleksitet ved rekursion

Hvert rekursivt kald holder en ramme, så rekursion bruger plads svarende til dybden. Lineær rekursion er O(n); DFS på et balanceret træ er O(log n). Går du for dybt, rammer du 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 frames

Rekursionstræet for quicksort

Quicksort er O(n log n) med et godt pivotelement, men et dårligt pivotelement på sorteret inddata forringer den til O(n^2). Derfor er det vigtigt at randomisere pivotelementet. Se koden.

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]))  # sorted

Potensfunktion: Rekursion i log n

Naiv x^n kræver O(n) multiplikationer, men kvadrering halverer arbejdet ved hvert trin: x^n = (x^(n/2))^2. Det giver en ren O(log n) — halvering i praksis. Se koden.

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=10

Hurtigt tjek

Hurtigt tjek — vis, hvad metoden med rekursionstræer lærte dig. Ét spørgsmål, tag dig god tid. 🌳

Besvar den i den interaktive lektion

Opsamling af lektionen

Opsamling: Et rekursionstræ viser det samlede arbejde, mastersætningen løser rekurrenser for del-og-hersk-algoritmer, og rekursion bruger stakplads svarende til O(dybde).

Gratis at komme i gang

Lær Forberedelse til kodeinterviews med en AI-underviser — gratis

Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.

Kurser: 90
Lektioner: 360

Start gratis Se hele kurset

Ofte stillede spørgsmål

Er lektionen “Rekursion og rekursionstræmetoden” gratis?

Ja — hele teksten til “Rekursion og rekursionstræmetoden” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.

Hvad lærer jeg i “Rekursion og rekursionstræmetoden”?

Følg rekursive kald i træer, anvend Master Theorem, og udled tidskompleksiteten for merge sort, fakultet og Fibonacci-varianter. Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.

Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?

Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 3 af 4.

Hvor lang tid tager lektionen “Rekursion og rekursionstræmetoden”?

De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.

Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?

Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.

Alle lektioner i dette kursus

← Tilbage til Forberedelse til kodeinterviews