Всем привет!
Последние несколько дней я почти полностью посвятил рекурсии. До этого я мог написать рекурсивную функцию по знакомому шаблону, но не всегда понимал, почему она работает и как самостоятельно увидеть рекурсивную идею в новой задаче.
Сейчас я начал смотреть на такие задачи немного иначе. Вместо того чтобы сразу писать код или пытаться представить все вызовы функции, я сначала разбираю смысл состояния.
Что я начал делать перед написанием рекурсии
Теперь перед кодом я стараюсь ответить на четыре вопроса:
- что именно должна делать или возвращать функция;
- какой случай является самым простым;
- как получить ответ через задачу меньшего размера;
- почему каждый новый вызов приближает нас к остановке.
Например, если функция решает задачу для числа $$$n$$$, то следующий вызов обычно должен работать с меньшим значением: $$$n-1$$$, $$$n/2$$$ или другой более простой версией состояния.
Самое важное — рекурсия не должна вызывать сама себя бесконечно. Поэтому нужен базовый случай.
Простой пример:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
Здесь функция решает задачу для $$$n$$$ через уже более простую задачу для $$$n-1$$$.
Формула выглядит так:
$$$ n! = n \cdot (n-1)! $$$Базовый случай:
$$$ 0! = 1 $$$Раньше я просто запоминал такой код. Сейчас уже лучше понимаю, зачем нужна каждая его часть.
Ветвящаяся рекурсия
Ещё я понял разницу между обычной цепочкой рекурсивных вызовов и ситуацией, когда из одного состояния появляются сразу несколько следующих состояний.
Хороший пример — биномиальные коэффициенты.
Для них используется формула:
$$$ C_n^k = C_{n-1}^{k-1} + C_{n-1}^{k} $$$Базовые случаи:
В обоих случаях ответ равен $$$1$$$.
def combinations(n, k):
if k == 0 or k == n:
return 1
return combinations(n - 1, k - 1) + combinations(n - 1, k)
Здесь из одного вызова появляются два новых. Поэтому количество вычислений быстро растёт.
Именно на таких задачах я начал лучше понимать, почему правильная формула ещё не гарантирует быстрое решение.
Мемоизация и повторяющиеся состояния
Некоторые рекурсивные решения у меня получали TLE, хотя сама идея была правильной.
Проблема оказалась в том, что программа много раз вычисляла одно и то же состояние.
Например, при вычислении биномиальных коэффициентов вызов с одинаковыми значениями n и k может появляться снова и снова.
Для таких случаев можно использовать мемоизацию:
from functools import cache
@cache
def combinations(n, k):
if k == 0 or k == n:
return 1
return combinations(n - 1, k - 1) + combinations(n - 1, k)
Теперь результат каждого состояния сохраняется.
Если функция снова вызывается с теми же аргументами, Python не вычисляет всё заново, а берёт готовый ответ.
После этого я начал задавать себе полезный вопрос:
Не решаю ли я одну и ту же маленькую задачу несколько раз?
Если ответ положительный, то, скорее всего, нужна мемоизация или динамическое программирование.
Ханойские башни
Долгое время я не мог нормально понять задачу о Ханойских башнях.
Сам код выглядит коротко, но рекурсивный переход сначала казался почти магическим.
Мне помогло визуальное объяснение на YouTube. После него я наконец увидел три основных шага:
- перенести $$$n-1$$$ дисков с начального стержня на вспомогательный;
- перенести самый большой диск на конечный стержень;
- перенести $$$n-1$$$ дисков со вспомогательного стержня на конечный.
То есть задача для $$$n$$$ дисков сводится к двум задачам для $$$n-1$$$ дисков.
Количество действий задаётся рекуррентной формулой:
$$$ T(n)=2T(n-1)+1 $$$Итоговое количество перемещений:
$$$ T(n)=2^n-1 $$$После того как я понял именно эти три шага, код уже стал намного понятнее:
def hanoi(n, start, finish, auxiliary):
if n == 1:
print(start, finish)
return
hanoi(n - 1, start, auxiliary, finish)
print(start, finish)
hanoi(n - 1, auxiliary, finish, start)
Главный вывод для меня: иногда одна хорошая визуализация даёт больше, чем много попыток просто читать готовый код.
Первое настоящее понимание DFS
После обычной рекурсии я начал разбирать обходы графов.
Одна из задач была связана с комнатой или лабиринтом, представленным в виде таблицы.
Сначала я смотрел на неё просто как на двумерный массив. Потом понял более полезную модель:
- каждая доступная клетка — это вершина графа;
- переход в соседнюю клетку — это ребро;
- вся доступная область — компонент связности.
Функция DFS делает примерно следующее:
- проверяет, можно ли зайти в клетку;
- отмечает её как посещённую;
- запускается для соседних клеток.
def dfs(x, y):
if x < 0 or x >= n or y < 0 or y >= m:
return 0
if grid[x][y] == '#':
return 0
if visited[x][y]:
return 0
visited[x][y] = True
result = 1
result += dfs(x + 1, y)
result += dfs(x - 1, y)
result += dfs(x, y + 1)
result += dfs(x, y - 1)
return result
Идею можно записать так:
$$$ dfs(v)=1+\sum dfs(u) $$$где $$$u$$$ — ещё не посещённые соседи вершины $$$v$$$.
Зачем отмечать посещённые клетки
Раньше я не до конца понимал, почему массив visited настолько важен.
Теперь вижу сразу две причины.
Во-первых, без отметки посещённых вершин алгоритм может ходить по кругу:
A -> B -> A -> B -> ...
Во-вторых, одна и та же клетка может быть посчитана несколько раз.
Поэтому вершину нужно отмечать посещённой сразу после входа в неё, а не после обхода всех соседей.
Это небольшая деталь, но без неё DFS может работать неправильно или вообще не завершиться.
Деревья и правильное хранение данных
Ещё мне попалась задача, где нужно было удалить сообщение вместе со всеми ответами на него.
Изначально данные было удобно читать в виде:
сообщение -> родитель
Но для удаления всех потомков это хранение неудобно.
Гораздо полезнее построить обратную структуру:
родитель -> список детей
Например:
children = [[] for _ in range(n)]
for child, parent in relations:
children[parent].append(child)
После этого удаление всех ответов превращается в обычный обход поддерева:
def remove_subtree(v):
removed[v] = True
for child in children[v]:
remove_subtree(child)
Это помогло мне понять важный принцип:
Иногда главная сложность задачи не в алгоритме, а в том, как представить исходные данные.
Если хранение выбрано правильно, само решение может оказаться очень коротким.
Какие ошибки я исправил
За эти дни я заметил несколько повторяющихся ошибок в своём коде.
1. Печать вместо возврата значения
Иногда я писал рекурсивную функцию, которая сразу что-то печатала, хотя дальше результат нужно было использовать в вычислениях.
Теперь стараюсь разделять:
- вычисление результата через
return; - вывод результата через
print.
Например, лучше так:
def sum_digits(n):
if n == 0:
return 0
return n % 10 + sum_digits(n // 10)
print(sum_digits(12345))
2. Лишние глобальные переменные
Глобальные переменные могут сделать решение сложнее для понимания и отладки.
Теперь стараюсь передавать нужные данные в аргументах функции или возвращать результат.
3. Неправильный выбор структуры данных
Если нужны быстрые проверки принадлежности, лучше использовать set.
used = set()
if value in used:
...
В среднем проверка через множество работает за $$$O(1)$$$, тогда как поиск в списке занимает $$$O(n)$$$.
4. Попытка изменить строку
Я ещё раз закрепил, что строки в Python неизменяемые.
Так делать нельзя:
s[0] = 'a'
Нужно создавать новую строку или сначала преобразовывать её в список.
s = list(s)
s[0] = 'a'
s = ''.join(s)
5. Слишком раннее написание кода
Иногда я начинал писать решение, ещё не определив:
- что является вершиной;
- какие существуют переходы;
- что хранит функция;
- какие состояния уже посещены.
Теперь стараюсь сначала построить модель задачи, а потом переходить к реализации.
Практические советы для других новичков
Вот несколько вещей, которые действительно помогли мне лучше понять рекурсию.
Сначала придумайте смысл функции
Не начинайте с первой строки кода.
Сначала сформулируйте словами:
dfs(v) возвращает размер области, достижимой из вершины v.
Или:
solve(n) возвращает ответ для задачи размера n.
После этого базовый случай и переход становятся намного понятнее.
Не пытайтесь держать в голове всё дерево вызовов
Рекурсивная функция должна правильно решать текущую задачу, предполагая, что меньшая задача уже решается правильно.
Это намного легче, чем вручную представлять сотни вызовов.
Проверяйте уменьшение задачи
Каждый рекурсивный вызов должен приближаться к базовому случаю.
Например:
solve(n - 1)
обычно безопаснее, чем:
solve(n)
Второй вариант может привести к бесконечной рекурсии.
Рисуйте маленькие примеры
Для $$$n=3$$$ или маленькой таблицы удобно нарисовать дерево вызовов на бумаге.
Это помогает увидеть:
- повторяющиеся состояния;
- порядок вызовов;
- момент возврата из функции;
- необходимость
visited.
Всегда оценивайте сложность
Даже правильная рекурсия может быть слишком медленной.
Если из каждого состояния появляются два новых вызова, сложность может быть близка к $$$O(2^n)$$$.
Если все состояния сохраняются и каждое вычисляется один раз, решение часто ускоряется до $$$O(n)$$$ или $$$O(nk)$$$.
Что дальше
В следующие дни хочу закрепить:
- DFS на графах;
- DFS на двумерных таблицах;
- поиск компонент связности;
- обход деревьев;
- BFS и очередь;
- первые задачи на динамическое программирование.
Особенно хочу научиться быстрее определять модель задачи ещё до написания кода:
- массив;
- граф;
- дерево;
- сетка;
- состояние динамического программирования.
Главный вывод за эти три дня:
Рекурсия становится намного проще, когда перестаёшь воспринимать её как магию и начинаешь точно понимать смысл каждого вызова, базовый случай и переход к меньшей задаче.
