что такое call stack какие ключевые слова вы знаете

Простое объяснение рекурсии и стека вызовов

Перевод статьи «Recursion and the Call Stack Explained By Reading A Book».

Рекурсия это один из наиболее потрясающих принципов во всех языках программирования.

Нерекурсивные функции (другими словами, функции, которые вы использовали в прошлом), запускались единожды при каждом вызове и возвращали результат благодаря инструкции возврата return.

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

Выглядит это примерно так.

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

Но вместе с тем довольно сложно придумать для этой ситуации аналогию из окружающего мира. И находить аналогии становится еще сложнее, когда мы затрагиваем концепцию стека вызовов (о ней мы еще поговорим).

Кто-то предлагает в качестве аналогии набор коробок, внутри которых спрятаны другие коробки:

Другие предлагают представить себе матрешку:

Но этот пример бесполезен для понимания стека вызовов.

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

Чтобы разобраться в концепциях этой статьи, нужно иметь базовое понимание функций в JavaScript.

Пример 1 — факториалы

Факториалы это самый распространенный пример рекурсии. Вероятно, вы знакомы с понятием факториалов по курсу алгебры.

Факториал числа 3 записывается как 3! и означает 3*2*1, что равно 6.

Это можно выразить при помощи цикла for, где обновление переменной будет происходить вне цикла:

Но с той же целью мы можем использовать и рекурсию. Вместо того чтобы создавать цикл, обновляющий переменную вне своей области видимости, мы можем применить рекурсию и сделать n-1 вызовов, где n — искомый факториал.

Я сначала покажу, как это выглядит в виде кода, а затем мы оценим, как это работает.

Этот код позволяет достигнуть того же результата, что и код, приведенный выше.

Но если вы посмотрите на строку 5, вы заметите, что инструкция return упоминает саму функцию.

Так когда же эта функция вернет итоговое значение? Как нам связать 4 вызова функции, чтобы в итоге вернулось значение 24?

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

Но теперь у нас две концепции — рекурсия и стек вызовов — налагаются одна на другую. Это сложно.

Чтобы визуализировать стек вызовов, давайте представим, сто он строится слева направо. Каждый раз при добавлении блока он добавляется на левом конце стека и сдвигает остальные блоки вправо.

Итак, проходя нашу рекурсивную функцию, мы генерируем стек:

Стек вызовов создается внизу гифки. В конце у нас остается 1*2*3*4, что дает 24.

Этот стек состоит из четырех вызовов функции, и ни один из них не запускается, пока функция не вернет 1. Они остаются в стеке, пока не будет добавлено последнее значение, в данном случае — 1.

Это потому, что каждый из первых трех вызовов в стеке включает ссылку на следующий вызов.

Итак, когда num=4, функция возвращает 4*getFactorial(3). Конечно, функция не может вернуть точное значение, пока мы не узнаем значения getFactorial(3). Вот поэтому нам и нужен стек вызовов!

Рекурсия позволяет функции вызываться бесконечное число раз подряд. При этом обновляется стек вызовов. Итоговое значение возвращается после запуска последнего вызова.

Стек вызовов обновляется слева направо, после чего вы можете прочесть все вызовы в порядке их отработки. Самый последний вызов обрабатывается первым, а первый —последним.

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

Пример 2 — разделение строки

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

Стоит задача: развернуть строку.

То есть, нужно вернуть строку, где буквы строки, переданной в качестве input, будут записаны в обратном порядке.

Это тоже можно сделать при помощи цикла for, но мы воспользуемся рекурсией.

Давайте подумаем, как нам развернуть слово «cat».

При каждом вызове функции нам нужно отделить первую (или последнюю) букву в строке, а затем вырезать ее из строки. При повторном запуске функции мы опять берем первую (или последнюю) букву.

В конечном итоге стек вызовов позволит нам вернуть буквы в нужном порядке.

Давайте разберем его, как мы делали в первом примере.

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

Этот пример имеет одно важное отличие от предыдущего: мы осуществляем конкатенацию строки, а не умножение.

Поэтому порядок строк в этой инструкции return имеет большое значение, ведь он определяет порядок дальнейшего объединения.

Поскольку это не серия операций умножения, здесь немного проще понять стек вызовов. Вот как это выглядит:

