Рекурсия: Когда функция зовёт саму себя. От факториала до фракталов

Представьте зеркало, поставленное напротив зеркала, где отражения уходят в бесконечность. Или матрёшку, внутри которой скрывается такая же, только меньше. Это и есть рекурсия в жизни — явление, когда объект частично состоит из самого себя или определяется через себя. В программировании рекурсия — это мощнейший инструмент, позволяющий элегантно решать сложные задачи, разбивая их на более простые подзадачи того же типа. Это не просто технический приём, а особый образ мышления.

Что такое рекурсия? Суть в одном предложении

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

Классические примеры рекурсии в коде

Давайте рассмотрим примеры, которые показывают красоту и логику рекурсивного подхода.

1. Вычисление факториала

Факториал числа n (n!) — произведение всех целых чисел от 1 до n. Его можно определить рекурсивно: n! = n * (n-1)!, а 0! = 1.

function factorial(n) {
  if (n === 0) { // Базовое условие
    return 1;
  } else {
    return n * factorial(n - 1); // Рекурсивный вызов
  }
}
console.log(factorial(5)); // 120

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

Последовательность, где каждое следующее число равно сумме двух предыдущих: 0, 1, 1, 2, 3, 5, 8... Классический, но неэффективный пример (из-за экспоненциальной сложности), который отлично иллюстрирует идею.

function fibonacci(n) {
  if (n < 2) { // Базовые условия: F(0)=0, F(1)=1
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2); // Два рекурсивных вызова
}
console.log(fibonacci(6)); // 8

3. Обход дерева (каталогов файловой системы)

Это, пожалуй, самое практичное применение. Рекурсия идеально подходит для работы с древовидными структурами.

function traverseDirectory(dir) {
  for (let item of dir.items) {
    if (item.isFile) {
      console.log('Файл:', item.name);
    } else if (item.isDirectory) {
      console.log('Каталог:', item.name);
      traverseDirectory(item); // Рекурсивный обход подкаталога
    }
  }
}

Прямая и хвостовая рекурсия

Рекурсия бывает разной. В прямой (как в примерах выше) функция совершает дополнительные операции (умножение, сложение) после рекурсивного вызова. В хвостовой рекурсии вызов функции является последней операцией. Это важно для оптимизации (оптимизация хвостовой рекурсии), которую некоторые компиляторы выполняют, экономя память стека.

// Хвостовая рекурсия для факториала (с аккумулятором)
function factorialTail(n, accumulator = 1) {
  if (n === 0) return accumulator;
  return factorialTail(n - 1, n * accumulator); // Хвостовой вызов
}

Рекурсия в реальном мире: не только код

• Фракталы (снежинка Коха, множество Мандельброта) — геометрические фигуры, части которых подобны целому.
• Синтаксический разбор в компиляторах (например, разбор арифметических выражений).
• Алгоритмы сортировки (быстрая сортировка, сортировка слиянием).
• Задачи с возвратом (backtracking), например, прохождение лабиринта или расстановка ферзей на шахматной доске.

FAQ: Часто задаваемые вопросы о рекурсии

Чем рекурсия лучше циклов?

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

Когда стоит избегать рекурсии?

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

Что такое переполнение стека?

Это ошибка (Stack Overflow), возникающая, когда рекурсивных вызовов становится слишком много, и память, выделенная под стек вызовов, исчерпывается. Часто из-за отсутствия или ошибки в базовом условии.

Всегда ли можно заменить рекурсию циклом?

Да, теоретически всегда. Для этого часто используется структура данных — стек, которая явно имитирует работу стека вызовов. Однако такая реализация может быть менее наглядной.

С чего начать практику?

1. Напишите рекурсивную функцию для суммы чисел от 1 до n.
2. Реализуйте алгоритм бинарного поиска рекурсивно.
3. Напишите функцию для вычисления глубины дерева.
4. Решите задачу о Ханойских башнях.

Рекурсия — это мост между математическим определением и программной реализацией. Освоив её, вы получаете не просто ещё один инструмент, а новый способ декомпозиции проблем, который открывает двери к пониманию сложных алгоритмов и структур данных.