Источник: Nuances of Programming
Курс SkillFactory Frontend-разработчик. Получите перспективную творческую профессию в IT.
ля любого разработчика рекурсия — это заклятый враг, с которым по силе могут сравниться лишь ее друзья — регулярные выражения.
Сложность в понимании рекурсии объясняется двумя причинами. Во-первых, приходится уложить в голове принцип вызова функцией самой себя. Во-вторых, нужно понять разницу между базовым случаем и рекурсивным, иначе вы застрянете в бесконечном цикле, пока не возникнет переполнение стека.
Если же вы справитесь с освоением этих 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.
Читайте также:
Перевод статьи Tyler Hawkins: Recursion vs. Loops in JavaScript
