Алгоритмы с нуля
Рекурсия и backtracking: тест с множественным выбором
Суть Тест с множественным выбором по всему юниту: base case и recursive case, глубина call stack, сложность по дереву рекурсии, шаблон backtracking и pruning.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на middle-высоте — в небеШесть вопросов через весь юнит. Каждый — это решение, которое вы принимаете, когда реально пишете рекурсивный код: не определение для заучивания, а суждение о корректности, стоимости или о том, какое исправление верное.
Цель
Убедитесь, что вы связываете четыре идеи юнита: base case и сужающийся recursive case обеспечивают завершение рекурсии, call stack задаёт память, дерево рекурсии задаёт время, а backtracking с pruning превращает полный перебор в нечто практичное.
Викторина
Completed
У рекурсивной функции есть base case, но она всё равно переполняет стек на любом входе, даже на крошечном. В чём наиболее вероятная причина?
Heads-up Неправильный возврат base case даёт неправильный ответ, а не переполнение стека. Переполнение означает, что рекурсия не останавливается, а это проблема прогресса в recursive case.
Heads-up Рекурсии не нужен цикл. Дефект в том, что каждый вызов должен приближаться к base case; если аргумент не сужается, base case недостижим.
Heads-up Если переполнение происходит даже на крошечных входах, значит, рекурсия не делает прогресса. Корректная сужающаяся рекурсия на малом n никогда бы не переполнила стек.
Викторина
Completed
factorial(n) и наивный fibonacci(n) оба рекурсируют до глубины n. Почему factorial нормален для больших n, а fibonacci нет?
Heads-up Глубина стека задаётся самым глубоким путём, а не общим числом вызовов. Оба достигают глубины n, значит, оба используют O(n) стека. Разница в общей работе — числе узлов дерева рекурсии.
Heads-up У обоих есть base case и оба завершаются. Fibonacci медленный, потому что branching factor 2 делает дерево рекурсии экспоненциальным, а не потому, что он не останавливается.
Heads-up Они рекурсируют до одной и той же глубины n. Именно branching factor (2 против 1), а не глубина, заставляет число узлов fibonacci взрываться до O(2^n).
Викторина
Completed
У рекурсивной функции branching factor b = 3 и глубина d = 12, на вызов делается O(1) работы. Примерно сколько вызовов она делает и о чём это говорит?
Heads-up Branching factor и глубина умножаются на каждом уровне, а не один раз. Каждый уровень умножает число узлов на b, давая b^d, а не b на d.
Heads-up Основание — это branching factor, а показатель — глубина: b^d = 3^12, а не d^b. Перестановка их сильно занижает оценку.
Heads-up Это глубина стека, а не число вызовов. При ветвлении на каждом уровне до b раз больше узлов, чем на предыдущем.
Викторина
Completed
В шаблоне backtracking choose-explore-undo что ломается, если опустить шаг undo (push в current, но никогда pop)?
Heads-up Завершение контролируется base case, а не undo. Без undo рекурсия всё равно останавливается — она лишь по пути выдаёт неправильные частичные решения.
Heads-up Undo необходим для корректности при общем изменяемом состоянии. Общий массив current должен быть чистым перед следующим соседним выбором, иначе каждая поздняя ветка наследует оставшиеся элементы.
Heads-up Pruning — это проверка is-valid перед рекурсией; она независима от undo. Пропуск undo портит частичное решение, а это отдельный дефект.
Викторина
Completed
Subsets, permutations и combinations используют один и тот же шаблон backtracking. Что на самом деле их различает?
Heads-up Все три написаны одним и тем же рекурсивным скелетом backtracking в этом юните. Меняются логика выбора и base case, а не рекурсия против итерации.
Heads-up У combinations есть естественный prune (осталось слишком мало элементов, чтобы достичь k), но pruning — это общая идея backtracking. Определяющее различие — правило выбора, а не кто может делать prune.
Heads-up У них разные размеры выхода: 2^n subsets против n! permutations. Они различаются, потому что для permutations порядок важен, а для subsets — нет.
Викторина
Completed
Корректный рекурсивный обход дерева работает в тестах, но коллега говорит, что перед продакшеном его надо переписать итеративно. Когда это оправдано?
Heads-up Рекурсия и итерация обычно имеют одинаковую временную сложность. Беспокойство — это память на стеке при большой глубине, а не сырая скорость; неглубокая рекурсия не нуждается в переписывании.
Heads-up Корректная на малых входах всё равно может переполнить стек при большой глубине. Если глубина масштабируется со входом, итеративная версия с явным стеком убирает этот жёсткий лимит.
Heads-up Отсутствующий base case — это баг, который надо исправить как есть, а не компромисс рекурсия-против-итерации. Реальный триггер для итеративного переписывания — неограниченная глубина стека.
Итог
Сквозная линия юнита — одна цепочка: base case плюс сужающийся recursive case обеспечивают завершение рекурсии; call stack делает глубину стоимостью O(глубина) по памяти; дерево рекурсии делает общую работу равной branching factor в степени глубины по времени; а backtracking применяет этот рекурсивный скелет (choose, explore, undo) с pruning, чтобы пропускать обречённые ветки. Сначала верно задайте base case и прогресс, затем читайте время по дереву, а память — по стеку.