DSA Interview Prep · Lektion

Rekursion och metoden med rekursionsträd

Följ rekursiva anrop i träd, tillämpa Master Theorem och härled tidskomplexiteten för merge sort, fakultet och varianter av Fibonacci.

Lektion 3 av 413 steg

Rekursion och metoden med rekursionsträd är en gratis lektion i DSA Interview Prep på CoddyKit. Detta är lektion 3 av 4. Du kan läsa vilka 3 lektioner som helst i den här lärvägen kostnadsfritt i sin helhet – därefter låser CoddyKit PRO upp alla lektioner, plus praktisk övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Den ingår i lärvägen för DSA Interview Prep, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.

Rekursion och anropsstacken

När en funktion anropar sig själv lägger varje anrop till en stackram, som staplas tills ett basfall nås och ramarna sedan tas bort. Att föreställa sig detta är det första steget i att analysera 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ädet för Fibonacci

Ett rekursionsträd expanderar varje anrop till dess underanrop. Naiv Fibonacci delar sig i två i varje steg och bildar ett träd med omkring 2^n noder — det är 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

Identifiera upprepade delproblem

I det trädet upprepas samma anrop, som fib(3), längs flera grenar. Dessa överlappande delproblem visar att memoisering kan användas, vilket minskar O(2^n) till 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ädet för mergesortering

Mergesorteringens träd har log n nivåer, och varje nivå utför totalt O(n) arbete — varje element berörs en gång. Multiplicera dem för att 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

Masterteoremet

Masterteoremet löser T(n) = a*T(n/b) + O(n^d) med tre fall. För mergesortering (a=2, b=2, d=1) ger det O(n log n). Lär dig de tre fallen utantill inför tentan.

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

Rita rekursionsträd steg för steg

Så här ritar du ett rekursionsträd: placera T(n) högst upp, expandera varje anrop, summera arbetet på varje nivå och multiplicera sedan med antalet nivåer. Öva tills det går automatiskt.

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

Exponentiell rekursion: delmängder

Att generera alla delmängder har komplexiteten O(2^n) — det finns exakt 2^n delmängder, så det går inte att göra snabbare. Varje element är antingen med eller inte med, vilket bygger ett binärt valträd. 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)

Svansrekursion och optimering

Svansrekursion innebär att det rekursiva anropet är det allra sista steget. Vissa språk återanvänder stackramen för detta, men Python gör inte det — djup rekursion leder därför fortfarande till stack overflow. Använd en loop i stället.

# 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

Minneskomplexitet vid rekursion

Varje rekursivt anrop innehåller en stackram, så rekursion använder O(djup) minne. Linjär rekursion är O(n); DFS i ett balanserat träd är O(log n). Går du för djupt får 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ädet för quicksort

Quicksort har komplexiteten O(n log n) med ett bra pivotval, men ett dåligt pivotval för sorterad indata försämrar den till O(n^2). Därför är det viktigt att välja pivot slumpmässigt. 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 på log n

Naiva x^n kräver O(n) multiplikationer, men kvadrering halverar arbetet i varje steg: x^n = (x^(n/2))^2. Det ger en tydlig O(log n) — halvering i praktiken. 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

Snabbtest

Snabbtest — visa vad metoden med rekursionsträd har lärt dig. En fråga, ta den tid du behöver. 🌳

Besvara frågan i den interaktiva lektionen

Lektionssammanfattning

Sammanfattning: ett rekursionsträd visar det totala arbetet, Masterteoremet löser rekurrenser för divide-and-conquer, och rekursion använder O(djup) stackminne.

Gratis att börja

Lär dig Python med en AI-lärare – gratis

Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.

Kurser: 30
Lektioner: 120

Börja lära dig gratis Visa hela kursen

Vanliga frågor

Är lektionen ”Rekursion och metoden med rekursionsträd” gratis?

Ja – du kan läsa vilka 3 lektioner som helst i lärvägen DSA Interview Prep, inklusive ”Rekursion och metoden med rekursionsträd”, kostnadsfritt i sin helhet här på webben. Därefter låser CoddyKit PRO upp alla lektioner, plus interaktiv övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.

Vad lär jag mig i ”Rekursion och metoden med rekursionsträd”?

Följ rekursiva anrop i träd, tillämpa Master Theorem och härled tidskomplexiteten för merge sort, fakultet och varianter av Fibonacci. Ni övar på DSA Interview Prep med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.

Behöver jag någon erfarenhet för att börja lära mig DSA Interview Prep?

Du behöver inga förkunskaper. Utbildningen i DSA Interview Prep på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 3 av 4.

Hur lång tid tar lektionen ”Rekursion och metoden med rekursionsträd”?

De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.

Kan jag skriva och köra kod i den här DSA Interview Prep-lektionen?

Ja. Varje DSA Interview Prep-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.

Alla lektioner i den här kursen

Big-O-notation från grunden
Analysera loopar och nästlade loopar
Rekursion och metoden med rekursionsträd
Rymdkomplexitet och avvägningar

← Tillbaka till DSA Interview Prep