def recursive(args):
if base_condition(args): # базовый случай
return base_value
return recursive(smaller_args) # рекурсивный случай
Функции и методы
Функция/метод
Описание
Пример
isinstance(obj, classinfo)
Проверяет тип объекта. classinfo может быть кортежем типов.
isinstance(x, (int, float))
copy.copy(x)
Поверхностная копия: копирует верхний уровень, вложенные объекты — по ссылке.
lst2 = copy.copy(lst1)
copy.deepcopy(x)
Глубокая копия: рекурсивно копирует все вложенные изменяемые объекты.
lst2 = copy.deepcopy(lst1)
sys.getrecursionlimit()
Возвращает максимально допустимую глубину рекурсии.
sys.getrecursionlimit()
sys.setrecursionlimit(limit)
Изменяет лимит глубины рекурсии. Используйте с осторожностью.
sys.setrecursionlimit(2000)
functools.lru_cache
Декоратор для мемоизации: сохраняет результаты вызовов и ускоряет рекурсию.
@lru_cache(maxsize=None)
⚠️ Проверить по документации:sys.setrecursionlimit() и functools.lru_cache не разбираются в исходной лекции напрямую, но являются стандартными инструментами Python для работы с рекурсией.
Исключения
Исключение
Когда возникает
Что делать
RecursionError
Превышена максимальная глубина рекурсии.
Проверить базовый случай, уменьшать аргумент, переписать на цикл.
ValueError
Функция получила аргумент неподходящего значения.
Добавить guard clause и сообщение об ошибке.
Частые рекурсивные паттерны
# 1. Свертка числа к 0
def sum_digits(n: int) -> int:
if n == 0:
return 0
return n % 10 + sum_digits(n // 10)
# 2. Разделяй и властвуй
def binary_search(arr: list[int], target: int, left: int, right: int) -> int:
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
if arr[mid] < target:
return binary_search(arr, target, mid + 1, right)
return binary_search(arr, target, left, mid - 1)
# 3. Обход вложенной структуры
def sum_nested(data):
if isinstance(data, int):
return data
if isinstance(data, (list, tuple)):
return sum(sum_nested(item) for item in data)
return 0