Рекурсия и стек

393

31 декабря 2016, 16:30

В общем единственная тема, которую я никак не могу понять - это рекурсия. Написал маленький код, но не понимаю как он работает до конца.

function power (base, exponent){
   if (exponent == 0)
       return 1;
   else
       return base * power(base, exponent -1);
}
console.log(power(2, 3));

Можете ли объяснить по шагам как тут всё устроено?

Answer 1

Привожу пример: вычислим pow(2, 4), последовательно переходя к более простой задаче:

pow(2, 4) = 2 * pow(2, 3)
pow(2, 3) = 2 * pow(2, 2)
pow(2, 2) = 2 * pow(2, 1)
pow(2, 1) = 2

На шаге 1 нам нужно вычислить pow(2,3), поэтому мы делаем шаг 2, дальше нам нужно pow(2,2), мы делаем шаг 3, затем шаг 4, и на нём уже можно остановиться, ведь очевидно, что результат возведения числа в степень 1 – равен самому числу.

Далее, имея результат на шаге 4, он подставляется обратно в шаг 3, затем имеем pow(2,2) – подставляем в шаг 2 и на шаге 1 уже получаем результат.

Этот алгоритм на JavaScript:

function pow(x, n) { 
  if (n != 1) { // пока n != 1, сводить вычисление pow(x,n) к pow(x,n-1) 
    return x * pow(x, n - 1); 
  } else { 
    return x; 
  } 
} 
 
console.log( pow(2, 3) ); // 8

Говорят, что «функция pow рекурсивно вызывает сама себя» до n == 1.

Значение, на котором рекурсия заканчивается называют базисом рекурсии. В примере выше базисом является 1.

Общее количество вложенных вызовов называют глубиной рекурсии. В случае со степенью, всего будет n вызовов.

Максимальная глубина рекурсии в браузерах ограничена, точно можно рассчитывать на 10000 вложенных вызовов, но некоторые интерпретаторы допускают и больше.

Итак, рекурсию используют, когда вычисление функции можно свести к её более простому вызову, а его – ещё к более простому, и так далее, пока значение не станет очевидно.

Answer 2

function power (base, exponent){
   //Посчитаем силу базы (хз что это, но надо так надо :)
   //Если экспонента точно равна нулю, то мы знаем ответ!
   if (exponent == 0) {
       return 1; //и он равен нулю
   }
   else { //Но если экспонента нулю не равна, то ответ мы не знаем
       //Попробуем уменьшить экспоненту на 1 и посчитать снова
       exponent = exponent - 1;
       //результатом работы функции будет число, умноженное на результат работы ЭТОЙ же функции, но с экспонентой, уменьшенной на 1
       return base * power(base, exponent);
   }
   //Если придет значение экспоненты меньше нуля, то все, браузеру хана :)
}