Рекурсия

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

Зачем нужно

Рекурсия естественно решает задачи с рекурсивной структурой: обход деревьев, вложенные структуры данных, задачи «разделяй и властвуй». Многие алгоритмы (quicksort, mergesort, обход DOM) проще и понятнее в рекурсивной форме.

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

Обход деревьев (DOM, файловая система, JSON), сортировки, поиск путей, фракталы, парсинг вложенных структур, глубокое клонирование, flatMap.

Предпосылки

Function Declaration, Замыкания (Closures)

Структура рекурсии

function recursive(input) {
  // 1. Базовый случай (условие выхода)
  if (условие_выхода) {
    return результат;
  }

  // 2. Рекурсивный случай (уменьшение задачи + вызов себя)
  return recursive(уменьшенный_input);
}

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

Факториал

function factorial(n) {
  // Базовый случай
  if (n <= 1) return 1;
  // Рекурсивный случай
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 120
// 5 * 4 * 3 * 2 * 1 = 120

// Стек вызовов:
// factorial(5) → 5 * factorial(4)
//   factorial(4) → 4 * factorial(3)
//     factorial(3) → 3 * factorial(2)
//       factorial(2) → 2 * factorial(1)
//         factorial(1) → 1 (базовый случай)
//       → 2 * 1 = 2
//     → 3 * 2 = 6
//   → 4 * 6 = 24
// → 5 * 24 = 120

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

// Наивная реализация — O(2^n)
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

console.log(fib(10)); // 55

// Оптимизированная с мемоизацией — O(n)
function fibMemo(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

console.log(fibMemo(50)); // 12586269025 — мгновенно

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

function power(base, exp) {
  if (exp === 0) return 1;
  if (exp < 0) return 1 / power(base, -exp);
  return base * power(base, exp - 1);
}

console.log(power(2, 10)); // 1024
console.log(power(3, 0));  // 1

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

DOM-дерево

function walkDOM(node, callback) {
  callback(node);
  node = node.firstElementChild;
  while (node) {
    walkDOM(node, callback); // рекурсия для каждого дочернего
    node = node.nextElementSibling;
  }
}

// Найти все текстовые узлы
walkDOM(document.body, (node) => {
  if (node.nodeType === Node.TEXT_NODE) {
    console.log(node.textContent.trim());
  }
});

Произвольное дерево

const fileSystem = {
  name: 'root',
  children: [
    {
      name: 'src',
      children: [
        { name: 'index.js', children:  },
        { name: 'utils.js', children:  },
        {
          name: 'components',
          children: [
            { name: 'App.jsx', children:  },
            { name: 'Header.jsx', children:  },
          ]
        }
      ]
    },
    { name: 'package.json', children:  },
  ]
};

function findFile(node, fileName) {
  if (node.name === fileName) return node;
  for (const child of node.children) {
    const found = findFile(child, fileName);
    if (found) return found;
  }
  return null;
}

console.log(findFile(fileSystem, 'App.jsx'));
// { name: 'App.jsx', children:  }

Отображение дерева

function printTree(node, prefix = '', isLast = true) {
  const connector = isLast ? '└── ' : '├── ';
  console.log(prefix + connector + node.name);

  const newPrefix = prefix + (isLast ? '    ' : '│   ');
  const children = node.children || ;
  children.forEach((child, i) => {
    printTree(child, newPrefix, i === children.length - 1);
  });
}

printTree(fileSystem);
// └── root
//     ├── src
//     │   ├── index.js
//     │   ├── utils.js
//     │   └── components
//     │       ├── App.jsx
//     │       └── Header.jsx
//     └── package.json

Глубокое клонирование

function deepClone(obj) {
  // Базовые случаи
  if (obj === null || typeof obj !== 'object') return obj;
  if (obj instanceof Date) return new Date(obj.getTime());
  if (obj instanceof RegExp) return new RegExp(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;
}

const original = {
  name: 'Иван',
  settings: { theme: 'dark', nested: { level: 3 } },
  tags: ['js', 'react']
};

const copy = deepClone(original);
copy.settings.theme = 'light';
console.log(original.settings.theme); // 'dark' — оригинал не изменился

Выравнивание массивов (flat)

function flatten(arr) {
  const result = ;
  for (const item of arr) {
    if (Array.isArray(item)) {
      result.push(...flatten(item)); // рекурсия для вложенных
    } else {
      result.push(item);
    }
  }
  return result;
}

console.log(flatten([1, [2, [3, [4]], 5], 6]));
// [1, 2, 3, 4, 5, 6]

Stack Overflow (переполнение стека)

// Каждый вызов добавляет фрейм в стек
function infiniteRecursion() {
  return infiniteRecursion; // нет базового случая!
}
// infiniteRecursion; // RangeError: Maximum call stack size exceeded

// Типичный лимит стека: ~10000-25000 вызовов
function countStack(n = 0) {
  try {
    return countStack(n + 1);
  } catch (e) {
    return n;
  }
}
console.log(countStack); // ~10000+ (зависит от движка)

Tail Call Optimization (TCO)

Хвостовая рекурсия — рекурсивный вызов является последней операцией:

// НЕ хвостовая рекурсия — после рекурсии ещё операция (умножение)
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1); // нужен результат для умножения
}

// Хвостовая рекурсия — рекурсия последняя операция
function factorialTail(n, acc = 1) {
  if (n <= 1) return acc;
  return factorialTail(n - 1, acc * n); // последняя операция
}

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

Внимание: TCO поддерживается только в Safari. V8 (Chrome, Node.js) НЕ оптимизирует хвостовую рекурсию.

Trampoline — обход лимита стека

function trampoline(fn) {
  return function(...args) {
    let result = fn(...args);
    while (typeof result === 'function') {
      result = result;
    }
    return result;
  };
}

function factorialTramp(n, acc = 1) {
  if (n <= 1) return acc;
  return  => factorialTramp(n - 1, acc * n); // возвращает функцию, не вызов
}

const safeFact = trampoline(factorialTramp);
console.log(safeFact(100000)); // Infinity, но без stack overflow

Итеративная vs рекурсивная

// Рекурсивная сумма массива
function sumRecursive(arr) {
  if (arr.length === 0) return 0;
  return arr[0] + sumRecursive(arr.slice(1));
}

// Итеративная сумма — эффективнее
function sumIterative(arr) {
  let total = 0;
  for (const num of arr) total += num;
  return total;
}

// Используй рекурсию когда:
// - Структура данных рекурсивная (деревья, графы)
// - Задача естественно делится на подзадачи
// - Глубина вложенности небольшая

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

1. Забытый базовый случай

// Бесконечная рекурсия → Stack Overflow
function oops(n) {
  return oops(n - 1); // нет проверки n <= 0
}

2. Базовый случай не достигается

function countdown(n) {
  if (n === 0) return; // базовый случай
  console.log(n);
  countdown(n - 2); // если n нечётное, пропустит 0!
}
// countdown(5); // 5, 3, 1, -1, -3... → stack overflow

// Исправление:
function countdownFixed(n) {
  if (n <= 0) return; // <= вместо ===
  console.log(n);
  countdownFixed(n - 2);
}

3. Неэффективная рекурсия без мемоизации

// fib(40) — миллионы повторных вычислений
// Всегда используй мемоизацию для перекрывающихся подзадач

Практика

Напиши рекурсивную функцию суммы вложенного массива: [1, [2, [3, 4]], 5] → 15
Реализуй рекурсивный поиск по вложенному объекту (findValue)
Напиши функцию deepFreeze(obj), рекурсивно замораживающую объект
Реализуй бинарный поиск рекурсивно
Напиши trampoline-версию подсчёта чисел Фибоначчи