Рекурсия

Рекурсия: как это работает?

Найдите наименьший случай, на который можно ответить без работы. Это и есть базовый случай.

Считайте, что функция уже работает на меньшем входе. Ей доверяют, а не прослеживают её.

Напишите один шаг, уменьшающий задачу. Потом вызовите себя на остатке.

Соедините вернувшийся результат с этим одним шагом. Эти две строки и есть всё тело.

Каждый вызов занимает кадр памяти. Глубина n значит n живых кадров одновременно.

Без базового случая вызовы не кончаются. Стек заполняется и программа падает.

1. sum([2, 4, 6])Список не пуст. Берём двойку и спрашиваем про остаток.
2. sum([4, 6])Берём четвёрку и спрашиваем снова. Список продолжает уменьшаться.
3. sum([6])Остался один элемент. Это всё ещё не базовый случай.
4. sum([]) = 0Пустой список это базовый случай. Он отвечает без работы.
5. 0, 6, 10, 12Результаты разворачиваются наверх. Каждый вызов добавляет своё значение.

function recurse(n) {
    if (n <= 0) return 0; // base case
    return n + recurse(n - 1); // recursive case: smaller subproblem
}

Рекурсия: разбор примера

Развернуть вложенный массив

Дан массив, элементы которого это числа или другие массивы. Верните один плоский массив чисел.

Вложенность бывает любой глубины.

Число это базовый случай, оно возвращается как есть.

Массив это меньшая задача: разверните каждый элемент и склейте куски. Глубина разбирается сама.

function flatten(items) {
    const result = [];

    for (const item of items) {
        if (Array.isArray(item)) {
            // trust the call to handle every depth below this one
            result.push(...flatten(item));
        } else {
            result.push(item);
        }
    }

    return result;
}

Рекурсия: когда применять?

Эти формулировки в условии ведут сюда:

• •задача определена через меньшую версию самой себя
• •вложенная/древовидная структура для обхода (папки, выражение, связный список)
• •нужно посчитать сумму/количество/глубину по всем подэлементам
• •естественное деление на базовый случай и рекурсивный (факториал, Фибоначчи, глубина дерева)

Рекурсия: с чем путают?

• Рекурсия с мемоизацией (Recursion with memoization): Мемоизация это то же самое плюс кеш прошлых ответов. Она нужна, когда аргумент повторяется.
• Бэктрекинг (Backtracking): Бэктрекинг отменяет выбор после того, как его исследовал. Обычная рекурсия ничего не отменяет.
• Стек (LIFO) (Stack (LIFO)): Стек вызовов это стек, который вы не писали. Свой стек снимает ограничение по глубине.
• Обход дерева (Tree traversal): На деревьях рекурсия дешевле и понятнее всего. Та страница про три порядка посещения.

Рекурсия: частые ошибки

• Базового случая нет или он неверный

  Тогда вызовы идут, пока не заполнится стек. Пишите базовый случай раньше всего остального.

• Вход не уменьшается

  Каждый вызов обязан приближать к базовому случаю. Тот же аргумент даёт бесконечный цикл.

• Уходят слишком глубоко

  Списку из миллиона узлов нужен миллион кадров. Такое переписывают циклом.

• Делят один изменяемый массив между вызовами

  Вложенный вызов может испортить то, что нужно родителю. Копируйте или откатывайте изменение на выходе.

Рекурсия: задачи с собеседований

• Факториал и числа Фибоначчи: Классическая форма, хотя Фибоначчи требует кеша.
• Разворот строки: Поменяйте концы местами и спуститесь в середину.
• Разворачивание вложенного списка: Базовый случай это обычное значение.
• Слияние двух отсортированных списков: Возьмите меньшую голову и спуститесь в остаток.
• Возведение в степень: Делите показатель пополам вместо вычитания единицы.
• Ханойские башни: Два меньших перемещения вокруг одного прямого.
• Глубина двоичного дерева: Единица плюс более глубокий из двух потомков.

Рекурсия: сложность по времени и памяти

O(n)

Глубина примерно до 10000 в браузере безопасна. Глубже стоит переписать рекурсию циклом.