Рекурсия, рекурсия, рекурсия…

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

Так что же это такое? Рекурсия — это когда функция вызывает сама себя. То есть внутренняя функция вызывается внутри той же внешней функции. Например:

function practice(x) {
   console.log(x)
   practice(x-1)
}

Теперь есть небольшая проблема с вышеупомянутой функцией, но мы займемся этим через минуту.

Рекурсия против. Итерация

Многие проблемы можно решить, используя либо рекурсию, либо итерацию (т. е. сопоставление, циклы for и т. д.) для получения тех же результатов. Например, давайте возьмем классический пример нахождения факториала по заданному числу. Напоминаем, что факториал — это произведение всех положительных целых чисел, меньших или равных заданному числу (например, 3! = 1 * 2 * 3 = 6). Вот один из способов решения этой проблемы с помощью итерации:

function findFactorial(num) {  
   let factorial = 1;  
   for (let i = 2; i <= num; i++) {    
      factorial *= i;  
   }  
   return factorial;
}

В этом случае наша функция findFactorial принимает число в качестве аргумента и сразу же устанавливает переменную счетчика в 1. Факториалы представляют собой произведение всех положительных целых чисел, поэтому наш счетчик должен начинаться с 1, а не с 0. Затем мы используем цикл for, начиная с индекса 2, который умножает каждый индекс на текущий счетчик факториала. Наконец, мы возвращаем factorial.

Точно так же эту проблему можно решить с помощью рекурсивной функции:

function findFactorial(num, factorial = 1) {
   if (num === 0) {
      return factorial;
   }
   return findFactorial(num - 1, factorial * num);
}

Здесь наша функция findFactorial принимает требуемое число в качестве аргумента и необязательный счетчик factorial в качестве аргумента, для которого мы установили значение по умолчанию, равное 1. Опять же, это связано с тем, что факториалы умножают только положительныецелые числа. Затем у нас есть базовый случай, который завершает работу функции, когда num уменьшается до 0 (подробнее о базовых случаях через минуту). Затем в игру вступает рекурсия, когда мы снова вызываем функции findFactorial, но уменьшаем аргумент num на 1 и умножаем счетчик factorial на исходное число. Функция начинается сначала и будет продолжаться до тех пор, пока factorial не станет равным 0.

Рекурсивный и базовый случай

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

Если мы просто вызовем функцию внутри той же функции с точно такими же аргументами, не будет ничего, что могло бы определить, когда она должна перестать читать себя и продолжить… ну, навсегда:

function practice(x) {
   console.log(x)
   practice(x)
}

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

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

function practice(x) {
   console.log(x)
   practice(x-1)
}

Учитывая X, скажем, 5, как функция узнает, когда остановиться? Он может уйти в минус навсегда. Быстрое решение для этого будет:

function practice(x) {
   if (x === 0) {
      return;
   }
   console.log(x)
   practice(x-1)
}

При последнем вызове, когда x -1 = 0 и снова начинается сверху, оператор if поймает его и возвратится, остановив функцию и выполнив выход из нее.

Совершенно очевидно, что рекурсивный случай — это блок кода, в котором функция вызывается снова. Легко, как это!

Стек вызовов

Рекурсию иногда называют «стеком вызовов» из-за того, что функция перемещается поверх стека вызовов при ее вызове. Думайте об этом, как о приготовлении стопки блинов. Вы кладете первое блюдо на тарелку, второе поверх него и третье поверх него. Затем, когда вы идете съесть один, вы сначала снимаете блин № 3, затем № 2 и, наконец, № 1. Чтобы вернуться к факторному примеру, предположим, что мы ввели число 4 в качестве аргумента:

function findFactorial(num, factorial = 1) {
   if (num === 0) {
      return factorial;
   }
return findFactorial(num - 1, factorial * num);
}
findFactorial(4)

После того, как функция была успешно запущена, и мы пытаемся получить окончательное значение factorial, оно будет выглядеть так:

1. 1 (начальный факториал) * 1 (конечное числовое значение) = 1
2. 1 (новый факториал) * 2 (следующее числовое значение) = 2
3. 2 (новый факториал) * 3 (следующее числовое значение) = 12
4. 12 (новый факториал) * 4 (начальное числовое значение) = 24
5. factorial = 24

Вывод

Хотя на самом деле использование рекурсии не дает каких-либо преимуществ в производительности, она, безусловно, может сделать ваш код намного легче для чтения и сделать его намного красивее, чем краткая итерация. Кроме того, это такая ключевая концепция, что она наверняка появится в интервью, и вы обязательно встретите ее на Github. Рекурсия печально известна тем, что ее чрезвычайно сложно сформулировать и к ней нужно много времени, чтобы привыкнуть, так что не волнуйтесь, если вы не сразу ее поняли! Непрерывная практика рефакторинга итераций в рекурсии — лучший способ добиться в этом успеха.