Алгоритмы с нуля
Что такое рекурсия?
Представь себе поиск выхода из лабиринта. Одна тактика: на каждом перекрёстке пробуй один путь, и если тот упирается в тупик, вернись и попробуй другой. Ты применяешь одну и ту же стратегию (исследовать, откатиться, повторить) снова и снова. В этом суть рекурсии — функция, которая решает задачу, вызывая саму себя на меньшей версии той же задачи, доверяя, что она сработает для меньшей версии так же, как для целого.
После этого урока ты поймёшь, что такое рекурсия: как функция может вызвать саму себя, что такое базовый случай и рекурсивный случай и почему оба обязательны, как работает рекурсивный прыжок веры (доверься, что рекурсивный вызов сделает правильное для меньшего входа), и когда рекурсия сияет — когда задача естественно разбивается на меньшие копии самой себя.
Что такое рекурсия?
Рекурсия — это когда функция вызывает саму себя для решения меньшей версии той же задачи. Вместо решения задачи целиком ты разбиваешь её на две части:
- Базовый случай: Версия задачи настолько маленькая, что ты можешь ответить на неё сразу, без рекурсии.
- Рекурсивный случай: Функция вызывает саму себя на меньшем входе, потом использует тот ответ, чтобы построить ответ для твоего текущего входа.
Обе части обязательны. Без базового случая функция вызывает себя бесконечно. Без сжимающегося рекурсивного случая ты никогда не достигнешь базовый — ты зацикливаешься иначе.
Две обязательные части
Посмотрим на конкретный пример: вычисление факториала числа.
Факториал определён как: 5! = 5 × 4 × 3 × 2 × 1 = 120. В общем виде, n! = n × (n - 1)!.
1
function factorial(n) {
2
// Базовый случай: остановиться здесь
3
if (n <= 1) {
4
return 1;
5
}
6
// Рекурсивный случай: сжать и вызвать себя
7
return n * factorial(n - 1);
8
}
- L2 Базовый случай: самый маленький вход, который мы обрабатываем напрямую. Без рекурсии.
- L5 Рекурсивный случай: вызвать factorial на меньшем входе, потом использовать результат.
Почему это работает? Когда ты вызываешь factorial(4), она говорит: «Мне нужно 4 × factorial(3).» Ты доверяешь, что factorial(3) вернёт 6 (правильный ответ для 3!). Потом ты умножаешь 4 × 6 = 24. Это доверие — что рекурсивный вызов сделает правильное для меньшего входа — называется рекурсивным прыжком веры.
Почему прыжок веры работает
Ключевая идея: каждый рекурсивный вызов передаёт меньший вход. В конце концов, вход сжимается до 1 (или 0), и базовый случай его ловит. Тогда цепь вызовов разворачивается, каждый строит свой ответ из ответа меньшего ниже.
Проследим factorial(4):
factorial(4) → нужно 4 × factorial(3)
factorial(3) → нужно 3 × factorial(2)
factorial(2) → нужно 2 × factorial(1)
factorial(1) → базовый случай, return 1
factorial(2) → return 2 × 1 = 2
factorial(3) → return 3 × 2 = 6
factorial(4) → return 4 × 6 = 24Рекурсия vs итерация
Много задач можно решить обоими способами. Например, факториал можно вычислить цикло́м:
result = 1
for i from 2 to 4:
result = result × i
return resultЭто итеративно (используется цикл, функция не вызывает саму себя). Это использует меньше памяти (нет нескольких вызовов функции на стеке) и иногда быстрее. Но это менее интуитивно, когда задача естественно самоподобна — как обход деревьев, где каждый узел содержит меньшие поддеревья, или merge sort, что расщепляет массив пополам рекурсивно.
Рекурсия сияет, когда структура задачи отражает рекурсию: задача разбивается на меньшие копии самой себя. Деревья, графы, перестановки и алгоритмы разделяй-и-властвуй естественны для рекурсии.
Кодим рекурсию на JavaScript и строим интуицию с помощью двух примеров.
Пример 1: Факториал
function factorial(n) {
// Базовый случай: n <= 1 возвращает 1
if (n <= 1) {
return 1;
}
// Рекурсивный случай: n * factorial(n - 1)
return n * factorial(n - 1);
}
console.log(factorial(4)); // 24
console.log(factorial(5)); // 120Пример 2: Сумма целых чисел от 1 до n
Вместо цикла используй рекурсию:
function sumTo(n) {
// Базовый случай: сумма до 1 это 1
if (n <= 1) {
return 1;
}
// Рекурсивный случай: n + сумма всего ниже n
return n + sumTo(n - 1);
}
console.log(sumTo(5)); // 5 + 4 + 3 + 2 + 1 = 15
console.log(sumTo(10)); // 55Паттерн одинаков: базовый случай для самого маленького входа, рекурсивный случай, что сжимает вход и вызывает саму себя.
Попробуй обе функции:
Проследим factorial(4) шаг за шагом, показывая разворачивание рекурсивных вызовов.
1
function factorial(n) {
2
if (n <= 1) return 1;
3
return n * factorial(n - 1);
4
}
Время: Каждый рекурсивный вызов обрабатывает одно значение входа. Для factorial(n) есть n вызовов (от n вниз до 1), каждый делает постоянную работу (одно умножение и одно сравнение). Итого: O(n) время.
Место: Каждый вызов функции занимает место на стеке вызовов. Самая глубокая рекурсия идёт от n до 1, поэтому глубина стека O(n). Это означает O(n) памяти для стека.
Контрастируй это с итеративным цикло́м: O(n) время, но O(1) памяти. Рекурсия меняет память на ясность, когда задача естественно рекурсивна.
Правило большого пальца: Используй рекурсию, когда задача естественно разбивается на меньшие копии самой себя (деревья, графы, backtracking). Более чистая логика стоит дополнительной памяти стека — если только рекурсия не очень глубокая (сотни тысяч вызовов), что может переполнить стек.
Сколько рекурсивных вызовов происходит при вызове factorial(5)?
Что случится, если ты забудешь базовый случай?
В функции sumTo, что такое базовый случай?
Почему factorial(n) вызывает factorial(n - 1), а не factorial(n) снова?
Расставь шаги, что происходят при вызове factorial(3):
- factorial(3) вызывает factorial(2)
- factorial(2) вызывает factorial(1)
- factorial(1) попадает в базовый случай, возвращает 1
- factorial(2) получает 1, вычисляет 2 * 1 = 2, возвращает 2
- factorial(3) получает 2, вычисляет 3 * 2 = 6, возвращает 6
Частая ошибка
Ошибка: нет базового случая. Эта функция не имеет базового случая:
function badFactorial(n) {
return n * badFactorial(n - 1);
}Она вызывает себя бесконечно. Хотя n сжимается, нет условия остановки. В конце концов стек вызовов переполняется и программа падает. Каждая рекурсивная функция ДОЛЖНА иметь базовый случай.
Частая ошибка
Ошибка: вход не сжимается. Эта функция вызывает себя на том же входе:
function badLoop(n) {
if (n <= 0) return 1;
return badLoop(n); // БАГ: n не сжимается
}Хотя есть базовый случай, рекурсивный вызов передаёт тот же n, не n - 1. Базовый случай никогда не достигается (или только если вход уже ≤ 0). Рекурсивный случай должен сжимать вход.
Ты пишешь рекурсивную функцию, что считает вниз от n до 1. Что должно быть истинным?
Рекурсия — это когда функция вызывает саму себя для решения меньшей версии той же задачи.
Базовый случай: Самый маленький вход, что функция может обработать напрямую, без рекурсии. Пример: if (n <= 1) return 1;
Рекурсивный случай: Функция вызывает саму себя на меньшем входе, потом использует результат, чтобы построить ответ для текущего входа. Пример: return n * factorial(n - 1);
Оба обязательны: Нет базового случая → бесконечная рекурсия (падение). Вход не сжимается → бесконечная рекурсия (падение).
Рекурсивный прыжок веры: Доверься, что рекурсивный вызов возвращает правильный ответ для меньшего входа. Это позволяет тебе сосредоточиться на: «Дан ответ для n - 1, как я построю ответ для n?»
Рекурсия vs итерация: Обе могут решить ту же задачу. Итерация более экономна по памяти (нет дополнительного стека вызовов). Рекурсия более интуитивна для задач с рекурсивной структурой (деревья, графы, backtracking).
Почему рекурсия важна: Деревья естественно зовут рекурсию (каждое поддерево — меньшее дерево). Merge sort и quicksort проще понять рекурсивно. Backtracking исследует все пути, вызывая себя на каждом выборе. Следующие уроки учат стек вызовов, backtracking и обход деревьев — всё построено на этом основании.