Чтобы возвести x в натуральную степень n — можно умножить его на себя n раз в цикле:
| function pow(x, n) {
|
| var result = x;
|
| for(var i=1; i<n; i++) {
|
| result *= x;
|
А можно поступить проще.
Ведь xn = x * xn-1, т.е. можно вынести один x из-под степени. Таким образом, значение функции pow(x,n) получается из pow(x, n-1) умножением на x.
Этот процесс можно продолжить. Например, вычислим 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;
|
…То есть, для степени pow(2, n) мы получаем результат как 2 * pow(2, n-1), затем уменьшаем n ещё на единицу и так далее. Этот процесс останавливается на n==1, так как очевидно, что pow(x,1) == x.
Код для такого вычисления:
| function pow(x, n) {
|
| // пока n!=1, сводить вычисление pow(..,n) к pow(..,n-1)
|
| return (n != 1) ? x*pow(x, n-1) : x;
|
| }
|
Говорят, что «функция pow рекурсивно вызывает сама себя».
Значение, на котором рекурсия заканчивается называют базисом рекурсии. В примере выше базисом является 1.
Общее количество вложенных вызовов называют глубиной рекурсии. В случае со степенью, всего будет n вызовов. Максимальная глубина рекурсии ограничена и составляет около 10000, но это число зависит от браузера и может быть в 10 раз меньше.
Рекурсию используют, когда вычисление функции можно свести к её более простому вызову, а его — еще к более простому, и так далее, пока значение не станет очевидно.
