DSA Interview Prep · Lekcja

Rekurencja i metoda drzewa rekurencji

Rekurencja i metoda drzewa rekurencji to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.

Rekurencja i stos wywołań

Gdy funkcja wywołuje samą siebie, każde wywołanie dodaje ramkę stosu. Ramki odkładają się aż do osiągnięcia przypadku bazowego, po czym wywołania są rozwijane. Wyobrażenie sobie tego procesu to pierwszy krok do analizy rekurencji.

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

Drzewo rekurencji dla Fibonacciego

Drzewo rekurencji rozwija każde wywołanie na jego wywołania podrzędne. Naiwna implementacja Fibonacciego rozgałęzia się za każdym razem na dwa wywołania, tworząc drzewo o około 2^n węzłach — daje to O(2^n). Zobacz kod.

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

Rozpoznawanie powtarzających się podproblemów

W tym drzewie te same wywołania, takie jak fib(3), powtarzają się w różnych gałęziach. Te nakładające się podproblemy wskazują na możliwość zastosowania memoizacji, która zmniejsza O(2^n) do 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

Drzewo rekurencji sortowania przez scalanie

Drzewo sortowania przez scalanie ma log n poziomów, a na każdym poziomie łączny koszt wynosi O(n) — każdy element jest przetwarzany raz. Pomnożenie tych wartości daje O(n log n). Zobacz kod.

# 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

Twierdzenie Mastera

Twierdzenie Mastera rozwiązuje równanie T(n) = a*T(n/b) + O(n^d) w trzech przypadkach. Dla sortowania przez scalanie (a=2, b=2, d=1) daje wynik O(n log n). Warto zapamiętać te trzy przypadki przed egzaminem.

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

Rysowanie drzew rekurencji krok po kroku

Aby narysować drzewo rekurencji: umieść T(n) na górze, rozwiń każde wywołanie, zsumuj pracę na każdym poziomie, a następnie pomnóż ją przez liczbę poziomów. Warto ćwiczyć, aż stanie się to automatyczne.

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

Rekurencja wykładnicza: podzbiory

Generowanie wszystkich podzbiorów ma złożoność O(2^n) — istnieje dokładnie 2^n podzbiorów, więc nie da się uzyskać lepszego wyniku. Każdy element albo należy do podzbioru, albo nie, co tworzy binarne drzewo wyborów. Zobacz kod.

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)

Rekurencja ogonowa i optymalizacja

Rekurencja ogonowa występuje wtedy, gdy wywołanie rekurencyjne jest ostatnim krokiem. Niektóre języki ponownie wykorzystują tę samą ramkę stosu, ale Python tego nie robi — dlatego głęboka rekurencja nadal prowadzi do przepełnienia stosu. Zamiast tego należy użyć pętli.

# 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

Złożoność pamięciowa rekurencji

Każde wywołanie rekurencyjne przechowuje ramkę, więc rekurencja wymaga O(głębokości) pamięci. Rekurencja liniowa ma złożoność O(n), a przechodzenie DFS zrównoważonego drzewa — O(log n). Zbyt głęboka rekurencja kończy się błędem 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

Drzewo rekurencji sortowania szybkiego

Sortowanie szybkie ma złożoność O(n log n) przy dobrym pivocie, ale zły pivot dla posortowanych danych wejściowych obniża wydajność do O(n^2). Dlatego losowanie pivota ma znaczenie. Zobacz kod.

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

Funkcja potęgowania: rekurencja O(log n)

Naiwne obliczenie x^n wymaga O(n) mnożeń, ale podnoszenie do kwadratu zmniejsza pracę o połowę w każdym kroku: x^n = (x^(n/2))^2. Daje to elegancką złożoność O(log n) — dzielenie przez połowę w praktyce. Zobacz kod.

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

Szybki test

Szybki test — sprawdźmy, czego nauczyła metoda drzewa rekurencji. Proszę spokojnie poświęcić chwilę na jedno pytanie. 🌳

Podsumowanie lekcji

Podsumowanie: drzewo rekurencji pokazuje całkowity koszt pracy, twierdzenie Mastera rozwiązuje rekurencje typu „dziel i zwyciężaj”, a rekurencja wymaga O(głębokości) pamięci stosu.

Często zadawane pytania

Czy lekcja „Rekurencja i metoda drzewa rekurencji” jest bezpłatna?

Tak — pełny tekst „Rekurencja i metoda drzewa rekurencji” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.

Co nauczysz się w „Rekurencja i metoda drzewa rekurencji”?

Prześledzą Państwo wywołania rekurencyjne na drzewach, zastosują twierdzenie Mastera i wyprowadzą złożoność czasową dla sortowania przez scalanie, silni oraz wariantów ciągu Fibonacciego. Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?

Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.

Ile czasu zajmuje lekcja „Rekurencja i metoda drzewa rekurencji”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?

Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

← Powrót do DSA Interview Prep