DSA Interview Prep · Урок

Рекурсия и метод дерева рекурсии

«Рекурсия и метод дерева рекурсии» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.

Рекурсия и стек вызовов

Когда функция вызывает саму себя, каждый вызов добавляет кадр стека, и кадры накапливаются, пока не будет достигнут базовый случай, после чего вызовы завершаются в обратном порядке. Представить этот процесс — первый шаг к анализу рекурсии.

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

Дерево рекурсии для чисел Фибоначчи

Дерево рекурсии раскрывает каждый вызов в его подвызываемые функции. Наивное вычисление чисел Фибоначчи каждый раз разделяется на два вызова, образуя дерево примерно из 2^n узлов — это O(2^n). Посмотрите код.

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

Распознавание повторяющихся подзадач

В этом дереве одни и те же вызовы, например вычисление третьего числа, повторяются в разных ветвях. Такие перекрывающиеся подзадачи указывают на необходимость мемоизации, которая сокращает O(2^n) до 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

Дерево рекурсии сортировки слиянием

Дерево сортировки слиянием имеет log n уровней, и на каждом уровне суммарно выполняется O(n) работы: каждый элемент обрабатывается один раз. Перемножив эти величины, получаем O(n log n). Посмотрите код.

# 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

Теорема мастера

Теорема мастера решает рекуррентные соотношения T(n) = a*T(n/b) + O(n^d) с помощью трёх случаев. Для сортировки слиянием (a=2, b=2, d=1) она даёт O(n log n). Запомните эти три случая к экзамену.

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

Построение деревьев рекурсии: пошаговое руководство

Чтобы построить дерево рекурсии: поместите T(n) наверх, раскройте каждый вызов, просуммируйте работу на каждом уровне, а затем умножьте её на количество уровней. Практикуйтесь, пока это не станет автоматическим.

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

Экспоненциальная рекурсия: subsets

Генерация всех subsets имеет сложность O(2^n): их ровно 2^n, поэтому улучшить этот показатель невозможно. Каждый элемент либо включается, либо не включается, образуя двоичное дерево вариантов. Посмотрите код.

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)

Хвостовая рекурсия и оптимизация

Хвостовая рекурсия — это рекурсия, в которой рекурсивный вызов является самым последним шагом. Некоторые языки переиспользуют для него кадр стека, но Python так не делает, поэтому глубокая рекурсия всё равно приводит к переполнению. Используйте цикл.

# 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

Пространственная сложность рекурсии

Каждый рекурсивный вызов хранит кадр стека, поэтому рекурсия требует O(глубины) памяти. Линейная рекурсия имеет сложность O(n), а поиск в сбалансированном дереве с помощью DFS — O(log n). Зайдите слишком глубоко — и получите 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

Дерево рекурсии быстрой сортировки

Быстрая сортировка имеет сложность O(n log n) при удачном опорном элементе, но при неудачном опорном элементе на отсортированных входных данных её сложность ухудшается до O(n^2). Поэтому важно выбирать опорный элемент случайным образом. Посмотрите код.

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

Возведение в степень: рекурсия O(log n)

Наивное вычисление x^n требует O(n) умножений, но возведение в квадрат сокращает работу вдвое на каждом шаге: x^n = (x^(n/2))^2. Так получается чистая сложность O(log n) — деление пополам в действии. Посмотрите код.

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

Быстрая проверка

Быстрая проверка — покажите, чему научил Вас метод дерева рекурсии. Один вопрос, не спешите. 🌳

Итоги урока

Итоги: дерево рекурсии показывает общий объём работы, теорема мастера решает рекуррентные соотношения «разделяй и властвуй», а рекурсия требует O(глубины) памяти стека.

Часто задаваемые вопросы

Урок «Рекурсия и метод дерева рекурсии» бесплатный?

Да — полный текст урока «Рекурсия и метод дерева рекурсии» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Рекурсия и метод дерева рекурсии»?

Представляйте рекурсивные вызовы в виде дерева, применяйте основную теорему и выводите временную сложность сортировки слиянием, вычисления факториала и вариантов алгоритма Фибоначчи Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать DSA Interview Prep?

Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.

Сколько времени занимает урок «Рекурсия и метод дерева рекурсии»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке DSA Interview Prep?

Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

Нотация Big-O с нуля
Анализ циклов и вложенных циклов
Рекурсия и метод дерева рекурсии
Пространственная сложность и компромиссы

← Назад к DSA Interview Prep