С возвращением, неутомимые исследователи Python! 🚀 В предыдущих частях мы заложили фундамент (Часть 1: Встроенный Арсенал) и расширили инструментарий специализированными структурами вроде deque и концептуально важными связанными списками (Часть 2: Deque и Linked Lists). Мы много говорили о том, как хранить данные. Теперь пришло время сместить фокус на то, как решать задачи, используя продвинутые техники программирования.
def factorial_recursive(n):
"""Вычисляет факториал n с помощью рекурсии."""
# Добавим выводы, чтобы видеть процесс
print(f"Вычисляем factorial_recursive({n})...")
# Сначала проверим корректность ввода
if not isinstance(n, int) or n < 0:
raise ValueError("Факториал определен только для целых неотрицательных чисел")
# 1. Базовый случай
if n == 0 or n == 1:
print(f"Базовый случай для n={n}, возвращаем 1.")
return 1
# 2. Рекурсивный шаг
else:
print(f"Рекурсивный шаг для n={n}. Вызываем factorial_recursive({n-1}).")
# Вызываем себя же для n-1
result_n_minus_1 = factorial_recursive(n - 1)
# Комбинируем результат
result = n * result_n_minus_1
print(f"Вернулись к n={n}. Результат {n} * factorial({n-1}) = {result}")
return result
# --- Пример вызова ---
try:
target_n = 4
print(f"\n--- Запускаем вычисление {target_n}! ---")
final_result = factorial_recursive(target_n)
print(f"--- Готово ---")
print(f"\nИтоговый факториал {target_n}! = {final_result}")
except ValueError as e:
print(f"Ошибка: {e}")
# Попробуем некорректный ввод
try:
print("\n--- Пробуем factorial_recursive(-1) ---")
factorial_recursive(-1)
except ValueError as e:
print(f"Ожидаемая ошибка: {e}")--- Запускаем вычисление 4! ---
Вычисляем factorial_recursive(4)...
Рекурсивный шаг для n=4. Вызываем factorial_recursive(3).
Вычисляем factorial_recursive(3)...
Рекурсивный шаг для n=3. Вызываем factorial_recursive(2).
Вычисляем factorial_recursive(2)...
Рекурсивный шаг для n=2. Вызываем factorial_recursive(1).
Вычисляем factorial_recursive(1)...
Базовый случай для n=1, возвращаем 1.
Вернулись к n=2. Результат 2 * factorial(1) = 2
Вернулись к n=3. Результат 3 * factorial(2) = 6
Вернулись к n=4. Результат 4 * factorial(3) = 24
--- Готово ---
Итоговый факториал 4! = 24
--- Пробуем factorial_recursive(-1) ---
Вычисляем factorial_recursive(-1)...
Ожидаемая ошибка: Факториал определен только для целых неотрицательных чисел👍 Плюсы рекурсии
👎 Минусы рекурсии (особенно в Python)
Важное замечание: Для многих простых задач, которые часто приводят как примеры рекурсии (вроде факториала или чисел Фибоначчи), итеративное решение в Python почти всегда будет более предпочтительным. Оно быстрее, не рискует переполнением стека и часто не сильно сложнее в написании. Рекурсию для таких задач стоит рассматривать скорее как учебный пример.
# КРАЙНЕ НЕЭФФЕКТИВНАЯ наивная рекурсия для Фибоначчи
def fib_naive(n):
# print(f"Вычисляем fib_naive({n})") # Раскомментируйте, чтобы увидеть лавину вызовов
if n < 0:
raise ValueError("N должно быть >= 0")
if n <= 1:
return n
else:
# Вот здесь проблема: fib(n-1) и fib(n-2) будут многократно
# вызывать вычисление ОДНИХ И ТЕХ ЖЕ меньших значений fib(k)
return fib_naive(n - 1) + fib_naive(n - 2)
# --- Попробуем вызвать (даже для небольшого n) ---
import time
n_val = 40 # Уже достаточно, чтобы увидеть тормоза
print(f"Вычисляем fib({n_val}) наивной рекурсией (может занять время)...")
start_time = time.perf_counter()
try:
result_naive = fib_naive(n_val)
end_time = time.perf_counter()
print(f"fib({n_val}) = {result_naive}")
print(f"Время выполнения: {end_time - start_time:.6f} сек")
except ValueError as e:
print(e)
except RecursionError:
print("Ошибка: Достигнута максимальная глубина рекурсии!") fib(5)
/ \
fib(4) fib(3) <-- fib(3) вызывается 1 раз здесь
/ \ / \
fib(3) fib(2) fib(2) fib(1) <-- fib(3) вызывается еще 1 раз, fib(2) - 2 раза
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0) <-- fib(2) вызывается еще раз...
/ \
fib(1) fib(0)# Кеш для хранения уже вычисленных значений fib(k)
# Используем словарь, так как ключи (n) могут быть любыми (хотя здесь целые)
memo_fib = {}
def fib_memo(n):
"""Вычисляет числа Фибоначчи с использованием мемоизации (явный кеш)."""
# print(f"Попытка вычислить fib_memo({n})")
if n < 0:
raise ValueError("N должно быть >= 0")
# 1. Проверка кеша
if n in memo_fib:
# print(f" Нашли fib({n})={memo_fib[n]} в кеше!")
return memo_fib[n]
# 2. Базовый случай
if n <= 1:
result = n
# 3. Рекурсивный шаг (если не в кеше и не базовый случай)
else:
# print(f" Вычисляем fib({n}) = fib({n-1}) + fib({n-2})")
result = fib_memo(n - 1) + fib_memo(n - 2)
# 4. Сохранение в кеш ПЕРЕД возвратом
# print(f" Сохраняем fib({n}) = {result} в кеш")
memo_fib[n] = result
# 5. Возврат
return result
# --- Вызов ---
import time
n_val = 40 # То же значение, что было медленным раньше
print(f"\n--- Вычисляем fib({n_val}) с мемоизацией ---")
start_time = time.perf_counter()
result_memo = fib_memo(n_val)
end_time = time.perf_counter()
print(f"fib({n_val}) = {result_memo}")
print(f"Время выполнения: {end_time - start_time:.6f} сек") # Теперь это МГНОВЕННО!
# Посмотрим на кеш после вычислений (для интереса)
# print(f"\nСодержимое кеша memo_fib после вычисления fib({n_val}):")
# print(memo_fib)
# Повторный вызов будет еще быстрее, т.к. все уже в кеше
print(f"\n--- Повторный вызов fib({n_val}) ---")
start_time = time.perf_counter()
result_memo_again = fib_memo(n_val)
end_time = time.perf_counter()
print(f"fib({n_val}) = {result_memo_again}")
print(f"Время выполнения повторного вызова: {end_time - start_time:.6f} сек")import functools
import time
# import sys
# При необходимости можно увеличить лимит рекурсии, но кеш часто помогает
# sys.setrecursionlimit(2000)
# Используем декоратор @cache (для Python 3.9+)
# или @functools.lru_cache(maxsize=None) для более старых версий
@functools.cache
def fib_cached(n):
"""Вычисляет Фибоначчи с автоматической мемоизацией через @cache."""
# print(f"Вызов fib_cached({n})") # Можно раскомментировать для отладки
if n < 0:
raise ValueError("N должно быть >= 0")
if n <= 1:
return n
else:
return fib_cached(n - 1) + fib_cached(n - 2)
# --- Вызов ---
n_val_cache = 100 # Теперь можно брать n побольше!
print(f"\n--- Вычисляем fib({n_val_cache}) с @cache ---")
start_time = time.perf_counter()
result_cache = fib_cached(n_val_cache)
end_time = time.perf_counter()
print(f"fib({n_val_cache}) = {result_cache}")
print(f"Время выполнения: {end_time - start_time:.6f} сек")
# Декоратор предоставляет удобный способ посмотреть статистику кеша
print(f"Статистика кеша fib_cached: {fib_cached.cache_info()}")
# Вывод может быть: CacheInfo(hits=98, misses=101, maxsize=None, currsize=101)
# hits - сколько раз результат взят из кеша
# misses - сколько раз результат пришлось вычислить
# currsize - текущий размер кешаВажный момент: мемоизация решает проблему повторных вычислений, но она не устраняет фундаментальное ограничение рекурсии — глубину стека вызовов. Хотя кеширование часто помогает избежать RecursionError (потому что ветки вызовов для уже вычисленных значений не разворачиваются), для задач с очень большой естественной глубиной рекурсии (даже если нет перекрывающихся подзадач) вы все равно можете столкнуться с этим лимитом.
import time
def fib_tab(n):
"""Вычисляет числа Фибоначчи с помощью табуляции (используя список)."""
if n < 0:
raise ValueError("N должно быть >= 0")
# Для n=0 и n=1 результат равен n
if n <= 1:
return n
# Шаг 1: Создаем таблицу (список) размером n+1
# dp_table[i] будет хранить значение fib(i)
dp_table = [0] * (n + 1)
# Шаг 2: Заполняем базовые случаи
# dp_table[0] уже 0
dp_table[1] = 1
# Шаг 3: Итеративно вычисляем остальные значения
# Начинаем с i=2, так как 0 и 1 уже известны
for i in range(2, n + 1):
# Используем уже вычисленные значения из таблицы!
dp_table[i] = dp_table[i - 1] + dp_table[i - 2]
# print(f"Рассчитали dp_table[{i}] = {dp_table[i]}") # Для отладки
# Шаг 4: Результат находится в последней ячейке
return dp_table[n]
# --- Вызов ---
n_val_tab = 100 # То же значение, что и для @cache
print(f"\n--- Вычисляем fib({n_val_tab}) с табуляцией ---")
start_time = time.perf_counter()
result_tab = fib_tab(n_val_tab)
end_time = time.perf_counter()
print(f"fib({n_val_tab}) = {result_tab}")
print(f"Время выполнения: {end_time - start_time:.6f} сек") # Тоже очень быстро!import time
def fib_tab_optimized(n):
"""Вычисляет Фибоначчи с табуляцией и оптимизацией памяти до O(1)."""
if n < 0:
raise ValueError("N должно быть >= 0")
if n <= 1:
return n
# Храним только два последних вычисленных значения
prev2 = 0 # Соответствует fib(i-2), начинаем с fib(0)
prev1 = 1 # Соответствует fib(i-1), начинаем с fib(1)
# Итерируемся от 2 до n
for i in range(2, n + 1):
# Вычисляем текущее значение fib(i)
current = prev1 + prev2
# Сдвигаем значения для следующей итерации:
# то, что было prev1, станет prev2
# то, что было current, станет prev1
prev2 = prev1
prev1 = current
# print(f"Итерация {i}: current=fib({i})={current}, prev1={prev1}, prev2={prev2}")
# После завершения цикла prev1 будет содержать fib(n)
return prev1
# --- Вызов ---
n_val_opt = 100
print(f"\n--- Вычисляем fib({n_val_opt}) с оптимизированной табуляцией ---")
start_time = time.perf_counter()
result_opt = fib_tab_optimized(n_val_opt)
end_time = time.perf_counter()
print(f"fib({n_val_opt}) = {result_opt}")
print(f"Время выполнения: {end_time - start_time:.6f} сек") # Быстро, O(n) по времени
print("Пространственная сложность: O(1)") # Используем константное количество памяти!Ключевой вывод
Рекурсия — это элегантный способ мышления о задачах, сводя их к более простым версиям самих себя, но ее нужно использовать с умом, помня о стеке вызовов. Динамическое Программирование — это не конкретный алгоритм, а мощная методология оптимизации, которая (через мемоизацию или табуляцию) позволяет превратить экспоненциально медленные решения в быстрые полиномиальные, если задача обладает свойствами перекрывающихся подзадач и оптимальной подструктуры.