Рекурсия и backtracking
Перебор с возвратом - целый жанр задач «сгенерируй все»: перестановки, сочетания, подмножества, расстановка ферзей, судоку. Каркас у них один, и проверяют владение именно им, а заодно двумя фирменными багами, которые ловят почти всех.
Типовые формулировки: «выведи все подмножества», «все валидные комбинации скобок», «расставь N ферзей».
// Слово «все» в условии - почти стопроцентная подсказка. Увидел его - вспоминай каркас «выбрал, спустился, откатил», дальше остаётся подставить кандидатов.
Рекурсия: база, шаг, сборка
Любое рекурсивное решение объясняется тремя пунктами, и проговорить их вслух - значит объяснить решение целиком. База: когда отвечаем сразу, без спуска. Шаг: как задача уменьшается, чтобы в конце концов дойти до базы. Сборка: как ответ складывается из ответов на подзадачи.
База пишется ДО рекурсивного вызова, и это не стилистика. Проверка, поставленная после спуска, не спасает от бесконечной рекурсии: функция успеет вызвать себя раньше, чем доберётся до условия остановки.
Отдельный близкий жанр - «раздели и властвуй»: разбить задачу на части, решить каждую, слить результаты. Так устроены сортировка слиянием и бинарный поиск. Время таких алгоритмов описывают рекуррентным соотношением - формулой, где время для входа размера n выражено через время для меньших кусков плюс работа на слияние. Готовый ответ по такой формуле выдаёт мастер-теорема, и на собесе обычно достаточно назвать её по имени.
// Полезно помнить, что рекурсия стоит памяти. Каждый незавершённый вызов лежит в стеке, и глубина n означает O(n) памяти, даже если внутри функции нет ни одной переменной.
- стек вызовов
- область памяти, где хранятся незавершённые вызовы функций. Его переполнение и есть та самая ошибка о превышении глубины рекурсии
Каркас перебора с возвратом
Скелет умещается в три строки: выбрал кандидата и добавил его в текущий путь, спустился рекурсией, откатил выбор обратно. Перестановки, сочетания, подмножества, ферзи - это буквально один и тот же цикл, отличающийся только тем, что считается кандидатом и когда путь признаётся готовым.
Первый фирменный баг - забытый откат. Без него состояние протекает между ветками: вторая ветка начинает работу, видя выборы первой, и результат получается бессмысленным. Причём ошибка не падает, а тихо портит ответ.
Второй - ссылка вместо копии. В список результатов кладут сам путь, а не его копию. Путь дальше продолжает изменяться, и на выходе все найденные ответы оказываются одним и тем же объектом с одинаковым содержимым - обычно пустым, потому что к концу перебора откаты вычистили его целиком. В Python лечится записью path[:] или list(path).
// Вся сила метода - в отсечениях. Проверять валидность частичного решения надо сразу на ветке, а не в листе дерева перебора: отбросив ветку на третьем шаге, ты не пойдёшь по всем тысячам её продолжений. На задаче о ферзях именно отсечения превращают неподъёмный перебор в мгновенный.
Сложность перебора и выход в динамику
Сложность перебора с возвратом - это размер дерева перебора, и он честно экспоненциальный: перестановок n!, подмножеств 2ⁿ. Отсечения сокращают число ветвей и константу, но класс сложности не меняют. Мысль «перепишу рекурсию циклом, будет быстрее» ошибочна: получится тот же перебор, просто со своим стеком вместо системного.
У этого есть и обратная, приятная сторона: если ответ задачи сам по себе экспоненциален - все 2ⁿ подмножеств надо выписать - то экспоненциальное время оптимально и извиняться не за что.
Хвостовая рекурсия - это когда рекурсивный вызов стоит самым последним действием функции, и потому его в принципе можно механически развернуть в цикл. Некоторые языки так и делают. Python и Java - нет, поэтому глубокую рекурсию там пишут итеративно, вручную заводя стек.
// Настоящий выход из экспоненты один: заметить, что подзадачи повторяются. Если рекурсия несколько раз считает одно и то же, добавь кеш по аргументам - и перебор превратится в динамическое программирование. Это самый естественный вход в динамику, гораздо надёжнее, чем сразу рисовать таблицу.
- мемоизация
- кеширование результатов рекурсии по её аргументам. Технически - словарь, по смыслу - переход от перебора к динамике
Как отвечать: «Сгенерируй все подмножества массива»
Иду по каркасу перебора с возвратом: двигаюсь по индексам, на каждом элементе две ветки - взять его или пропустить. Взял, добавил в путь, спустился рекурсией, откатил. В результат кладу копию пути, а не сам путь: иначе все ответы окажутся ссылками на один и тот же список, который к концу перебора откаты опустошат. Сложность честная - O(2ⁿ), и улучшить её нельзя, потому что столько подмножеств и есть в ответе. Та же заготовка с минимальными правками даёт сочетания и перестановки: меняется только множество кандидатов на шаге и условие, при котором путь считается готовым.
Каркас, заранее обезвреженный баг с копией, честная оценка сложности с объяснением её неустранимости и обобщение на семейство задач. Четыре разных сигнала в одном коротком ответе.
На чём валят
- −Забыть откат после рекурсивного вызова: состояние протекает между ветками, ответ тихо портится.
- −Положить в результат сам путь вместо его копии: все ответы окажутся одинаковыми.
- −Написать базу после рекурсивного вызова: рекурсия не остановится.
- −Считать, что переписывание перебора циклом ускорит его: экспонента останется экспонентой.
- −Не заметить повторяющиеся подзадачи и перебирать то, что давно посчитано: там просился кеш.
Проверьте себя
Пять вопросов из банка по этой подтеме. Всего их 9, остальные разбираются в тренажёре.
- В чём идея backtracking и чем он лучше полного перебора?A)Backtracking методично перебирает все комбинации до единой, обходя дерево вариантов целиком без отсеченийB)Строит решение по шагам и отсекает заведомо негодные ветки (prune), откатываясь назадC)Backtracking работает за полиномиальное времяD)Backtracking — это то же, что динамическое программирование
показать ответ и разбор
+B)Строит решение по шагам и отсекает заведомо негодные ветки (prune), откатываясь назад// разбор: Backtracking наращивает решение по одному шагу (расстановка ферзя, выбор элемента) и проверяет ограничения на каждом шаге. Как только частичное решение нарушает условие (два ферзя бьют друг друга), вся ветка отбрасывается без досмотра её потомков — это отсечение (pruning). В худшем случае сложность всё ещё экспоненциальна, но на практике отсечения убирают большую часть дерева перебора.
- Сколько всего подмножеств и перестановок у множества из n элементов, и почему это важно для перебора?A)Подмножеств ровно n², а перестановок 2n, поэтому оба перебора остаются посильными даже при большом nB)И тех и других по n штукC)Подмножеств n!, перестановок 2^nD)Подмножеств 2^n (каждый элемент включаем или нет), перестановок n!; перебор осмыслен лишь при малом n
показать ответ и разбор
+D)Подмножеств 2^n (каждый элемент включаем или нет), перестановок n!; перебор осмыслен лишь при малом n// разбор: Каждый из n элементов в подмножестве либо есть, либо нет — 2·2·…·2 = 2^n подмножеств. Перестановок n! — на первое место n вариантов, на второе n−1 и так далее. Оба роста взрывные: уже при n=20 это миллионы, при n=13 факториал больше миллиарда. Поэтому задачи «перебрать все подмножества/перестановки» решают перебором только для малых n, иначе ищут DP или жадные/приближённые методы.
- Почему хвостовая рекурсия в Java и Python не спасает от переполнения стека, хотя в некоторых языках спасает?A)Хвостовая рекурсия в этих языках выполняется ощутимо медленнее обычной из-за проверки последнего вызоваB)Проблема только в отрицательных числахC)Хвостовая рекурсия требует особого ключевого слова, которого нетD)JVM и CPython не делают оптимизацию хвостового вызова: кадр не переиспользуется, стек растёт
показать ответ и разбор
+D)JVM и CPython не делают оптимизацию хвостового вызова: кадр не переиспользуется, стек растёт// разбор: В языках с TCO (напр. Scheme, часть Scala-случаев) хвостовой вызов переиспользует текущий кадр, превращая рекурсию в итерацию с O(1) стеком. JVM и CPython этого не делают сознательно (в т.ч. чтобы сохранить читаемые стек-трейсы), поэтому хвостовая рекурсия у них всё равно наращивает стек и может упасть с переполнением. Лечение — переписать в цикл или вести собственный стек в куче.
- Что оценивает теорема о рекуррентных соотношениях (Master theorem) для T(n) = a·T(n/b) + f(n)?A)Только пиковый объём памяти рекурсии по глубине стека, но о времени работы она ничего не сообщаетB)Число строк кода в рекурсивной функцииC)Асимптотику «разделяй и властвуй» через сравнение f(n) с числом листьев n^(log_b a) — три случаяD)Точное число рекурсивных вызовов при входе
показать ответ и разбор
+C)Асимптотику «разделяй и властвуй» через сравнение f(n) с числом листьев n^(log_b a) — три случая// разбор: Master theorem даёт асимптотику для «разделяй и властвуй»: задача делится на a подзадач размера n/b, плюс f(n) на разбиение/склейку. Сравнивают f(n) с n^(log_b a) (числом листьев дерева рекурсии): если работа на уровнях меньше — доминируют листья (случай 1), если сопоставима — добавляется множитель log n (случай 2), если больше — доминирует верх (случай 3). Так, merge sort: a=2, b=2, f=n → n log n.
- Любую рекурсию можно переписать в итерацию. Что для этого нужно в общем случае?A)Достаточно механически заменить рекурсивный вызов циклом while, никакой дополнительной структуры не требуетсяB)Явно моделировать стек вызовов собственной структурой в куче — так уходит переполнение стека вызововC)Рекурсия и итерация несводимы друг к другуD)Нужно просто увеличить лимит глубины рекурсии
показать ответ и разбор
+B)Явно моделировать стек вызовов собственной структурой в куче — так уходит переполнение стека вызовов// разбор: Рекурсия неявно использует системный стек вызовов для хранения состояния незавершённых шагов. Чтобы уйти от него, это состояние моделируют вручную — собственным стеком в куче (или очередью для BFS-подобных обходов), проталкивая туда «отложенную работу». Простые хвостовые случаи сворачиваются в обычный цикл. Выгода — нет переполнения стека вызовов на больших глубинах; плата — более громоздкий код.
дальше
Теорию прочитали. Навык ставится повторением
В Сеньорчике эта подтема идёт в ежедневных сессиях: движок возвращает её, пока ответы не станут уверенными, и ведёт прогресс отдельно по каждой подтеме. Теория внутри тоже бесплатна, лимит только на количество вопросов в день.