Рекурсивные алгоритмы

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

Зачем нужно

Рекурсия позволяет элегантно решать задачи, которые естественно разбиваются на подзадачи: обход деревьев, сортировка (merge sort, quick sort), математические вычисления, работа с файловой системой. Многие алгоритмы невозможно или крайне сложно выразить без рекурсии.

Где используется

  • Обход деревьев (DOM, файловая система, JSON)
  • Алгоритмы сортировки (merge sort, quick sort)
  • Поиск в графах (DFS)
  • Математика (факториал, степень, числа Фибоначчи)
  • Генерация комбинаций и перестановок
  • Фракталы и визуализации

Предпосылки

Анатомия рекурсии

Каждая рекурсивная функция состоит из двух частей:

function recursive(input) {
  // 1. Базовый случай — условие ОСТАНОВКИ
  if (условие_остановки) {
    return результат;
  }

  // 2. Рекурсивный случай — вызов себя с МЕНЬШИМ входом
  return recursive(уменьшенный_input);
}

Если забыть базовый случай — бесконечная рекурсия → Maximum call stack size exceeded.

Примеры

Факториал

// n! = n × (n-1) × (n-2) × ... × 1
// 5! = 5 × 4 × 3 × 2 × 1 = 120

function factorial(n) {
  // Базовый случай
  if (n <= 1) return 1;

  // Рекурсивный случай
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 120

// Разворачивание вызовов:
// factorial(5)
//   5 * factorial(4)
//     4 * factorial(3)
//       3 * factorial(2)
//         2 * factorial(1)
//           return 1        ← базовый случай
//         return 2 * 1 = 2
//       return 3 * 2 = 6
//     return 4 * 6 = 24
//   return 5 * 24 = 120

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

// fib(0)=0, fib(1)=1, fib(n) = fib(n-1) + fib(n-2)
// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

// Наивная рекурсия — O(2^n), очень медленно!
function fibNaive(n) {
  if (n <= 1) return n;
  return fibNaive(n - 1) + fibNaive(n - 2);
}

// С мемоизацией — O(n), каждое значение считается один раз
function fibonacci(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];

  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  return memo[n];
}

console.log(fibonacci(50)); // 12586269025 (мгновенно!)

Степень числа

// Наивно: O(n)
function power(base, exp) {
  if (exp === 0) return 1;
  return base * power(base, exp - 1);
}

// Быстрое возведение: O(log n)
function fastPower(base, exp) {
  if (exp === 0) return 1;
  if (exp % 2 === 0) {
    const half = fastPower(base, exp / 2);
    return half * half; // x^n = (x^(n/2))^2
  }
  return base * fastPower(base, exp - 1);
}

console.log(fastPower(2, 10)); // 1024

Call Stack (стек вызовов)

Каждый вызов функции создаёт фрейм в стеке вызовов:

factorial(4) вызывает:

Стек:
┌────────────────┐
│ factorial(1)   │ ← текущий (вершина стека)
├────────────────┤
│ factorial(2)   │
├────────────────┤
│ factorial(3)   │
├────────────────┤
│ factorial(4)   │ ← первый вызов (дно стека)
└────────────────┘

После return 1:
┌────────────────┐
│ factorial(2)   │ ← return 2 * 1
├────────────────┤
│ factorial(3)   │
├────────────────┤
│ factorial(4)   │
└────────────────┘

Стек имеет ограниченный размер (~10 000-15 000 фреймов в V8). Глубокая рекурсия → RangeError: Maximum call stack size exceeded.

// Переполнение стека
function infinite() {
  return infinite; // бесконечная рекурсия
}
// RangeError: Maximum call stack size exceeded

// Слишком глубокая рекурсия
function deepRecursion(n) {
  if (n === 0) return 0;
  return deepRecursion(n - 1);
}
deepRecursion(100000); // может упасть

Обход деревьев

