Page 71 - 6105
P. 71
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;
}
}
alert (pow (2, 3)); // 8
В даному випадку «функція pow рекурсивно викликає сама себе» до n == 1.
Значення, на якому рекурсія закінчується, називають базисом рекурсії. В
наведеному вище прикладі базисом є 1. Загальну кількість вкладених викликів
називають глибиною рекурсії. У випадку зі ступенем, всього буде n викликів.
Максимальна глибина рекурсії в браузерах обмежена, точно можна
розраховувати на 10000 вкладених викликів, але деякі інтерпретатори допускають
і більше.
Отже, рекурсію використовують, коли обчислення функції можна звести до
її більш простого виклику, а його – ще до більш простого, і так далі, поки
значення не стане очевидне.
Розглянемо, як працюють функції і, що відбувається при їх виклику. У
кожного виклику функції є свій «контекст виконання» (execution context).
Контекст виконання - це службова інформація, яка відповідає поточному
запуску функції. Вона включає в себе локальні змінні функції і конкретне місце в
коді, на якому знаходиться інтерпретатор.
70
