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

Навигация по статье

Определение рекурсии в общем виде

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

Для создания рекурсивной функции в JavaScript вам понадобятся две вещи: базовый случай и рекурсивный случай.

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

Общая структура рекурсивной функции выглядит так:

function recursiveFunction(parameters) {
  // Проверяем базовый случай
  if (baseCase) {
    // Возвращаем результат базового случая
  }
  
  // Выполняем операции для текущего шага
  
  // Рекурсивно вызываем функцию с измененными параметрами
  recursiveFunction(modifiedParameters);
}

Важно обеспечить прогресс к базовому случаю, чтобы избежать зацикливания и бесконечной рекурсии.

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

Рассмотрим задачу вычисления факториала числа. Факториал числа N обозначается как N!, и представляет собой произведение всех целых чисел от 1 до N. Например, 5! равно 5 * 4 * 3 * 2 * 1, то есть 120.

function factorial(n) {
  // Базовый случай: факториал 0 равен 1
  if (n === 0) {
    return 1;
  }
  
  // Рекурсивный случай: вызываем функцию с меньшим значением
  return n * factorial(n - 1);
}

console.log(factorial(5)); // Выводит 120

В этом примере функция factorial вызывает саму себя с аргументом, меньшим на единицу. Когда значение аргумента становится равным 0, функция возвращает 1, что является базовым случаем выхода из рекурсии. Затем значения факториала умножаются друг на друга на каждом шаге рекурсии, пока не будет достигнут базовый случай.

Пример 2: Обход дерева

Рассмотрим пример обхода дерева, который имеет следующую структуру:

{
  value: 'A',
  children: [
    {
      value: 'B',
      children: [
        {
          value: 'C',
          children: []
        },
        {
          value: 'D',
          children: []
        }
      ]
    },
    {
      value: 'E',
      children: []
    }
  ]
}

Мы можем использовать рекурсию для обхода этого дерева и вывода всех его значений:

function traverseTree(node) {
  console.log(node.value); // Выводим значение текущего узла
  
  node.children.forEach(child => {
    traverseTree(child); // Рекурсивно вызываем функцию для каждого дочернего узла
  });
}

const tree = {
  value: 'A',
  children: [
    {
      value: 'B',
      children: [
        {
          value: 'C',
          children: []
        },
        {
          value: 'D',
          children: []
        }
      ]
    },
    {
      value: 'E',
      children: []
    }
  ]
};

traverseTree(tree); // Выводит 'A', 'B', 'C', 'D', 'E'

Функция traverseTree принимает узел дерева и выводит его значение. Затем она рекурсивно вызывает себя для каждого дочернего узла этого узла, пока не будут пройдены все узлы дерева.

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

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

Обработка и структурирование данных: Рекурсия может использоваться для обхода и обработки сложных структур данных, таких как деревья, графы или связанные списки. Например, рекурсия может использоваться для обхода дерева каталогов и файловой системы, поиска пути в графе или перебора элементов связанного списка.
Работа с рекурсивными алгоритмами: Многие алгоритмы могут быть определены рекурсивно и легче понять и реализовать с использованием рекурсии. Например, сортировка слиянием, быстрая сортировка, алгоритмы поиска и обхода графов и другие алгоритмы могут быть реализованы с помощью рекурсии.
Работа с задачами, разбиваемыми на подзадачи: Когда сложная задача может быть разбита на более простые подзадачи, рекурсия может быть полезна. Рекурсивная функция может вызывать саму себя для решения каждой подзадачи. Например, рекурсия может использоваться для решения задачи комбинаторики, генерации перестановок или подмножеств, разбора и обработки выражений и т.д.
Работа с рекурсивными структурами данных: Рекурсия может быть полезна при работе с рекурсивными структурами данных, такими как бинарные деревья, кучи или списки. Она позволяет рекурсивно обрабатывать и манипулировать этими структурами данных.
Работа с задачами поиска и обхода: Рекурсия может быть использована для решения задач поиска и обхода, таких как обход графа в глубину (Depth-First Search) или в ширину (Breadth-First Search), поиск пути в лабиринте, решение головоломок и многое другое.