Рекурсия идеально подходит для деревьев, потому что дерево — рекурсивная структура (каждое поддерево — тоже дерево).

// Обход дерева объектов (например, файловая система)
const fileSystem = {
  name: 'root',
  children: [
    {
      name: 'src',
      children: [
        { name: 'index.js', children:  },
        { name: 'app.js', children:  },
      ]
    },
    {
      name: 'package.json',
      children: 
    }
  ]
};

// Рекурсивный обход: вывести все файлы
function listFiles(node, indent = '') {
  console.log(indent + node.name);
  for (const child of node.children) {
    listFiles(child, indent + '  ');
  }
}

listFiles(fileSystem);
// root
//   src
//     index.js
//     app.js
//   package.json

// Глубокое копирование объекта (deep clone)
function deepClone(obj) {
  if (obj === null || typeof obj !== 'object') {
    return obj; // базовый случай: примитив
  }

  if (Array.isArray(obj)) {
    return obj.map(item => deepClone(item));
  }

  const clone = {};
  for (const key of Object.keys(obj)) {
    clone[key] = deepClone(obj[key]); // рекурсия
  }
  return clone;
}

// Глубокий поиск значения в вложенном объекте
function deepFind(obj, predicate) {
  if (predicate(obj)) return obj;

  if (typeof obj === 'object' && obj !== null) {
    for (const value of Object.values(obj)) {
      const found = deepFind(value, predicate);
      if (found !== undefined) return found;
    }
  }

  return undefined;
}

const data = { a: { b: { c: 42 } } };
console.log(deepFind(data, v => v === 42)); // 42

Рекурсия vs Итерация

Любую рекурсию можно переписать в цикл (и наоборот).

// Факториал: рекурсия
function factorialRec(n) {
  if (n <= 1) return 1;
  return n * factorialRec(n - 1);
}

// Факториал: итерация
function factorialIter(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}
// Итерация: O(1) памяти (нет стека), немного быстрее
Аспект Рекурсия Итерация
Читаемость Часто лучше для деревьев Часто лучше для линейных задач
Память O(n) стек вызовов O(1)
Производительность Overhead вызовов Быстрее
Переполнение стека Возможно Нет

Tail Recursion (хвостовая рекурсия)

Рекурсивный вызов — последняя операция в функции. Теоретически может быть оптимизирован движком (TCO), но V8 пока не поддерживает TCO.

// НЕ хвостовая рекурсия: return n * factorial(n-1)
// Нужно умножить ПОСЛЕ возврата

// Хвостовая рекурсия: return factorial(n-1, acc * n)
// Рекурсивный вызов — ПОСЛЕДНЯЯ операция
function factorialTail(n, accumulator = 1) {
  if (n <= 1) return accumulator;
  return factorialTail(n - 1, accumulator * n);
}

// Можно безопасно переписать в цикл (trampoline)
function trampoline(fn) {
  return function(...args) {
    let result = fn(...args);
    while (typeof result === 'function') {
      result = result;
    }
    return result;
  };
}

Частые ошибки

  1. Забыть базовый случай. Бесконечная рекурсия → crash
  2. Не уменьшать вход. Каждый рекурсивный вызов должен приближаться к базовому случаю
  3. Не использовать мемоизацию. Наивный Fibonacci O(2^n) → с memo O(n)
  4. Использовать рекурсию для линейных задач. Сумма массива лучше решается циклом

Практика

  1. Реализуйте sumArray(arr) рекурсивно: сумма = первый + сумма остальных
  2. Реализуйте flatten(arr) — разворачивание вложенных массивов:
    function flatten(arr) {
  const result = ;
  for (const item of arr) {
    if (Array.isArray(item)) {
      result.push(...flatten(item));
    } else {
      result.push(item);
    }
  }
  return result;
}
flatten([1, [2, [3, [4]], 5]]); // [1, 2, 3, 4, 5]
  3. Реализуйте isPalindrome(str) рекурсивно

Связанные темы

Ресурсы