Рекурсия и метод дерева рекурсии
Представляйте рекурсивные вызовы в виде дерева, применяйте основную теорему и выводите временную сложность сортировки слиянием, вычисления факториала и вариантов алгоритма Фибоначчи
«Рекурсия и метод дерева рекурсии» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding 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) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Рекурсия и метод дерева рекурсии»?
Представляйте рекурсивные вызовы в виде дерева, применяйте основную теорему и выводите временную сложность сортировки слиянием, вычисления факториала и вариантов алгоритма Фибоначчи Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Рекурсия и метод дерева рекурсии»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Нотация Big-O с нуля
- Анализ циклов и вложенных циклов
- Рекурсия и метод дерева рекурсии
- Пространственная сложность и компромиссы