Теория — Урок 46 | Python Fundamentals

Что такое рекурсия

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

# factorial.py
"""Рекурсивный факториал с базовым и рекурсивным случаем."""


def factorial(n: int) -> int:
    if n == 0 or n == 1:          # базовый случай
        return 1
    return n * factorial(n - 1)   # рекурсивный случай


print(factorial(5))  # 120

Функция factorial(5) вычисляется как 5 * factorial(4), а factorial(4) — как 4 * factorial(3), и так до factorial(1), который сразу возвращает 1.

Базовый и рекурсивный случай

Любая корректная рекурсия состоит из двух частей:

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

💡 На заметку: если базовый случай не достижим (например, функция вызывает себя с тем же аргументом), программа уйдёт в бесконечную рекурсию и упадёт с RecursionError.

⚠️ Проверить по документации: в современном коде часто используют guard clauses — ранний возврат при некорректных входных данных. Например, можно сразу поднять ValueError, если n < 0. Это не отменяет базовый случай, а дополняет его проверкой аргументов.

Стек вызовов и RecursionError

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

Для factorial(3) стек вызовов выглядит так:

# factorial(3) ждёт результат factorial(2)
#   factorial(2) ждёт результат factorial(1)
#     factorial(1) возвращает 1
#   возвращает 2 * 1 = 2
# возвращает 3 * 2 = 6

У стека есть лимит. По умолчанию Python позволяет около 1000 вложенных вызовов; при превышении возникает RecursionError:

# infinite_recursion.py
import sys


def infinite():
    return infinite()


print(f"Лимит рекурсии: {sys.getrecursionlimit()}")
try:
    infinite()
except RecursionError:
    print("Переполнение стека!")

⚠️ Проверить по документации: лимит рекурсии можно узнать через sys.getrecursionlimit() и изменить через sys.setrecursionlimit(). Увеличивать лимит обычно не рекомендуется — лучше переписать алгоритм итеративно или с мемоизацией.

Хвостовая рекурсия

Хвостовая рекурсия — частный случай, при котором рекурсивный вызов является последней операцией функции. В некоторых языках такой вызов оптимизируется и не расходует стек, но в Python это не работает.

# tail_recursion.py
def factorial_tail(n: int, accumulator: int = 1) -> int:
    if n == 0 or n == 1:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)


print(factorial_tail(5))  # 120

Несмотря на то что рекурсивный вызов — последняя операция, Python всё равно создаёт новый кадр стека. Поэтому для больших n хвостовая рекурсия тоже приведёт к RecursionError. В таких случаях используйте итерацию:

# iterative_factorial.py
def factorial_iterative(n: int) -> int:
    accumulator = 1
    while n > 1:
        accumulator *= n
        n -= 1
    return accumulator


print(factorial_iterative(5))  # 120

⚠️ Важно: не полагайтесь на хвостовую рекурсию в Python как на способ избежать переполнения стека. Для глубоких вычислений выбирайте цикл, очередь или мемоизацию.

Рекурсия или итерация?

Рекурсию и цикл можно часто заменить друг на друга, но у каждого подхода есть свои сильные стороны.

Критерий	Рекурсия	Итерация
Читаемость	Высокая для деревьев, графов, вложенных структур	Выше для простых последовательностей
Память	Стек вызовов растёт с глубиной	Обычно константная или меньше
Скорость	Медленнее из-за накладных расходов на вызовы	Быстрее
Риск	Переполнение стека	Бесконечный цикл
Когда использовать	Деревья, графы, обход вложенных данных, разбор выражений	Простые переборы, большие глубины

Функция isinstance

Встроенная функция isinstance(obj, classinfo) проверяет, принадлежит ли объект указанному типу или кортежу типов. Это удобно, когда рекурсивная функция должна по-разному обрабатывать числа, строки, списки и словари.

# isinstance_demo.py
x = 10
y = "Hello"

print(isinstance(x, int))        # True
print(isinstance(y, str))        # True
print(isinstance(y, (int, float)))  # False

value = 3.14
if isinstance(value, (int, float)):
    print("Число")
else:
    print("Не число")

Глубокое копирование и рекурсия

Функция deepcopy() из модуля copy использует рекурсию, чтобы создать полностью независимую копию объекта, включая все вложенные коллекции. Обычный copy() копирует только верхний уровень, а вложенные объекты остаются общими.

# deepcopy_demo.py
from copy import deepcopy


original_list = [[1, 2], [3, 4]]
copy_lst = deepcopy(original_list)
copy_lst[0][0] = "X"

print("Оригинал:", original_list)  # [[1, 2], [3, 4]]
print("Копия:", copy_lst)          # [['X', 2], [3, 4]]

В практических заданиях этого урока вы реализуете собственный аналог deepcopy() с помощью isinstance() и рекурсии.

Где применяется рекурсия

Обход деревьев и графов — поиск в глубину (DFS) естественно записывается рекурсивно.
Разбор вложенных выражений — каждое подвыражение обрабатывается той же функцией.
Ханойские башни — классическая задача на разбиение проблемы на две меньшие.
Комбинаторика — генерация перестановок, подмножеств и комбинаций.
Глубокое копирование — обход вложенных коллекций с созданием независимых копий.

📖 Теория: Рекурсия

⚡ Кратко