Если вы за несколько предыдущих разделов привыкли к рекурсии, она вам понравилась и теперь вы хотите применять её везде — подождите! На самом деле, за простотой идеи рекурсии скрывается довольно большая цена, которую мы платим при решении объёмных по количеству рекурсивных вызовов задач, и она как раз связана со стеком!

Что такое стек вызовов?

Во время выполнения любого JavaScript-кода интерпретатор пользуется скрытым от нас стеком — стеком вызовов. Чтобы понять, что это такое, давайте посмотрим на упрощённый алгоритм исполнения кода. Посмотрим на следующий код:

function question() {
  const answer = prompt('В чем же смысл жизни?');

  check(answer);
}

function check(answer) {
  alert(answer === '42' ? 'Верно' : 'Нет');
}

question();

Когда вызовется функция question, движок создаст контекст выполнения этой функции и положит в этот самый стек вызовов то, что он сейчас делает, чтобы не забыть:

Стек вызовов в начале исполнения

Сразу же после входа в question мы встречаем другую функцию — prompt. Интерпретатор понимает, что ему сейчас нужно будет приостановить работу над текущей функцией, вызвать другую и выполнить её. А ещё в эту функцию мы передали аргумент, который тоже нужно где-то сохранить, чтобы внутри функции мы могли посмотреть на его значение. Интерпретатор кладёт в стек вызовов функцию prompt, а также аргумент, который мы передали:

Стек вызовов в момент вызова prompt

Не будем вдаваться в подробности реализации prompt и класть в стек функции, которые она вызывает. Когда функция prompt полностью исполнится, интерпретатор удалит её из стека вызовов и вернётся в то же состояние, в котором находился при входе в question. Так как интерпретатор завершил свою работу, ему придётся «вспомнить», на чём он остановился. А для этого теперь достаточно просто посмотреть на «верхушку» нашего стека вызовов. Когда он это сделает, то поймёт, что ему необходимо вернуться в первую строчку (информация о том, в каком именно месте функции находится интерпретатор, тоже хранится в стеке) question, и продолжит своё выполнение оттуда.

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

При чем тут рекурсия?

Когда мы продолжим выполнение, то войдём в функцию check, а в ней сразу же войдём в функцию alert, которая «под капотом» тоже вызовет какие-нибудь встроенные функции... Если она написана не очень добросовестно, то может наплодить огромное количество вызовов подфункций и наполнить стек доверху:

В стеке закончилось место

А так как стек — это всего лишь выделенная память, которая может заканчиваться, то в какой-то момент у нас может не остаться места для хранения информации о новых вызовах. И тогда интерпретатор просто лишится возможности понимать, куда ему возвращаться после завершения обработки функции. Такая ситуация называется переполнением стека, и вы уже могли с ней встречаться в виде ошибки Maximum Call Stack Size Exceeded. Если такое происходит, то движок отказывается работать в подобных условиях и выкидывает исключение.

В той же функции подсчета чисел Фибоначчи, которую мы вспоминаем из раздела в раздел, такая ситуация могла бы произойти, если бы мы попытались посчитать число по индексу, скажем, 1000. Тогда нашему интерпретатору пришлось бы в этот стек класть 1000 объектов, описывающих состояние выполнения! И у нас действительно могло бы закончиться место в стеке быстрее, чем мы досчитали. Более того, все эти объекты занимают дополнительную память. А значит, функции, решаемые через рекурсию, более ресурсозатратны, чем при решении другими способами.

В следующей демонстрации посмотрим на обычные циклы как на альтернативу рекурсии.