Рекурсия

Рекурсия — это когда функция вызывает саму себя. Звучит странно? На самом деле это элегантный способ решать задачи, которые по природе своей «вложенные»: деревья, вложенные папки, математические последовательности. Но главное — понять два обязательных условия, без которых рекурсия превращается в бесконечный цикл.

🌀 Что такое рекурсия?

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

Аналогия из жизни: чтобы пересчитать, сколько людей в большой очереди, можно сказать: «Я первый, плюс сколько людей за мной». А человек за мной скажет: «Я первый за тобой, плюс сколько людей за мной». И так пока не дойдём до последнего, который скажет: «Я один — счёт равен 1». Это и есть рекурсия.

📋 Два обязательных условия рекурсии

Любая правильная рекурсивная функция обязательно содержит оба условия:

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

Факториал числа n (записывается n!) — это произведение всех натуральных чисел от 1 до n. Например: 5! = 5 × 4 × 3 × 2 × 1 = 120. По определению: 0! = 1 и 1! = 1.

Замечаем: 5! = 5 × 4!, а 4! = 4 × 3!, и так далее. Задача сводится к самой себе — это рекурсивная структура!

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

  // Рекурсивный вызов: n! = n × (n-1)!
  return n * factorial(n - 1);
}

console.log(factorial(0)); // 1
console.log(factorial(1)); // 1
console.log(factorial(5)); // 120
console.log(factorial(10)); // 3628800

Давайте пошагово проследим, что происходит при вызове factorial(4):

Функция «уходит вглубь», пока не достигает базового случая, а потом «поднимается обратно», собирая результаты.

🏗️ Стек вызовов: что происходит под капотом

Каждый вызов функции в JavaScript добавляет фрейм в стек вызовов (call stack). Стек — это структура «последний зашёл — первый вышел» (как стопка тарелок). При рекурсии каждый вызов ждёт, пока вернётся вложенный.

// При factorial(4) стек выглядит так:
// [factorial(4)] ← первый вызов
// [factorial(4), factorial(3)] ← второй вызов
// [factorial(4), factorial(3), factorial(2)] ← третий вызов
// [factorial(4), factorial(3), factorial(2), factorial(1)] ← базовый случай
// ← factorial(1) вернул 1, убирается из стека
// [factorial(4), factorial(3), factorial(2)] ← factorial(2) получил 1
// [factorial(4), factorial(3)] ← factorial(3) получил 2
// [factorial(4)] ← factorial(4) получил 6
// [] ← factorial(4) вернул 24, стек пуст

💥 Stack Overflow: когда рекурсия бесконечна

Если рекурсия никогда не достигает базового случая — стек вызовов переполняется. Это называется Stack Overflow (переполнение стека). JavaScript выбросит ошибку: RangeError: Maximum call stack size exceeded.

// ❌ Нет базового случая — бесконечная рекурсия
function countdown(n) {
  console.log(n);
  countdown(n - 1); // никогда не остановится!
}
countdown(5); // RangeError: Maximum call stack size exceeded

// ❌ Аргумент не меняется — никогда не достигнем базы
function broken(n) {
  if (n <= 0) return 0;
  return broken(n); // n не уменьшается! Бесконечный цикл.
}

// ✅ Правильно: аргумент уменьшается, есть базовый случай
function countdown(n) {
  if (n <= 0) {
    console.log("Старт!");
    return;
  }
  console.log(n);
  countdown(n - 1); // n уменьшается
}
countdown(5); // 5, 4, 3, 2, 1, Старт!

🐇 Пример 2: Числа Фибоначчи

Числа Фибоначчи: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34... Каждое число — сумма двух предыдущих. Определение само по себе рекурсивное: fib(n) = fib(n-1) + fib(n-2).

function fibonacci(n) {
  // Базовые случаи: fib(0) = 0, fib(1) = 1
  if (n === 0) return 0;
  if (n === 1) return 1;

  // Рекурсивный вызов: fib(n) = fib(n-1) + fib(n-2)
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(0));  // 0
console.log(fibonacci(1));  // 1
console.log(fibonacci(5));  // 5
console.log(fibonacci(10)); // 55

⚖️ Рекурсия vs цикл: когда что использовать?

Любую рекурсию можно переписать через цикл и наоборот. Так когда же рекурсия лучше?

// Факториал через цикл (итеративно):
function factorialLoop(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

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

// Для факториала цикл эффективнее — рекурсия здесь просто для обучения

Рассмотрим пример, где рекурсия действительно блистает — обход вложенного объекта (дерева):

// Подсчёт суммы всех вложенных чисел в дереве объектов
function sumTree(node) {
  // Базовый случай: если это число — вернуть его
  if (typeof node === "number") {
    return node;
  }

  // Рекурсивный случай: если объект — суммировать все дочерние узлы
  let total = 0;
  for (let key in node) {
    total += sumTree(node[key]); // рекурсивный вызов для каждой ветки
  }
  return total;
}

let tree = {
  value: 5,
  left: {
    value: 3,
    left: 1,
    right: 2
  },
  right: {
    value: 8,
    left: 4,
    right: {
      value: 7,
      left: 6,
      right: 9
    }
  }
};

console.log(sumTree(tree)); // 45

// Попробуйте написать это через цикл — это будет очень сложно!

🌳 Практический пример: обход вложенных папок

Представьте файловую систему: папки могут содержать другие папки. Рекурсия позволяет обойти всё дерево независимо от глубины вложенности:

const fileSystem = {
  name: "root",
  type: "folder",
  children: [
    { name: "document.txt", type: "file" },
    {
      name: "photos",
      type: "folder",
      children: [
        { name: "vacation.jpg", type: "file" },
        { name: "party.jpg", type: "file" },
        {
          name: "2024",
          type: "folder",
          children: [
            { name: "new_year.jpg", type: "file" }
          ]
        }
      ]
    },
    {
      name: "work",
      type: "folder",
      children: [
        { name: "report.pdf", type: "file" }
      ]
    }
  ]
};

function listFiles(node, indent = 0) {
  let prefix = "  ".repeat(indent);

  if (node.type === "file") {
    // Базовый случай: файл
    console.log(prefix + "📄 " + node.name);
    return;
  }

  // Рекурсивный случай: папка
  console.log(prefix + "📁 " + node.name);
  for (let child of node.children) {
    listFiles(child, indent + 1); // уровень вложенности увеличивается
  }
}

listFiles(fileSystem);
// 📁 root
//   📄 document.txt
//   📁 photos
//     📄 vacation.jpg
//     📄 party.jpg
//     📁 2024
//       📄 new_year.jpg
//   📁 work
//     📄 report.pdf

Попробуйте написать это без рекурсии — задача резко усложнится, потому что нужно вручную поддерживать стек состояний. Рекурсия делает это автоматически через стек вызовов.

✅ Итоги урока

• Рекурсия — функция, которая вызывает саму себя для решения подзадачи
• Два обязательных условия: базовый случай (когда остановиться) и рекурсивный вызов с изменённым аргументом
• Аргумент при рекурсивном вызове должен становиться ближе к базовому случаю
• Stack Overflow — переполнение стека при бесконечной рекурсии (без базового случая)
• Каждый вызов добавляет фрейм в стек вызовов; базовый случай «разматывает» стек обратно
• Рекурсия лучше цикла для деревьев, графов и вложенных структур
• Для простых линейных задач (факториал, сумма) — цикл эффективнее