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

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

Давайте посмотрим на вычисление 4! как итеративно, так и рекурсивно.

Итеративно:

function iterativeFactorial(num) {
  let result = 1;
  for (let i = 1; i < num + 1; i++) {
    result *= i;
  }
  return result;
}
iterativeFactorial(4);
=> 24

Рекурсивно:

function recursiveFactorial(num) {
  if (num === 0) {
    return 1;
  }
  
  return num * factorial(num - 1);
}
recursiveFactorial(4);
=> 24

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

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

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

const data = [
  { id: "0" },
  {
    id: "1",
    children: [
      {
        id: "1.1",
        children: [
          {
            id: "1.1.1",
            children: [
              {
                id: "1.1.1.1",
                children: [
                  { id: "1.1.1.1.1" },
                  { id: "1.1.1.1.2" },
                  { id: "1.1.1.1.3" }
                ]
              },
              { id: "1.1.1.2" },
              { id: "1.1.1.3" }
            ]
          },
          { id: "1.1.2" },
          { id: "1.1.3" },
        ]
      },
      { id: "1.2" },
      { id: "1.3" }
    ]
  },
  { id: "2" },
  { id: "3" }
];

Если мы хотим собрать все значения id объектов в один массив, итерация невозможна. Пожалуйста, сдайте свой компьютер за счетами, если вы планируете вручную подсчитать степень вложенности каждого объекта. Что, если мы используем API, а приведенное выше является динамически отображаемым JSON? Нам нужно решение, которое работает динамически.

Введите рекурсию.

Рекурсивная функция, возвращающая массив всех идентификаторов, может быть:

function returnIdArr(data, result = []) {
  for (let i = 0; i < data.length; i++) {
    result.push(data[i].id);
    
    if (data[i].children) {
      returnIdArr(data[i].children, result);
    }
  }
  
  return result;
}
returnIdArr(data);
=> ['0', '1', '1.1', '1.1.1', '1.1.1.1', '1.1.1.1.1', '1.1.1.1.2', '1.1.1.1.3', '1.1.1.2', '1.1.1.3', '1.1.2', '1.1.3', '1.2', '1.3', '2', '3']

Функция выполняет цикл по массиву, и если какой-либо из объектов включает свойство «дочерние элементы», функция рекурсивно вызывает себя во вложенном дочернем массиве до бесконечности (или до тех пор, пока «дочерние элементы» не исчезнут). Каждый идентификатор помещается в массив результатов, который сам передается в качестве аргумента при каждом рекурсивном вызове.

Разрыв потока выполнения для первых нескольких кадров:

...
// the first iteration of the loop pushes '0' into the result array
result.push(data[0].id); // result = ['0']
if (data[0].children)... // false
/* ------------------------------------------------ */
...
// the second iteration pushes '1' into the result array
result.push(data[1].id); // result = ['0', '1']
// now true:
if (data[1].children) {
  returnIdArr(data[1].children, ['0', '1']);
/* recursively calls the function with the children and current result array as arguments */
...
/* ------------------------------------------------ */
/* the first iteration of this new loop (nested one level down) pushes '1.1' into the result array */
result.push(data[0].id); // result = ['0', '1', '1.1']
// true again:
if (data[0].children)...
returnIdArr(data[1].children, ['0', '1', '1.1']);
// and recursion again...
...

Мы можем видеть значение рекурсии в таких случаях - наша относительно простая функция returnIdArr действует как швейцарский армейский нож, возвращающий массив id для любой версии этой структуры данных. Он эффективен, удобочитаем и динамичен.

Теперь, посмотрев на приведенные выше кадры в стеке вызовов более разборчивым взглядом, мы можем даже начать рассматривать их влияние на память. Ни один из фреймов в стеке вызовов не может выскочить до тех пор, пока не будет пройден каждый элемент в текущем массиве. Это означает, что сначала должны быть оценены все дочерние свойства в текущем массиве, а также дочерние свойства в них. Фактически, первый уровень массива, заканчивающийся объектом, свойство id которого равно «3», остается в стеке вызовов все время, пока все остальные вложенные массивы не будут полностью пройдены.

Есть ли другие способы справиться с этим?

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

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

Вот некоторая (надуманная) рекурсия головы в действии:

function headCount(num) {
  if (num === 0) {
    return;
  } else {
    countDown(num - 1);
  }
  console.log(num);
}
count(3)
// 1
// 2
// 3

Функция headCount проверяет, равен ли ее аргумент num 0. Если нет, функция рекурсивно вызывает себя с уменьшенным числом в качестве аргумента.

Следует отметить две вещи:

  1. Рекурсия происходит наверху или в голове функции / обработки.
  2. Регистрируемые числа начинаются с 1 (а не с 3) и увеличиваются.

С другой стороны, с хвостовой рекурсией все наоборот - обработка происходит до рекурсивного вызова.

Вот немного (в равной степени надуманной) хвостовой рекурсии:

function tailCount(num) {
  if (num === 0) {
    return;
  } else {
    console.log(num)
  }
  countDown(num - 1);
}
countDown(3)
// 3
// 2
// 1

В отличие от нашей функции headCount, tailCount выводит числа, начинающиеся с 3, а затем уменьшающиеся. Чтобы это различие существовало, фреймы в соответствующих стеках вызовов должны отличаться при достижении операторов console.log.

Функция headCount должна создавать фреймы для каждого контекста выполнения из каждого рекурсивного вызова. Только после достижения базового случая, num === 0, кадры могут начать выскакивать из стека, достигая, таким образом, каждого соответствующего console.log.

С другой стороны, функция tailCount заменяет свой контекст выполнения каждым рекурсивным вызовом. Вызываемая рекурсивная функция регистрирует свой номер и не нуждается ни в каком контексте из предыдущего вызова. Из-за оптимизации хвостовых вызовов многие компиляторы гарантируют, что в стеке вызовов существует только один кадр на протяжении всего потока выполнения.

Незначительная разница в написанном коде, но огромная разница в поведении.

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

О, пока вы здесь, вы можете прочитать эту статью: Рекурсия: орел или решка