Рекурсивная функция вызывает себя для решения меньшей версии той же задачи. Каждая рекурсивная функция требует двух вещей: **базового случая**, останавливающего рекурсию, и **рекурсивного случая**, движущегося к базовому.
```python
def factorial(n):
if n == 0: # базовый случай: остановиться здесь
return 1
return n * factorial(n - 1) # рекурсивный случай: меньшая задача
factorial(4) # 24
```
**Что происходит при каждом вызове — стек вызовов**
Когда Python вызывает функцию, он помещает фрейм на стек вызовов. Каждый фрейм хранит локальные переменные и адрес возврата. С `factorial(4)` стек растёт так:
```
factorial(4) -> вызывает factorial(3) ждёт...
factorial(3) -> вызывает factorial(2) ждёт...
factorial(2) -> вызывает factorial(1) ждёт...
factorial(1) -> вызывает factorial(0) ждёт...
factorial(0) -> возвращает 1 (базовый случай!)
factorial(1) возвращает 1 * 1 = 1
factorial(2) возвращает 2 * 1 = 2
factorial(3) возвращает 3 * 2 = 6
factorial(4) возвращает 4 * 6 = 24
```
Стек *раскручивается* после достижения базового случая — каждый ждавший вызов получает ответ и вычисляет собственное значение.
**Самая распространённая ошибка: забыть базовый случай**
Без базового случая рекурсия никогда не останавливается — Python генерирует `RecursionError`:
```python
def bad_factorial(n):
return n * bad_factorial(n - 1) # нет базового случая!
bad_factorial(3) # RecursionError: maximum recursion depth exceeded
```
**Другая распространённая ошибка: не двигаться к базовому случаю**
```python
def also_bad(n):
if n == 0:
return 0
return also_bad(n + 1) # движется от 0, а не к нему!
```
Всегда проверяй: делает ли каждый рекурсивный вызов задачу *строго меньше*?
**Простой пример: сумма списка**
```python
def total(lst):
if not lst: # базовый случай: пустой список
return 0
return lst[0] + total(lst[1:]) # первый элемент + сумма остального
total([1, 2, 3, 4]) # 10
```
Это менее эффективно, чем `sum(lst)`, но чётко показывает рекурсивный паттерн: отдели один элемент, рекурси по остальному, объедини.
Когда рекурсия — правильный инструмент: деревья, «разделяй и властвуй»
Рекурсия блестяще подходит, когда задача имеет естественно рекурсивную структуру: деревья, вложенные данные, алгоритмы «разделяй и властвуй».
**Бинарный поиск** (разделяй и властвуй)
```python
def binary_search(lst, target, lo=0, hi=None):
if hi is None:
hi = len(lst) - 1
if lo > hi: # базовый случай: не найдено
return -1
mid = (lo + hi) // 2
if lst[mid] == target:
return mid
if lst[mid] < target:
return binary_search(lst, target, mid + 1, hi) # ищем в правой половине
return binary_search(lst, target, lo, mid - 1) # ищем в левой половине
binary_search([1, 3, 5, 7, 9], 7) # 3
```
**Обход дерева** (естественно рекурсивная структура)
```python
def tree_sum(node):
if node is None: # базовый случай: пустой узел
return 0
return node['value'] + tree_sum(node.get('left')) + tree_sum(node.get('right'))
tree = {'value': 1, 'left': {'value': 2, 'left': None, 'right': None},
'right': {'value': 3, 'left': None, 'right': None}}
tree_sum(tree) # 6
```
**Выравнивание вложенных списков**
```python
def flatten(lst):
result = []
for item in lst:
if isinstance(item, list):
result.extend(flatten(item)) # рекурсия во вложенный список
else:
result.append(item)
return result
flatten([1, [2, [3, 4]], 5]) # [1, 2, 3, 4, 5]
```
**Хвостовая рекурсия — Python её не оптимизирует**
В некоторых языках (Scheme, Erlang) рекурсивный вызов, являющийся *последней* операцией в функции (хвостовой вызов), оптимизируется компилятором для повторного использования фрейма стека. Python намеренно этого НЕ делает (Гвидо ван Россум: это сделало бы трассировки нечитаемыми). Хвостово-рекурсивная функция в Python всё равно создаёт O(n) фреймов стека:
```python
def factorial_tail(n, acc=1):
if n == 0:
return acc
return factorial_tail(n - 1, acc * n) # хвостовой вызов - но НЕ оптимизируется
```
Если нужна очень глубокая рекурсия (тысячи вызовов), вместо неё используй итерацию.
Рекурсия vs итерация, lru_cache, и преобразование в стек
**Рекурсия vs итерация — когда переключаться**
Рекурсия элегантна для естественно иерархических задач. Итерация часто лучше, когда глубина рекурсии может быть большой, или структура линейная (связный список, плоская последовательность).
```python
# Рекурсивно - понятно, но O(n) фреймов стека
def sum_recursive(n):
if n == 0: return 0
return n + sum_recursive(n - 1)
# Итеративно - тот же результат, O(1) места в стеке
def sum_iterative(n):
total = 0
while n > 0:
total += n
n -= 1
return total
```
Лимит рекурсии Python по умолчанию — 1000. Можно поднять через `sys.setrecursionlimit(n)`, но это временная мера — большая глубина рекурсии обычно означает, что стоит перейти на итерацию.
**`functools.lru_cache` — мемоизация дорогих рекурсивных вызовов**
Без кешировани наивный Фибоначчи повторно вычисляет одни и те же подзадачи экспоненциально:
```python
def fib(n):
if n <= 1: return n
return fib(n - 1) + fib(n - 2) # O(2^n) вызовов
fib(35) # занимает ~2 секунды
```
Добавь `@lru_cache` и каждая подзадача решается один раз:
```python
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n <= 1: return n
return fib(n - 1) + fib(n - 2) # теперь O(n) вызовов
fib(35) # мгновенно
fib.cache_info() # CacheInfo(hits=..., misses=36, ...)
```
**Преобразование рекурсии в итерацию с явным стеком**
Любую рекурсию можно преобразовать в итерацию, поддерживая собственный стек (список). Это полностью избегает лимита рекурсии Python:
```python
def flatten_iterative(lst):
result = []
stack = [lst]
while stack:
current = stack.pop()
for item in reversed(current):
if isinstance(item, list):
stack.append(item) # поместить вложенный список для обработки позже
else:
result.append(item)
return result
flatten_iterative([1, [2, [3, 4]], 5]) # [1, 2, 3, 4, 5]
```
**Практическое правило**: используй рекурсию, когда глубина ограничена и мала (например, высота дерева < 100), и `lru_cache`, когда подзадачи пересекаются. Переходи на итерацию (с явным стеком), когда глубина неограничена или критична производительность.
Напишите рекурсивную функцию, которая подсчитывает, сколько раз целевое значение встречается во вложенном списке (списке, который может содержать другие списки).
def flatten(data):
result = []
for item in data:
if isinstance(item, list):
result.extend(flatten(item))
else:
result.append(item)
return result
print(flatten([1, [2, [3, [4]], 5], 6]))
Напишите рекурсивную функцию, которая выполняет бинарный поиск в отсортированном списке. Возвращайте индекс целевого элемента, если найден, или -1, если нет.
Напишите рекурсивную функцию, которая выводит шаги решения головоломки Ханойских башен для n дисков. Переместите все диски со стержня A на стержень C, используя стержень B как вспомогательный. Выводите каждый ход как 'Move disk from X to Y'.
def hanoi(n, source, target, auxiliary):
if n == 1:
print(f"Move disk from {source} to {target}")
return
hanoi(n - 1, source, auxiliary, target)
print(f"Move disk from {source} to {target}")
hanoi(n - 1, auxiliary, target, source)
hanoi(3, 'A', 'C', 'B')
No split tab
Настройки cookies
Мы используем необходимые cookies для работы сайта. С вашего разрешения мы также можем сохранять настройки сайта и использовать аналитические и рекламные cookies, чтобы понимать использование сайта и поддерживать развитие проекта.
* Вы всегда можете изменить свой выбор в настройках сайта.
Выберите категории cookies
Настройки аналитики
Можно отключить аналитику использования платформы. Также можно отправить в Google Analytics запрос на удаление данных об использовании этого сайта, связанных с этим браузером.
Учебный workspace
Учитесь, читая, запуская код и решая задачи.
Практикуйте программирование с пояснениями тем, упражнениями, инструментами browser IDE, проверкой regex и тренировкой печати кода в одном workspace.
Открывайте инструменты во вкладках.Упражнения, IDE-инструменты и тренажеры остаются доступными как вкладки сайта.
Переключайтесь без потери контекста.Переходите между пояснениями, кодом и утилитами, сохраняя свое место.
Используйте sidebar как карту.Левые панели содержат навигацию, настройки, файлы, libraries и управление инструментами.
PythonJavaScriptSQLite
Одна IDE, три практичных режима
Python в браузере.Запускайте небольшие скрипты, пробуйте библиотеки и тренируйте API-запросы без установки.
JavaScript для быстрых экспериментов.Проверяйте код для браузера и сравнивайте идеи рядом с учебными материалами.
SQLite для практики с данными.Открывайте обозреватель базы данных, изучайте таблицы, пишите запросы и учитесь SQL локально.
ТемаIDE
Работайте рядом в split tabs
Держите инструкции перед глазами.Откройте упражнение или справочную страницу рядом с IDE, вместо постоянных переключений.
Сравнивайте инструменты во время обучения.Размещайте проверки regex, пояснения и эксперименты с кодом рядом, когда это нужно для задачи.
Закройте split, когда закончите.Workspace вернётся к одной сфокусированной вкладке, а открытые вкладки сайта останутся доступны.
Тренажер слепой печати кода
Или просто текста
Тренажер рассчитан на физическую клавиатуру.Откройте этот раздел на ноутбуке или компьютере с широким экраном. На телефоне тренировка слепой печати не будет корректной.
Скорость: 0 зн/мин
0 слов/мин
Лучшая скорость (60с): 0 зн/мин
0 слов/мин
Ошибки: 0
Общее время: 0.0 с
Для активации режима слепого набора не подсматривайте на физическую клавиатуру.