Рекурсия с показателями

Question

Я пытаюсь изучить рекурсию путем рефакторинга некоторых простых задач с использованием рекурсии (а не традиционных циклов). Я боролся с экспонентами. Я не могу понять, как это работает. Насколько я могу судить, не было определено никакой математической операции для определения того, что "pow" должна делать со своими параметрами. Итак ... как он "знает" математически, что делать со своими параметрами? Может кто-нибудь помочь мне понять это, пожалуйста? Почему это вычисляется правильно и не заканчивается на «return base *? What-do-I-do-here?»

function pow(base, exponent) {
  if (exponent === 0) {
    return 1;
  }
  return base * pow(base, exponent - 1);
}

pow(2, 3); //-> 8

Answer 1

Есть небольшая поговорка:

Чтобы понять рекурсию, нужно понимать рекурсию.

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

Каждая хорошая рекурсивная функция имеет базовый случай (не путать с параметром base в вашей функции), и этот базовый случай - это рекурсия, которую вы должны понять, т.е. понять, как прийти к базовому случаю.

if (exponent === 0) {
    return 1;
}

Вышеупомянутое составляет основу способности функции вычислять мощность.

Процесс оценки

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

См. В чем разница между выражением и оператором в Python?

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

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

Обратите внимание, как этот процесс рекурсивен? Надеюсь, теперь вы начинаете понимать

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

Answer 2

Вся рекурсия начинается в конце, с «стопора», чтобы мы не зацикливались вечно. В данном случае это нулевой тест:

if (exponent === 0) {
    return 1;
}

Ну, поскольку мы продолжаем рекурсивно, вычитая 1 из текущего показателя степени, что положительно, это условие в конечном итоге будет истинным:

return base * pow(base, exponent - 1);

Итак, вы довольны, что мы не oop вечно? В конце концов показатель степени будет равен нулю, и мы вернем 1, и рекурсия остановится.

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

• Мы закончим, когда показатель степени равен 0, вернув 1, поэтому начните с 1.

• Go назад на одну рекурсию. Тогда показатель степени будет равен 1, а результат будет равен основанию, умноженному на 1, что является основанием. Эй, это правильный ответ!

• Хорошо, go назад еще на одну рекурсию. Тогда показатель степени будет равен 2, а результат будет равен основанию, умноженному на основание, умноженному на 1, или квадрату основания. Эй, это снова правильный ответ!

• И я считаю, что обнаружил здесь закономерность: результат всегда умножается на основание (а также на 1), такое же количество раз, как и значение экспоненты, в любом случае это может быть.

И это действительно то, что означает возведение в степень.