Рекурсия в JavaScript

Что такое рекурсия

Рекурсией называют процесс, когда функция вызывает сама себя. То есть, объявляется функцию и в ее теле происходит обращение к ней же (она вызывается). Важным в рекурсии является граничное условие, при выполнении которого функция прекратит вызываться и вернет какое-то значение. Без этого условия возникнет ошибка о переполнении стека вызовов:

Uncaught RangeError: Maximum call stack size exceeded

На собеседованиях очень любят задавать вопросы про рекурсию или предложить решить задачку используя ее, так как это один из базовых принципов в программировании. Если вы Junior Front-End разработчик, то очень высока вероятность, что на собеседовании спросят что-то на эту тему, поэтому полезно знать, что такое рекурсия.

Пример рекурсии

Классический пример рекурсии — это, конечно же, факториал, его приводят во всех книжках по программированию, где упоминается рекурсия.

На всякий случай вспомним, что это такое. В математике факториал числа n равен произведению всех целых положительных чисел меньших или равных ему, и обозначается как n! Формулой можно выразить так:

n! = n * (n - 1) * (n - 2) * … * 3 * 2 * 1

Например, факториал числа 4! = 1 * 2 * 3 * 4 = 24, а для 6! = 1 * 2 * 3 * 4 * 5 * 6 = 720. Факториал нуля равен единице: 0! = 1.

Чтобы можно было сравнить разные подходы, для начала давайте приведем пример вычисления факториала в JavaScript с помощью простого цикла.

function factorial(n) {
  let result = 1;

  for (let i = n; i > 0; i--) {
    result *= i;
  }

  return result;
}

Все достаточно просто, инициализируем переменную и в цикле все перемножаем. Но, можно еще проще и короче. Цикл идет в обратном порядке, чтобы приблизить его смысл к следующему примеру.

Давайте теперь решим задачу с помощью рекурсии. Математически рекурсию можно выразить следующей формулами:

n! = n * (n - 1)!

или

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

или

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

И так далее, пока не дойдем до нуля.

Теперь тоже самое, но с помощью JavaScript.

function factorial(n) {
  if (n === 0) {
    return 1;
  }

  return n * factorial(n - 1);
}

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

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

factorial(4) = 4 * factorial(3);
factorial(4) = 4 * (3 * factorial(2));
factorial(4) = 4 * (3 * (2 * factorial(1)));
factorial(4) = 4 * (3 * (2 * (1 * factorial(0))));
factorial(4) = 4 * (3 * (2 * (1 * 1))));

factorial(0) = 1, потому, что у нас есть граничное условие, при n = 0 мы возвращаем 1.

На этом, про рекурсию в JavaScript, все. Надеюсь, смог помочь начинающему веб разработчику понять, что такое рекурсия.