Как работает рекурсия?

Как работает рекурсия

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

Базовая концепция

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

1. Базовый случай (base case) — условие, при котором рекурсия прекращается
2. Рекурсивный случай — функция вызывает саму себя с изменённым аргументом

Пример 1: Факториал

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

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

Как это работает в памяти

Когда функция вызывает саму себя, JavaScript создаёт новый фрейм вызова в call stack (стек вызовов). Каждый вызов функции добавляет новый фрейм на стек, а когда функция возвращает значение, фрейм удаляется.

Пример 2: Обход вложенного объекта

Рекурсия очень полезна для работы с вложенными структурами:

const menu = {
  name: "Главное меню",
  items: [
    { name: "Главная" },
    {
      name: "Услуги",
      items: [
        { name: "Разработка" },
        { name: "Дизайн" }
      ]
    }
  ]
};

function printMenu(item, indent = 0) {
  const padding = " ".repeat(indent);
  
  if (!item.items || item.items.length === 0) {
    console.log(padding + item.name);
    return;
  }
  
  console.log(padding + item.name);
  item.items.forEach(subitem => {
    printMenu(subitem, indent + 2);
  });
}

printMenu(menu);

Пример 3: Поиск в дереве

const tree = {
  id: 1,
  name: "root",
  children: [
    {
      id: 2,
      name: "child-1",
      children: [
        { id: 4, name: "grandchild-1" },
        { id: 5, name: "grandchild-2" }
      ]
    }
  ]
};

function findNodeById(node, targetId) {
  if (node.id === targetId) {
    return node;
  }
  
  if (!node.children || node.children.length === 0) {
    return null;
  }
  
  for (const child of node.children) {
    const result = findNodeById(child, targetId);
    if (result) return result;
  }
  
  return null;
}

console.log(findNodeById(tree, 5));

Проблемы и оптимизация

Проблема: Stack Overflow Глубокая рекурсия заполняет call stack и может вызвать ошибку RangeError.

Решение 1: Увеличить базовый случай

function safeRecursion(n) {
  if (n > 10000) return;
  return safeRecursion(n + 1);
}

Решение 2: Tail call optimization (TCO)

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

Решение 3: Итеративный подход

function factorialIterative(n) {
  let result = 1;
  for (let i = n; i > 1; i--) {
    result *= i;
  }
  return result;
}

Когда использовать рекурсию

Успешно использовать рекурсию стоит для:

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

Избегать рекурсию стоит при:

• Простых циклах (вопрос перфоманса)
• Очень глубоких структурах (риск stack overflow)
• Отсутствии явного базового случая

Рекурсия — мощный инструмент, но требует аккуратности и понимания, как работает стек вызовов.