Когда мы строим стек вызовов так, как показано на гифке, у нас есть определенный порядок вызовов рекурсивной функции и фрагментов строки. Этот порядок очень важен.

Когда мы осуществим все вызовы в стеке, этот порядок позволит нам воссоздать строку в обратном порядке.

Источник

Контекст выполнения и стек вызовов в JavaScript

Если вы — JavaScript-разработчик или хотите им стать, это значит, что вам нужно разбираться во внутренних механизмах выполнения JS-кода. В частности, понимание того, что такое контекст выполнения и стек вызовов, совершенно необходимо для освоения других концепций JavaScript, таких, как поднятие переменных, области видимости, замыкания. Материал, перевод которого мы сегодня публикуем, посвящён контексту выполнения и стеку вызовов в JavaScript.

Контекст выполнения

Контекст выполнения (execution context) — это, если говорить упрощённо, концепция, описывающая окружение, в котором производится выполнение кода на JavaScript. Код всегда выполняется внутри некоего контекста.

▍Типы контекстов выполнения

В JavaScript существует три типа контекстов выполнения:

Стек выполнения

Стек выполнения (execution stack), который ещё называют стеком вызовов (call stack), это LIFO-стек, который используется для хранения контекстов выполнения, создаваемых в ходе работы кода.

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

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

Изучим эту идею с помощью следующего примера:

Вот как будет меняться стек вызовов при выполнении этого кода.

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

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

Когда функция first() завершает работу, её контекст извлекается из стека и управление передаётся глобальному контексту. После того, как весь код оказывается выполненным, движок извлекает глобальный контекст выполнения из текущего стека.

О создании контекстов и о выполнении кода

До сих пор мы говорили о том, как JS-движок управляет контекстами выполнения. Теперь поговорим о том, как контексты выполнения создаются, и о том, что с ними происходит после создания. В частности, речь идёт о стадии создания контекста выполнения и о стадии выполнения кода.

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

Перед выполнением JavaScript-кода создаётся контекст выполнения. В процессе его создания выполняются три действия:

Привязка this

В глобальном контексте выполнения this содержит ссылку на глобальный объект (как уже было сказано, в браузере это объект window ).

В контексте выполнения функции значение this зависит от того, как именно была вызвана функция. Если она вызвана в виде метода объекта, тогда значение this привязано к этому объекту. В других случаях this привязывается к глобальному объекту или устанавливается в undefined (в строгом режиме). Рассмотрим пример:

Лексическое окружение

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

В лексическом окружении имеется два компонента:

Лексическое окружение можно представить в виде следующего псевдокода:

Окружение переменных

Окружение переменных (Variable Environment) — это тоже лексическое окружение, запись окружения которого хранит привязки, созданные посредством команд объявления переменных ( VariableStatement ) в текущем контексте выполнения.

Так как окружение переменных также является лексическим окружением, оно обладает всеми вышеописанными свойствами лексического окружения.

Рассмотрим примеры, иллюстрирующие то, что мы только что обсудили:

Схематичное представление контекста выполнения для этого кода будет выглядеть так:

Только что мы только что описали, называется «поднятием переменных» (Hoisting). Объявления переменных «поднимаются» в верхнюю часть их лексической области видимости до выполнения операций присвоения им каких-либо значений.

▍Стадия выполнения кода

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

Итоги

Только что мы обсудили внутренние механизмы выполнения JavaScript-кода. Хотя для того, чтобы быть очень хорошим JS-разработчиком, знать всё это и не обязательно, если у вас имеется некоторое понимание вышеописанных концепций, это поможет вам лучше и глубже разобраться с другими механизмами языка, с такими, как поднятие переменных, области видимости, замыкания.

Уважаемые читатели! Как вы думаете, о чём ещё, помимо контекста выполнения и стека вызовов, полезно знать JavaScript-разработчикам?

Источник

Просмотр стека вызовов и использование окна “Стек вызовов” в отладчике

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

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

[Frames below may be incorrect and/or missing, no symbols loaded for name.dll]

Окно Стек вызовов аналогично перспективе “Отладка” в некоторых интегрированных средах разработки, например Eclipse.

