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

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

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

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

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

Напишем функцию, которая позволяет вычислять факториал для положительных целых чисел. Записываются факториалы так: 5!, а формула для них выглядит так:

n! = n * (n - 1) * (n - 2) * ... * 1

Тогда 5! будет равно:

5! = 5 * 4 * 3 * 2 * 1 = 120

Как написать для этого функцию? Один из вариантов предполагает использование цикла while. Можно создать переменную для result, а затем умножить ее на x в цикле, каждый раз декрементируя x на 1. Вот соответствующий код:

export const factorial = (x) => {
if (x < 0) {
throw new Error('x must be greater than or equal to 0');
}

if (x <= 1) {
return 1;
}

let result = 1;

while (x > 0) {
result *= x;
x--;
}

return result;
};

Заметьте, что мы также обработали неверные входные значения меньше 0 и упростили случаи с 0 и 1, поскольку и 0!, и 1! равны 1.

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

export const factorial = (x) => {
if (x < 0) {
throw new Error('x must be greater than or equal to 0');
}

if (x <= 1) {
return 1;
}

return x * factorial(x - 1);
};

Гораздо короче. Заметьте, что в последней строке мы возвращаем x, умноженную на результат повторного вызова той же функции factorial с аргументом x-1. Это и есть рекурсивный случай.

Если просто вызывать функцию рекурсивно, то получится бесконечный цикл, значит нужен способ его разорвать. Именно поэтому у нас есть условие, которое срабатывает, когда x <= 1. При достижении этой точки мы перестаем рекурсивно вызывать функцию factorial  —  это базовый случай.

Готовы к очередному примеру?

Пример #2: возведение в степень

Разберем похожий случай. На этот раз мы реализуем функцию возведения в степень. Например, 2^3  —  это 2, возведенное в 3-ю степень, то есть 2 * 2 * 2, что равно 3.

В JavaScript есть 2 нативных способа возведения чисел в степени. В нашем случае это либо вызов Math.pow(2, 3), либо использование степенного синтаксиса вроде 2 ** 3. Сейчас же представим, что этих возможностей не существует. Как тогда можно написать подобную функциональность самим?

Используя цикл while, можно создать функцию вроде такой:

export const power = (x, y) => {
if (y < 0) {
throw new Error(
'exponent must be greater than or equal to 0 (for the purposes of this example)'
);
}

if (y === 0) {
return 1;
}

let result = 1;

while (y > 0) {
result *= x;
y--;
}

return result;
};

Заметьте, что в этом примере мы будем игнорировать отрицательные степени, хотя в реальности они вполне допустимы. Кроме того, мы будем обрабатывать случай, в котором степень равна 0, поскольку любое число в степени 0 всегда равно 1 (2^0 = 1).

По аналогии с примером факториала мы начали с result равного 1, после чего стали циклически умножать result на x, пошагово уменьшая y до момента достижения 0.

А вот как будет выглядеть рекурсивное решение:

export const power = (x, y) => {
if (y < 0) {
throw new Error(
'exponent must be greater than or equal to 0 (for the purposes of this example)'
);
}

if (y === 0) {
return 1;
}

return x * power(x, y - 1);
};

И снова это решение оказалось короче! В последней строке у нас рекурсивный случай, когда мы умножаем x на результат вызова функции power с x и декрементируемым аргументом y-1.

Помимо этого, у нас есть базовый случай, в котором при y равном 0 мы возвращаем 1. Таким образом мы исключаем возможность бесконечного вызова функции power.

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

Продолжаем.

Пример #3: сумма чисел в массиве

Теперь мы напишем функцию, суммирующую все числа в массиве. В JavaScript есть метод reduce, который предоставляет простой инструмент для сведения массива в сумму его элементов:

numbers.reduce((number, sum) => number + sum, 0);

Сейчас же мы снова представим, что reduce не существует. Как тогда написать собственную функцию? Один из вариантов  —  это использовать цикл for для перебора всех элементов массива и их сложения. Код получится таким:

export const sumNumbersArray = (numbers) => {
let sum = 0;

for (let i = 0; i < numbers.length; i++) {
sum += numbers[i];
}

return sum;
};

Коротко и просто. А что, если мы захотим сделать это рекурсивным способом? Тогда есть такой вариант:

export const sumNumbersArray = (numbers) => {
if (numbers.length === 0) {
return 0;
}

return numbers[0] + sumNumbersArray(numbers.slice(1));
};

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

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

Пока вы думаете, нас ждет очередной пример.

Пример #4: поиск наибольшего числа в массиве

В этом примере мы напишем функцию, получающую массив чисел и возвращающую наибольшее из них. В JavaScript для этого можно использовать вспомогательную функцию Math.max:

Math.max(...numbers);

Но в целях эксперимента снова нужно представить, что такой функциональности нет. Как тогда написать ее самим? При использовании цикла for решение получится таким:

export const maxNumberArray = (numbers) => {
let max = numbers[0];

for (let i = 1; i < numbers.length; i++) {
if (numbers[i] > max) {
max = numbers[i];
}
}

return max;
};

Здесь мы изначально предполагаем, что первое число в массиве является наибольшим, после чего начинаем этот массив перебирать, начиная со второго элемента и сравнивая текущий элемент с найденным максимальным. Если текущий элемент оказывается больше последнего максимального, мы обновляем это максимальное значение. По завершению перебора всего списка у нас остается наибольшее число.

Вроде все просто. А теперь посмотрим на рекурсивный вариант решения:

export const maxNumberArray = (numbers) => {
if (numbers.length <= 1) {
return numbers[0];
}

const numberA = numbers[0];
const numberB = maxNumberArray(numbers.slice(1));

return numberA > numberB ? numberA : numberB;
};

Не кажется ли он вам несколько более сложным для понимания? Давайте его разберем.

Если в массиве находится 0 или 1 элемент, то мы просто возвращаем 1-ый (undefined в случае пустого массива). Это базовый случай.

Для массивов, содержащих 2 и более элементов, мы будем выполнять сравнение  —  брать 1-ый элемент и сравнивать его с результатом рекурсивного вызова maxNumberArray для оставшейся части массива, в завершении возвращая наибольшее число.

Не особо понятно? Мне тоже. 

Рассмотрим пример вызова maxNumberArray и поэтапно его разберем. Представьте, что мы вызываем эту функцию с такими аргументами:

maxNumberArray([1, 9, 5, 7, 3, 8, 2, 4])

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

2 больше 4? максимальное число 4.
8 больше 4? максимальное число 8.
3 больше 8? максимальное число 8.
7 больше 8? максимальное число 8.
5 больше 8? максимальное число 8.
9 больше 8? максимальное число 9.
1 больше 9? максимальное число 9.

Итак, по сути, мы проходим по массиву в обратном порядке, начиная с 2 последних чисел. Мы сравниваем эти 2 числа и оставляем наибольшее. Затем мы смещаемся на 1 элемент влево и сравниваем его с текущим максимальным числом.

Таким образом мы продолжаем смещаться влево, пока не достигаем начала массива. В этот момент мы уже сравнили все числа, и у нас осталось наибольшее.

Будет ли такой рекурсивный вариант лучше варианта с циклом? Опять же, вопрос субъективный. Но я думаю, что нет. Когнитивная сложность понимания работы этой рекурсивной функции выше, чем усилия, необходимые для понимания реализации этой функции с помощью цикла.

В данном случае рекурсивный вариант больше выглядит как более “умное” решение, но не более “понятное”.

Осталось разобрать последний пример.

Пример #5: поиск ключа, спрятанного в ящиках внутри ящиков

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

Итак, предположим, что:

  • 1-ая коробка (коробка A) содержит 3 других коробки (коробку B, коробку C и коробку D).
  • коробка B пуста.
  • коробка C содержит 2 коробки (коробку E и коробку F).
  • коробка E содержит 1 коробку (коробку G).
  • коробка G содержит ключ (Ура!).
  • коробка F пуста.
  • коробка D содержит 1 коробку (коробку H).
  • коробка H пуста.

Как написать функцию, которая будет обыскивать коробки, пока не найдет ключ?

Для этого можно использовать цикл while:

export const findKeyInBox = (box) => {
const pile = [];
pile.push(box);

while (pile.length > 0) {
const currentBox = pile.pop();
console.log(`Looking in Box ${currentBox.id}`);

for (let i = 0; i < currentBox.contents.length; i++) {
if (currentBox.contents[i].type === 'key') {
console.log(`Found the key in Box ${currentBox.id}!`);
return currentBox.id;
}

if (currentBox.contents[i].type === 'box') {
console.log(
`Found Box ${currentBox.contents[i].id} in Box ${currentBox.id}`
);
pile.push(currentBox.contents[i]);
}
}
}
};

Мы начинаем с пустой кучи (pile, массива, который можно использовать в качестве стека) и затем добавляем в эту кучу первую коробку.

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

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

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

Теперь интересно взглянуть на рекурсивное решение задачи. Оно у нас будет таким:

export const findKeyInBox = (box) => {
console.log(`Looking in Box ${box.id}`);

for (let i = 0; i < box.contents.length; i++) {
if (box.contents[i].type === 'key') {
console.log(`Found the key in Box ${box.id}!`);
return box.id;
}

if (box.contents[i].type === 'box') {
console.log(`Found Box ${box.contents[i].id} in Box ${box.id}`);
const boxContainingKey = findKeyInBox(box.contents[i]);

if (boxContainingKey) {
return boxContainingKey;
}
}
}
};

Обратите внимание на разницу между рекурсивным решением и решением с помощью цикла. В рекурсивном мы не отслеживаем кучу, а просто заглядываем в 1-ую коробку и, если других коробок там не находим, то рекурсивно вызываем для нее функцию findKeyInBox. При этом состояние за нас снова отслеживается в стеке вызовов.

Заключение

Итак, что же лучше: циклы или рекурсия? Как я и говорил, решать вам. В плане быстродействия между этими 2 подходами обычно значительной разницы нет, и нотация “О” большое для них будет одинаковой, поскольку в каждом случае выполняется одинаковое число операций.

Единственное, что таким образом можно оптимизировать  —  это читаемость. Что для вас понятнее  —  рекурсивное решение или решение с циклом? А если подумать о следующем разработчике, который будет читать ваш код? 

Если при этом дополнительно учесть, что читается код в 10 раз чаще, чем пишется, то оптимизировать его нужно именно под читаемость.

Если захотите еще раз просмотреть примеры и заглянуть в тестовые кейсы, то все эти функции лежат в репозитории на GitHub.

Читайте также:

Читайте нас в TelegramVK и Дзен


Перевод статьи Tyler Hawkins: Recursion vs. Loops in JavaScript

Предыдущая статьяКак создать многопользовательский чат с помощью WebSocket за 10 минут
Следующая статья10 самых серьезных ошибок в UX/UI-дизайне