Стек вызовов (Call stack)
Стек вызовов — конструкция, образующаяся в памяти когда функции вызывают друг друга.
Во время вызова функции для неё выделяется память (для локальных переменных, аргументов и других объектов), если одна функция вызывает другую функцию, то снова происходит выделение памяти под новый вызов, в то же время, память под первую функцию остаётся занята, до возврата в неё управления. Таким образом стек вызовов состоит из записей или элементов стека вызовов однозначно соответствующих вызовам функций. Стек вызовов работает по принципу LIFO — последняя вызванная функция находится на вершине стека и удаляется из него при завершении.
Рассмотрим функцию print_vector_length для печати длины вектора который начинается в начале координат. На вход функции print_vector_length поступают координаты вектора, вычисляется длина вектора и печатается на экран. Для вычисления длины используется вторая функция calc_distance которая вычисляет расстояние между двумя точками.
from math import sqrt
def calc_distance(x1, y1, x2, y2):
return sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
def print_vector_length(x, y):
length = calc_distance(x, y, 0, 0)
print(length)
print_vector_length(3, 4)
Аналогичная запись на стеке создается и при вызове функции sqrt внутри calc_distance, каждый вызов функции повышает глубину стека вызовов.
Функция, по отношению к записи на стеке вызовов, является шаблоном вычислительного процесса, а запись на стеке вызовов — это данные этого процесса. Каждый вызов функции порождает вычислительный процесс и выделяет для него запись на стеке вызовов. Если функция вызывает саму себя, то образуется несколько независимых записей на стеке вызовов, так как запись на стеке соответствует не функции, а вызову функции.
Чем больше глубина вложенности функций, тем больше будет расти стек вызовов и тем больше будут затраты памяти. Следовательно, глубина вызовов функции ограничена памятью.
Ссылки
- Грокаем алгоритмы. Адитья Бхаргава. Питер. 2018. Глава 3. Рекурсия. Стек. Стек вызовов