Web-разработка

Схватка “рекурсия против циклов” на арене JavaScript

07.02.2023

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

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

Если же вы справитесь с освоением этих 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.

Схватка “рекурсия против циклов” на арене JavaScript

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

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

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

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

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

Заключение

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

Как обнаружить дублирование кода в проекте

Создание модели машинного обучения с помощью Google Colab без дополнительных настроек

Как изменить PYTHONPATH на Windows

Тесты

Что вы знаете о типах данных Java?

Хорошо ли вы разбираетесь в процессе веб-дизайна?

Насколько хорошо вы разбираетесь в алгоритмах и структурах данных