У каждого вызова функции есть свой «контекст выполнения» (execution context).

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

При любом вызове функции интерпретатор переключает контекст на новый. Этот процесс состоит из нескольких шагов:

Текущая функция приостанавливается.
Информация о её выполнии, то есть текущий контекст заносится в специальную внутреннюю структуру данных: «стек контекстов».
Запускается новая функция, для нее создаётся свой контекст.
По завершении подвызова предыдущий контекст достаётся из стека, выполнение в нём возобновляется.

Например, для вызова:

function pow(x, n) {

return (n != 1) ? x*pow(x, n-1) : x;

}

alert( pow(2, 3) );

Просходит следующее:

pow(2, 3)

Запускается функция pow, с аргументами x=2, n=3. Эти переменные хранятся в контексте выполнения, схематично изображённом ниже:

· Контекст: { x: 2, n: 3 }

pow(2, 2)

В строке 2 происходит вызов pow, с аргументами x=2, n=2. Для этой функции создаётся новый текущий контекст (выделен красным), а предыдущий сохраняется в «стеке»:

· Контекст: { x: 2, n: 3 }

· Контекст: { x: 2, n: 2 }

pow(2, 1)

Опять вложенный вызов в строке 2, на этот раз — с аргументами x=2, n=1. Создаётся новый текущий контекст, предыдущий добавляется в стек:

· Контекст: { x: 2, n: 3 }

· Контекст: { x: 2, n: 2 }

· Контекст: { x: 2, n: 1 }

Выход из pow(2, 1).

При вызове pow(2, 1) вложенных вызовов нет. Функция для n==1 тут же заканчивает свою работу, возвращая 2. Текущий контекст больше не нужен и удаляется из памяти, из стека восстанавливается предыдущий:

· Контекст: { x: 2, n: 3 }

· Контекст: { x: 2, n: 2 }

Возобновляется обработка внешнего вызова pow(2, 2).

Выход из pow(2, 2).

…И теперь уже pow(2, 2) может закончить свою работу, вернув 4. Восстанавливается контекст предыдущего вызова:

· Контекст: { x: 2, n: 3 }

Возобновляется обработка внешнего вызова pow(2, 3).

Выход из pow(2, 3).

Самый внешний вызов заканчивает свою работу, его результат: pow(2, 3) = 8.

Глубина рекурсии в данном случае составила: 3.

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

В самом конце, как и в самом начале, выполнение попадает во внешний код, который находится вне любых функций. У такого кода тоже есть контекст. Его называют «глобальный контекст», и он является начальной и конечной точкой любых вложенных подвызовов.

Обратим внимание на требования к памяти. Фактически, рекурсия приводит к хранению всех данных для внешних вызовов в стеке. То есть, возведение в степень n хранит в памяти n различных контекстов.

Реализация степени через цикл гораздо более экономна:

function pow(x, n) {

var result = x;

for(var i=1; i<n; i++) {

result *= x;

}

return result;

}

У такой функции pow будет один контекст, в котором будут последовательно меняться значения i и result.

Любая рекурсия может быть переделана в цикл. Как правило, вариант с циклом будет эффективнее.

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

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

Недостатки и преимущества рекурсии:

Требования к памяти.
Ограничена максимальная глубина стека.
Краткость и простота кода.