Отображаемые диалоговые окна и команды меню могут отличаться от описанных здесь в зависимости от текущих параметров или выпуска. Чтобы изменить параметры, выберите в меню Сервис пункт Импорт и экспорт параметров. См. раздел Сброс параметров.

Просмотр стека вызовов в отладчике

Во время отладки в меню Отладка выберите Окна > Стек вызовов.

Желтая стрелка указывает на кадр стека, в котором находится указатель выполнения. По умолчанию это кадр стека, сведения которого отображаются в окнах: исходного кода, Локальные, Контрольные значения, Видимые и Дизассемблированный код. Чтобы изменить контекст отладчика на другой кадр стека, переключитесь на другой кадр стека.

Отображение непользовательского кода в окне “Стек вызовов”

Непользовательский код — это любой код, который не отображается при включении режима Только мой код. В управляемом коде кадры непользовательского кода скрыты по умолчанию. Вместо кадров непользовательского кода отображается следующая запись.

Переключение на другой кадр стека (изменение контекста отладчика)

В окне Стек вызовов щелкните правой кнопкой кадр стека, код и данные которого нужно просмотреть.

Или можно дважды щелкнуть кадр в окне Стек вызовов, чтобы переключиться на этот кадр.

Выберите пункт Перейти к кадру.

Рядом с выбранным кадром стека появится зеленая стрелка с фигурным концом. Указатель выполнения остается в исходном кадре, который по-прежнему отмечен желтой стрелкой. При выборе команд Шаг или Продолжить в меню Отладка выполнение продолжится с исходного, а не с выбранного кадра.

Просмотр исходного кода функции в стеке вызовов

Выполнение кода до определенной функции из окна “Стек вызовов”

Установка точки останова в точке выхода вызова функции

Отображение вызовов в другой поток или из него

Визуальная трассировка стека вызовов

В Visual Studio Enterprise (только) можно просматривать карты кода для стека вызовов во время отладки.

