Рекурсия в JavaScript

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

Так что же такое рекурсия простыми словами?

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

Теперь вопрос: каков базовый случай рекурсии?

По сути, базовый случай - это условие, которое вы используете для остановки функции. Без базового случая ваша функция будет бесконечно зацикливаться, что нехорошо.

Один из известных примеров использования рекурсии - поиск факториала (!).

n! = n × (n−1)!, where 0! = 1.
To find 4! we need to find 3! then 2! then 1!
4! = 4 × 3!
3! = 3 × 2!;
2! = 2 × 1!;
1! = 1
4! = 4 × 3 × 2 × 1 => 24

Вот решение для поиска факториала с использованием рекурсии:

function factorial(num){
  //base case of recursion to stop calling itself
  if(num === 1 || num === 0) return 1;
  //recursivly calling itself with new value 
  return num * factorial(num - 1)
}
factorial(4) // => 24

Рекурсия имеет временную сложность O (n) и пространственную сложность O (n).

Теперь давайте попробуем понять, что происходит на каждой итерации нашей функции, например, factorial (4). Если считать 4! ответ - 24, поэтому функция должна вернуть 24.

Используя отладчик в браузере, мы можем проверять значение num при каждом вызове.

Вызов №1, num = 4, тогда наша функция должна вызвать сама себя со значением num-1.

function factorial(4){
//base case of recursion to stop calling itself
if(4 === 1 || 4 === 0) return 1; // =>false
  return 4 * factorial(3)
}

Тогда факториал (4) приостановлен, пока мы получаем результат из факториала (3).

Вызов # 2, факториал (3) вызывает факториал (2), и он приостановлен, пока мы получаем результат из факториала (2).

function factorial(3){
 if(3 === 1 || 3 === 0) return 1; // => false
 return 3 * factorial(2) 
}

Вызов №3, факториал (2) на удержании после вызова факториала (1).

function factorial(2){
 if(2 === 1 || 2 === 0) return 1; // => false
 return 2 * factorial(1) 
}

Вызов №4, последним вызовом был factorial (1), вызванный возвратом 1, так как базовый случай был установлен так.

function factorial(1){
 if(1 === 1 || 1=== 0) return 1; // => true
 return 1 * factorial(0) 
}
// => 1

Давайте представим, что происходит под капотом, когда мы вызываем factorial (4).

//Visualization of invoking function factorial(4)
function factorial(4){
//base case of recursion to stop calling itself
if(4 === 1 || 4 === 0) return 1; // => false
 
 return 4 * factorial(3){ // => 4 * 3 * 2 * 1
            if(3 === 1 || 3 === 0) return 1; // => false
            
              return 3 * factorial(2){ // => 3 * 2 * 1
                  
                  if(2 === 1 || 4 === 0) return 1;
                  
                     return 2 * factorial(1){ // => 2 * 1
                     
                      if(1 === 1 || 1 === 0) return 1; // => true
                       return 1 * factorial(0)}
                  }
            }
}
// factorial(4) = 4 * factorial(3) = 4 * (3 * factorial(2)) =
// 4 * (3 *(2 * factirial(1))) = 4 * (3 * (2 * (1))) = 
// 4 * (3 * (2)) = 4 * (6) = 24 
// => 4 * 3 * 2 * 1 => 24

factorial (4) = 4 * 3 * 2 * 1 = 24, правильный ответ.

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

Нерекурсивное решение для поиска факториала может использовать итерацию цикла:

function factorial(num){
   let result = 1;
   if(num === 0) return 1;
   while(num){
      result = result * num;
      num--;
   }
   return result;
}

Здесь временная сложность O (n); Сложность пространства - O (1).

Рекурсия требует меньше строк кода за счет используемого пространства. Так что рекурсия не годится, если вам небезразлично пространство. Итак, в зависимости от ситуации вы должны решить использовать рекурсию или нет.

Надеюсь, этот пост поможет вам разобраться в рекурсии. Буду признателен за любые отзывы!

Ресурсы с более подробной информацией: