Полевой справочник
Рекурсия
O(n)Функция вызывает саму себя на меньшей версии той же задачи, пока не сработает базовый случай, а результаты складываются на обратном пути.
Сигналы
задача определена через меньшую версию самой себявложенная/древовидная структура для обхода (папки, выражение, связный список)нужно посчитать сумму/количество/глубину по всем подэлементаместественное деление на базовый случай и рекурсивный (факториал, Фибоначчи, глубина дерева)
Шаблон
function recurse(n) {
if (n <= 0) return 0; // base case
return n + recurse(n - 1); // recursive case: smaller subproblem
}Похоже, но не то
- Бэктрекинг: Обычная рекурсия просто спускается к меньшим подзадачам и возвращает значение. Бэктрекинг это рекурсия плюс цикл выбрать/пойти дальше/отменить, который строит и разбирает путь, чтобы перебрать все допустимые варианты.
n рекурсивных вызовов с O(1) работы в каждом и без ветвления -> O(n) времени, O(n) глубина стека вызовов. На глубине порядка 1e4-1e5 при несбалансированных данных возможно переполнение стека.
Изучить этот паттерн