Суть Читайте реальные рекурсивные сниппеты и дерево рекурсии, предсказывайте поведение или стоимость и выбирайте баг или исправление с наибольшим эффектом.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на middle-высоте — в небе
◷ 14 min
Баги рекурсии находят чтением кода и трассировкой вызовов, а не догадками. Читайте каждый сниппет, предсказывайте, что он делает, и выбирайте ответ, который аккуратный инженер защитил бы на ревью.
Цель
Отработайте цикл, который вы запускаете на любой рекурсивной функции: найдите base case, проверьте, что recursive case делает прогресс, посчитайте ветвление, чтобы прочитать стоимость, и убедитесь, что backtracking восстанавливает состояние перед следующим выбором.
Сниппет 1 — отсутствующий прогресс
function sumDigits(n) { if (n === 0) return 0; // base case return (n % 10) + sumDigits(n / 10); // recursive case}sumDigits(123);
Викторина
Completed
Это должно суммировать десятичные цифры n. Что происходит на самом деле и почему?
Heads-up Так было бы, если бы n / 10 было целочисленным делением. В JavaScript / — деление с плавающей точкой, поэтому n никогда не достигает ровно 0 и base case не срабатывает; рекурсия не завершается.
Heads-up Завершения нет вовсе. Поскольку n никогда не становится ровно 0, ни один base case не срабатывает, и call stack растёт, пока не переполнится.
Heads-up Расширение base case лишь маскирует симптом. Реальный дефект в том, что recursive case не шагает к 0 целыми шагами. Используйте целочисленное деление, чтобы аргумент сужался к 0.
Читая это дерево вызовов наивного fib(4), какое утверждение верно?
Heads-up Посмотрите ещё раз: fib(2) встречается дважды, а fib(1) трижды. У наивной версии нет памяти, поэтому перекрывающиеся подзадачи пересчитываются, давая экспоненциальную работу.
Heads-up 9 узлов — это всего вызовов за время, а не одновременных фреймов. Стек держит лишь один путь корень-лист за раз, поэтому максимальная глубина здесь около 4.
Heads-up fib(n) вызывает fib(n-1) и fib(n-2): branching factor 2. Дерево верное; урок — в повторяющихся подзадачах, а не в числе ветвей.
Сниппет 3 — утёкшее состояние
function subsets(arr) { const result = [], current = []; function go(i) { if (i === arr.length) { result.push(current); return; } current.push(arr[i]); go(i + 1); current.pop(); go(i + 1); } go(0); return result;}
Викторина
Completed
Структура choose-explore-undo выглядит верно. Почему это возвращает массив пустых (или одинаковых) подмножеств?
Heads-up Pop корректно стоит между ветками include и exclude; порядок choose-explore-undo верен. Баг — в хранении живой ссылки вместо снимка-копии.
Heads-up Обе ветки должны переходить к i + 1, чтобы продвигаться по элементам; вызов go(i) не делал бы прогресса. Дефект — отсутствующая копия при записи готового подмножества.
Heads-up Subsets ветвятся include/exclude по индексу и не нуждаются в массиве used. Единственный изъян — push общего current по ссылке вместо копирования.
Сниппет 4 — вопрос о pruning
function combine(arr, k) { const result = []; function go(start, current) { if (current.length === k) { result.push([...current]); return; } for (let i = start; i < arr.length; i++) { current.push(arr[i]); go(i + 1, current); current.pop(); } } go(0, []); return result;}
Викторина
Completed
Это корректно генерирует C(n, k) комбинаций. Что меняет добавление `if (current.length + (arr.length - start) < k) return;` в начало go?
Heads-up Base case всё равно записывает только при current.length === k, поэтому выход не меняется. Проверка лишь пропускает ветки, которые заведомо не могут достичь размера k.
Heads-up Start index уже предотвращает дубликаты, идя только вперёд. Prune не может добавить дубликаты; он лишь избегает веток со слишком малым числом оставшихся элементов.
Heads-up Если current.length плюс все оставшиеся элементы всё равно меньше k, никакое завершение этой ветки не достигнет k, поэтому ничего валидного не пропускается. Это корректный prune.
Итог
Любой баг рекурсии читается одинаково: убедитесь, что base case действительно достижим (деление с плавающей точкой в Сниппете 1 никогда не даёт 0), следите за перекрывающимися подзадачами, которые делают дерево экспоненциальным (повторяющиеся вызовы fib в Сниппете 2), копируйте частичное решение при записи вместо хранения общей ссылки (Сниппет 3) и добавляйте pruning, который пропускает заведомо мёртвые ветки, не меняя выхода (Сниппет 4). Трассируйте вызовы, исправьте прогресс или состояние, затем перепроверьте.