В окне Стек вызовов откройте контекстное меню. Выберите Показать стек вызовов на карте кода (CTRL + SHIFT + ` ).

Просмотр дизассемблированного кода функции в стеке вызовов (C#, C++, Visual Basic, F#)

Включение или отключение отображения дополнительных сведений

Загрузка символов для модуля (C#, C++, Visual Basic, F#)

Чтобы загрузить символы

В окне Стек вызовов щелкните правой кнопкой какой-либо кадр стека, для которого не загружены символы. Кадр затеняется.

Укажите на параметр Загрузить символы, а затем выберите Серверы символов (Майкрософт) (если доступно) или перейдите по пути к символам.

Установка пути к символам

В окне Стек вызовов выберите пункт Параметры символов из контекстного меню.

Появится диалоговое окно Параметры, открытое на странице Символы.

Выберите Параметры символов.

В диалоговом окне Параметры щелкните значок “Папка”.

В поле Места размещения файлов символов (.pdb) появится курсор.

Введите путь к каталогу с символами на компьютере, на котором производится отладка. При локальной и удаленной отладке это путь на локальном компьютере.

Нажмите кнопку OK, чтобы закрыть диалоговое окно Параметры.

Источник

Что такое call stack?

Когда-то был оператор goto, и программы выглядели так

Мы что-то проверяем, если проверка успешна, вызываем какое-то действие. Затем возвращаемся назад.
Но такой вариант оказался неудобным, если это какое-то действие нужно вызывать из разных мест, а потом возвращаться именно в эти разные места. Поэтому сейчас используется не goto, а call (вызов), который кладет в стек адрес текущего места выполнения и переходит в подпрограмму. В конце подпрограммы по команде return, он берет из стека адрес и по нему возвращается назад.
Так как в стек можно положить что-то еще, то можно внутри вызванной подпрограммы вызвать другую подпрограмму, и рекурсивно вызывать столько раз сколько нужно. Потом все call-ы будут красиво закрыты return-ами в обратном порядке.

В данном варианте у нас работает так:
1. из основной части main, вызывается program1 (в стек кладется адрес этой)
2. из вызванного program1 вызывается program3 (в стек добавляется адрес этой команды, там уже две)
3. из program3 мы возвращаемся, беря последнее значение из стека (возвращаемся в program1)
4. снова возвращаемся, беря адрес из стека и попадаем в main
5. тоже самое с вызовом program2-program3-program2-main

Стек обычно растет сверху вниз, каждая команда return берет самый последний нижний адрес и возвращается по нему, что позволяет создавать множество вложенных вызовов, и рекурсивно с ними работать.
Но не нужно забывать, что стек не бесконечен. десять или сто вызовов вообще ни о чем на современных компах, но миллион или миллиард, умножить на размер адреса (например 4 байта), может занять мегабайты и гигабайты.

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

Call stack trace of exception:

Английский не очень хорошо знаю,

Источник

Контекст выполнения и стек вызовов в JavaScript

Если вы — JavaScript-разработчик или хотите им стать, это значит, что вам нужно разбираться во внутренних механизмах выполнения JS-кода. В частности, понимание того, что такое контекст выполнения и стек вызовов, совершенно необходимо для освоения других концепций JavaScript, таких, как поднятие переменных, области видимости, замыкания. Материал посвящён контексту выполнения и стеку вызовов в JavaScript.

Контекст выполнения

Контекст выполнения (execution context) — это, если говорить упрощённо, концепция, описывающая окружение, в котором производится выполнение кода на JavaScript. Код всегда выполняется внутри некоего контекста.

Типы контекстов выполнения

В JavaScript существует три типа контекстов выполнения:

Стек выполнения

Стек выполнения (execution stack), который ещё называют стеком вызовов (call stack), это LIFO-стек, который используется для хранения контекстов выполнения, создаваемых в ходе работы кода.

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

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

Изучим эту идею с помощью следующего примера:

Вот как будет меняться стек вызовов при выполнении этого кода.

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

Когда функция first() завершает работу, её контекст извлекается из стека и управление передаётся глобальному контексту. После того, как весь код оказывается выполненным, движок извлекает глобальный контекст выполнения из текущего стека.

О создании контекстов и о выполнении кода

До сих пор мы говорили о том, как JS-движок управляет контекстами выполнения. Теперь поговорим о том, как контексты выполнения создаются, и о том, что с ними происходит после создания. В частности, речь идёт о стадии создания контекста выполнения и о стадии выполнения кода.

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

Перед выполнением JavaScript-кода создаётся контекст выполнения. В процессе его создания выполняются три действия:

Концептуально контекст выполнения можно представить так:

Привязка this

В глобальном контексте выполнения this содержит ссылку на глобальный объект (как уже было сказано, в браузере это объект window ).

В контексте выполнения функции значение this зависит от того, как именно была вызвана функция. Если она вызвана в виде метода объекта, тогда значение this привязано к этому объекту. В других случаях this привязывается к глобальному объекту или устанавливается в undefined (в строгом режиме). Рассмотрим пример:

Лексическое окружение

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

В лексическом окружении имеется два компонента:

Существует два типа лексических окружений:

Существует два типа записей окружения:

В результате, в глобальном окружении запись окружения представлена объектной записью окружения, а в окружении функции — декларативной записью окружения.

Лексическое окружение можно представить в виде следующего псевдокода:

Окружение переменных

Окружение переменных (Variable Environment) — это тоже лексическое окружение, запись окружения которого хранит привязки, созданные посредством команд объявления переменных ( VariableStatement ) в текущем контексте выполнения.

Так как окружение переменных также является лексическим окружением, оно обладает всеми вышеописанными свойствами лексического окружения.

Рассмотрим примеры, иллюстрирующие то, что мы только что обсудили:

Схематичное представление контекста выполнения для этого кода будет выглядеть так:

То что мы только что описали, называется «поднятием переменных» (Hoisting). Объявления переменных «поднимаются» в верхнюю часть их лексической области видимости до выполнения операций присвоения им каких-либо значений.

Стадия выполнения кода

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

Итоги

Только что мы обсудили внутренние механизмы выполнения JavaScript-кода. Хотя для того, чтобы быть очень хорошим JS-разработчиком, знать всё это и не обязательно, если у вас имеется некоторое понимание вышеописанных концепций, это поможет вам лучше и глубже разобраться с другими механизмами языка, с такими, как поднятие переменных, области видимости, замыкания.

Источник