Урок 07

Рекурсия

Рекурсия — вызов функцией самой себя. Полезно для обхода древовидных структур, вычислений с повторяющимся шаблоном.

Базовый пример

Факториал:

function factorial(n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

factorial(5); // 120

База и шаг

Любая рекурсия имеет:

  1. Базовый случай — условие остановки
  2. Рекурсивный шаг — вызов себя с меньшей задачей

Без базы — бесконечная рекурсия и RangeError: Maximum call stack size exceeded.

Числа Фибоначчи

function fib(n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

fib(10); // 55

Медленно — много повторных вычислений. С мемоизацией быстрее:

function fibMemo() {
    const cache = new Map();

    return function fib(n) {
        if (n <= 1) return n;
        if (cache.has(n)) return cache.get(n);

        const result = fib(n - 1) + fib(n - 2);
        cache.set(n, result);
        return result;
    };
}

Обход дерева

function sumTree(node) {
    let total = node.value;

    for (const child of node.children ?? []) {
        total += sumTree(child);
    }

    return total;
}

const tree = {
    value: 1,
    children: [
        { value: 2, children: [{ value: 4 }] },
        { value: 3 },
    ],
};

sumTree(tree); // 10

Глубокая копия

function deepClone(value) {
    if (value === null || typeof value !== 'object') {
        return value;
    }

    if (Array.isArray(value)) {
        return value.map(deepClone);
    }

    const result = {};
    for (const [key, v] of Object.entries(value)) {
        result[key] = deepClone(v);
    }
    return result;
}

Сейчас есть structuredClone:

structuredClone(value);

Вложенный поиск

function findInTree(node, predicate) {
    if (predicate(node)) return node;

    for (const child of node.children ?? []) {
        const found = findInTree(child, predicate);
        if (found) return found;
    }

    return null;
}

Взаимная рекурсия

Две функции вызывают друг друга:

function isEven(n) {
    if (n === 0) return true;
    return isOdd(n - 1);
}

function isOdd(n) {
    if (n === 0) return false;
    return isEven(n - 1);
}

Хвостовая рекурсия

Рекурсивный вызов — последнее действие:

function factorialTail(n, acc = 1) {
    if (n <= 1) return acc;
    return factorialTail(n - 1, n * acc);
}

В некоторых языках оптимизируется. В JavaScript — не оптимизируется (кроме Safari). Всё равно может упасть на глубокой рекурсии.

Стек вызовов

Каждый рекурсивный вызов добавляет фрейм в стек. Глубина стека ограничена (~10000–15000).

function countdown(n) {
    if (n <= 0) return;
    countdown(n - 1);
}

countdown(100000); // RangeError

Решение — итерация:

function countdown(n) {
    while (n > 0) n--;
}

Когда использовать

  • Обход дерева, графа, вложенных структур
  • Разбор выражений (парсеры)
  • Задачи, которые естественно рекурсивны
  • Когда глубина небольшая

Когда не использовать

  • Простой цикл справится
  • Глубина может быть большой
  • Важна производительность

Итоги

  • Рекурсия — вызов себя
  • База + шаг
  • Без базы — переполнение стека
  • Мемоизация ускоряет
  • Идеально для деревьев
  • Стек ограничен — для глубоких задач итерация