Рекурсия не должна пугать
Рекурсия — заклятый враг каждого разработчика, сравнимая по силе только со своим другом — регулярными выражениями.
Рекурсия может быть трудной для понимания по нескольким причинам. Во-первых, вы должны понять концепцию функции, вызывающей саму себя. Во-вторых, вы должны понимать разницу между базовым и рекурсивным случаем, иначе вы можете застрять в бесконечном цикле, пока не вызовете переполнение стека.
Если вы сможете освоить эти две концепции, рекурсия не так страшна и сложна, как вы думаете. Рекурсивный код часто короче для написания и (в некоторых случаях) легче читается.
Давайте вместе рассмотрим пять примеров кода. Сначала мы решим каждую задачу с помощью цикла, а затем рекурсией. Какой подход лучше? Это вам решать.
Пример №1: факториал
Давайте напишем функцию, которая позволяет нам вычислять факториал для положительных целых чисел. Факториалы записываются так: 5!. А формула факториала выглядит так:
n! = n * (n - 1) * (n - 2) * ... * 1
Итак, 5! будет:
5! = 5 * 4 * 3 * 2 * 1 = 120
Как бы мы могли написать для этого функцию? Одним из подходов было бы использование файла while loop. Мы можем создать переменную для нашего result, а затем умножить ее на x в цикле, каждый раз уменьшая x на 1. Код выглядит следующим образом:
Обратите внимание, что мы также обработали неверные входные данные меньше 0 и упростили случаи 0 и 1, поскольку 0! и 1! оба равны 1.
Итак, это решение, использующее цикл. Что, если бы мы захотели написать эту функцию рекурсивно? Рекурсивное решение может выглядеть так:
Вау! Это намного короче. Обратите внимание, что в последней строке мы возвращаем x, умноженное на результат повторного вызова нашей той же функции factorial с x — 1 в качестве аргумента. Это рекурсивный случай.
Если бы мы просто вызывали нашу функцию рекурсивно, мы бы оказались в бесконечном цикле, поэтому нам нужен какой-то способ выйти из него. Вот почему у нас есть условие, которое обрабатывается, когда x <= 1. Когда мы достигнем этой точки, мы перестанем рекурсивно вызывать нашу функцию factorial. Это базовый случай.
Готовы к другому примеру?
Пример №2: Мощность
Попробуем аналогичный пример. На этот раз давайте реализуем степенную функцию, которая вычисляет результат возведения базового числа в степень. Так, например, 2^3 — это два, возведенные в степень три, или 2 * 2 * 2, что равно 8.
В JavaScript есть несколько способов сделать мощные функции изначально, например, вызвать Math.pow(2, 3) или использовать синтаксис возведения в степень, например 2 ** 3. А пока давайте притворимся, что этих утилит не существует. Как мы могли сами написать эту функциональность?
Используя while loop, мы могли бы написать функцию, которая выглядит так:
Обратите внимание, что в этом примере мы проигнорируем отрицательные показатели степени, хотя в реальной жизни иметь отрицательную степень вполне допустимо. Мы также рассмотрим случай, когда показатель степени равен 0, поскольку любое число, возведенное в 0, всегда равно 1 (2^0 = 1).
Как и в нашем примере с факториалом, мы начали с начального result, равного 1. Затем мы умножаем result на x в цикле, уменьшая y, пока не достигнем 0.
Теперь, как будет выглядеть рекурсивное решение? Как насчет этого:
Ого, опять короче! В самом низу у нас есть наш рекурсивный случай, когда мы умножаем x на результат вызова нашей функции power с x и уменьшенным y — 1.
Кроме того, у нас есть наш базовый случай, в котором мы возвращаем единицу, если y равно 0. Таким образом, мы можем отказаться от бесконечного вызова нашей функции power.
Интересно, что нам не нужно отслеживать переменную result в обоих наших рекурсивных решениях. Стек вызовов делает это за нас!
Готовы двигаться дальше?
Пример № 3: суммирование чисел в массиве
Напишем функцию, которая суммирует все числа в массиве. В JavaScript метод reduce предоставляет простой инструмент для преобразования массива в такую сумму:
numbers.reduce((number, sum) => number + sum, 0);
А пока представим, что reduce не существует. Как мы могли бы написать свою собственную функцию? Один из вариантов — использовать for loop для перебора всех элементов в массиве и добавления их вместе. Код выглядит следующим образом:
Коротко и просто. А что, если мы хотим сделать это рекурсивно? Мы могли бы написать рекурсивное решение следующим образом:
Каждый раз мы добавляем первое число к результату вызова функции sumNumbersArray для остальной части нашего массива, исключая первое число.
Теперь это лучший способ, чем использование for loop? Это субъективный вопрос, но, на мой взгляд, использование рекурсии здесь кажется более неестественным, чем просто использование цикла. Что вы думаете?
А пока рассмотрим другой пример.
Пример № 4: найти наибольшее число в массиве
Давайте напишем функцию, которая принимает массив чисел и возвращает наибольшее из них. В JavaScript мы могли бы использовать вспомогательную функцию Math.max следующим образом:
Math.max(...numbers);
Но ради аргумента давайте притворимся, что у нас нет этой функции. Как мы могли написать это сами? Используя for loop, наш код мог бы выглядеть так:
Начнем с предположения, что первое число в нашем массиве является наибольшим числом. Затем мы перебираем массив, начиная со второго элемента, и сравниваем текущий элемент с максимальным числом. Если текущий элемент больше максимального числа, мы обновляем максимальное число этим значением. После того, как мы закончили цикл по нашему списку, мы нашли наибольшее число.
Итак, довольно прямолинейно. А что, если бы мы захотели написать это рекурсивно? Мы могли бы написать нашу функцию так:
Не кажется ли вам, что это немного сложнее понять интуитивно? Давайте пройдемся по нему.
Если массив содержит ноль элементов или один элемент, мы просто вернем первый элемент (undefined в случае пустого массива). Это наш базовый случай.
Мы проведем сравнение для массивов, содержащих два и более элемента. Мы возьмем первый элемент массива, а затем сравним его с результатом рекурсивного вызова maxNumberArray для остальной части массива. Затем мы вернем то число, которое больше.
Все еще не ясно? И я нет.
Давайте посмотрим на пример того, как это вызывается, и каждый раз будем проходить по шагам. Представьте, что мы вызываем функцию с этим аргументом:
maxNumberArray([1, 9, 5, 7, 3, 8, 2, 4])
Поскольку функция рекурсивно вызывает себя, неразрешенные функции помещаются в стек вызовов. Как только мы достигаем базового случая массива только с одним элементом, функции начинают разрешаться. Итак, вот как выглядят наши сравнения:
Is 2 greater than 4? 4 is our max number. Is 8 greater than 4? 8 is our max number. Is 3 greater than 8? 8 is our max number. Is 7 greater than 8? 8 is our max number. Is 5 greater than 8? 8 is our max number. Is 9 greater than 8? 9 is our max number. Is 1 greater than 9? 9 is our max number.
Таким образом, концептуально мы идем по массиву в обратном направлении, начиная с двух последних чисел. Мы сравниваем эти два числа и оставляем наибольшее. Затем мы перемещаемся влево на один элемент и сравниваем это с нашим текущим максимальным числом.
Мы продолжаем двигаться влево, пока не достигнем начала массива, после чего мы сравнили все наши числа и нашли наибольшее из них.
Этот рекурсивный пример лучше? Опять же, это субъективный вопрос, но я чувствую, что ответ отрицательный. Когнитивная сложность понимания того, как работает эта рекурсивная функция, выше, чем усилия, необходимые для понимания функции, реализованной с помощью цикла.
Рекурсивная функция кажется «умным», но не «ясным» решением.
Давайте сделаем еще один пример, прежде чем мы завершим.
Пример № 5: найти ключ, спрятанный внутри коробок внутри коробок
Это будет наш самый сложный пример, но это идеальный вариант использования рекурсии. Представим, что у вас есть коробка. Этот ящик может содержать несколько других ящиков, других ящиков и так далее. Ящик также может быть пустым. И, наконец, в ящике, который мы ищем, лежит ключ.
Итак, представьте, что:
- Первый ящик (ящик A) содержит три других ящика (ящик B, ящик C и ящик D).
- В ящике B ничего нет.
- Внутри ящика C находятся два ящика (ящик E и ящик F).
- Внутри ящика E находится один ящик (ящик G).
- В коробке G лежит ключ (ура!).
- В ящике F ничего нет.
- Внутри ящика D находится один ящик (ящик H).
- В ящике H ничего нет.
Голова еще не болит?
Как мы можем написать функцию, которая просматривает ящики, пока не найдет ключ?
Мы могли бы написать эту функцию, используя while loop следующим образом:
Мы начинаем с пустой стопки (массив, который мы можем использовать в качестве структуры данных стека), а затем добавляем в эту стопку нашу первую коробку.
Затем, пока эта куча не пуста, берем из кучи коробку и заглядываем внутрь.
Каждый предмет, который мы находим в коробке, может быть либо ключом (ура, мы его нашли!) либо другой коробкой (отлично…). Если мы найдем ключ, то нам конец. Если мы находим коробку, то добавляем эту коробку в нашу стопку.
Мы повторяем наш цикл, пока не закончим все коробки или пока не найдем ключ.
А что, если бы мы захотели найти рекурсивное решение этой проблемы? Мы могли бы написать нашу функцию так:
Обратите внимание на различия между нашим рекурсивным решением и нашим циклическим решением. В рекурсивном решении мы не отслеживаем стопку. Мы просто просматриваем первый ящик, а затем, если находим еще ящики, рекурсивно вызываем нашу функцию findKeyInBox для этого ящика. Стек вызовов снова отслеживает наше состояние для нас!
Заключение
Итак, что лучше: циклы или рекурсия? Это вам решать. Обычно между циклами и рекурсией нет существенных различий в производительности, и нотация Big O одинакова, поскольку в каждом случае выполняется одинаковое количество операций.
Настоящая вещь, для которой вы оптимизируете, — это читабельность. Вам легче понять рекурсивное решение или решение цикла? А что насчет следующего разработчика, который прочитает этот код?
Код читается в 10 раз чаще, чем пишется, поэтому оптимизируйте его для удобочитаемости.
Спасибо за прочтение! Если вы хотите вернуться к этим примерам и увидеть тестовые случаи, вы можете найти все функции, которые мы обсуждали, в этом репозитории GitHub.
