Алгоритмы в Node: рекурсия, деревья и обход графов
Рекурсия, её реальная цена и как моделировать и обходить деревья и графы средствами чистого Node.
Map/Set и fs/promises из среднего курса. К концу этого урока вы сможете:
- писать рекурсивную функцию с корректным базовым случаем и рассуждать о её стеке вызовов;
- назвать компромиссы рекурсии и применять мемоизацию там, где она действительно помогает;
- моделировать дерево и граф в Node и обходить дерево каталогов;
- разрешать зависимости через топологический порядок и обнаруживать циклы;
- реализовывать и выбирать между поиском в ширину (BFS) и в глубину (DFS).
1. Рекурсия: базовый и рекурсивный случай
Рекурсивная функция вызывает саму себя на меньшей версии той же задачи. У каждой корректной рекурсии ровно две части: базовый случай, который возвращает ответ напрямую без рекурсии, и рекурсивный случай, который делает немного работы и затем вызывает себя на чём-то более близком к базовому.
function factorial(n) {
if (n <= 1) return 1; // base case: stop recursing
return n * factorial(n - 1); // recursive case: shrink toward the base
}
console.log(factorial(5)); // 120Читайте это как контракт: factorial(5) доверяет factorial(4) быть верным, умножает на 5 и возвращает. Базовый случай (n <= 1) — это то, что останавливает спуск. Уберите его — и функция никогда не завершится.
Аналогия. Рекурсия — это матрёшка. Чтобы сосчитать кукол, вы открываете внешнюю (немного работы), затем задаёте тот же вопрос кукле внутри (рекурсивный вызов). Самая маленькая цельная кукла, которую нельзя открыть, — это базовый случай; без него вы открывали бы вечно.
Рекурсия блистает, когда сами данные вложены на неизвестную глубину — папки внутри папок или ветка комментариев с ответами на ответы. Плоский цикл for не может легко выразить «и повтори это для каждого потомка, как бы глубоко он ни уходил»; рекурсия — может.