Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих - страница 15
Такая структура данных называется стеком. Стек — простая структура данных. А теперь самое неожиданное: все это время вы пользовались стеком, не подозревая об этом!
Стек вызовов
Во внутренней работе вашего компьютера используется стек, называемый стеком вызовов. Давайте посмотрим, как он работает. Предположим, имеется простая функция:
def greet(name):
print "hello, " + name + "!"
greet2(name)
print "getting ready to say bye..."
bye()
Эта функция приветствует вас, после чего вызывает две другие функции. Вот эти две функции:
def greet2(name):
print "how are you, " + name + "?"
def bye():
print "ok bye!"
Разберемся, что происходит при вызове функции.
примечание
В языке Python print тоже является функцией. Чтобы не усложнять пример, мы сделаем вид, что этой функции нет. Просто подыграйте нам.
Предположим, в программе используется вызов greet("maggie"). Сначала ваш компьютер выделяет блок памяти для этого вызова функции.
Затем эта память используется. Переменной name присваивается значение "maggie"; оно должно быть сохранено в памяти.
Каждый раз, когда вы вызываете функцию, компьютер сохраняет в памяти значения всех переменных для этого вызова. Далее выводится приветствие hello, maggie!, после чего следует второй вызов greet2("maggie"). И снова компьютер выделяет блок памяти для вызова функции.
Ваш компьютер объединяет эти блоки в стек. Второй блок создается над первым. Вы выводите сообщение how are you, maggie?, после чего возвращаете управление из вызова функции. Когда это происходит, блок на вершине стека извлекается из него.
Теперь верхний блок в стеке относится к функции greet; это означает, что вы вернулись к функции greet. При вызове функции greet2 функция greet еще не была завершена. Здесь-то и скрывается истинный смысл этого раздела: когда вы вызываете функцию из другой функции, вызывающая функция приостанавливается в частично завершенном состоянии. Все значения переменных этой функции остаются в памяти. А когда выполнение функции greet2 будет завершено, вы вернетесь к функции greet и продолжите ее выполнение с того места, где оно прервалось. Сначала выводится сообщение getting ready to say bye…, после чего вызывается функция bye.
Блок для этой функции добавляется на вершину стека. Далее выводится сообщение ok bye! с выходом из вызова функции.
Управление снова возвращается функции greet. Делать больше нечего, так что управление возвращается и из функции greet. Этот стек, в котором сохранялись переменные разных функций, называется стеком вызовов.
Упражнения
3.1 Предположим, имеется стек вызовов следующего вида:
Что можно сказать о текущем состоянии программы на основании этого стека вызовов?
А теперь посмотрим, как работает стек вызовов с рекурсивными функциями.
Стек вызовов с рекурсией
Рекурсивные функции тоже используют стек вызовов! Посмотрим, как это делается, на примере функции вычисления факториала. Вызов factorial(5) записывается в виде 5! и определяется следующим образом: 5! = 5*4*3*2*1. По тому же принципу factorial(3) соответствует 3*2*1. Рекурсивная функция для вычисления факториала числа выглядит так:
def fact(x):
if x == 1:
return 1
else:
return x * fact(x-1)
В программу включается вызов fact(3). Проанализируем этот вызов строку за строкой и посмотрим, как изменяется стек вызовов. Стоит напомнить, что верхний блок в стеке сообщает, какой вызов fact является текущим.
Здесь важно, что каждый вызов создает собственную копию x. Обратиться к переменной x, принадлежащей другой функции, невозможно.
Стек играет важную роль в рекурсии. В начальном примере были представлены два решения поиска ключа. Вспомните, как выглядел первый:
В этом случае все коробки лежат в одном месте и вы всегда знаете, в каких коробках еще нужно искать ключ.
Но в рекурсивном решении никакой кучи не существует.
Если кучи нет, то как ваш алгоритм узнает, в каких коробках еще нужно искать? Пример:
К этому моменту стек вызовов выглядит примерно так:
«Куча коробок» хранится в стеке! Это стек незавершенных вызовов функции, каждый из которых ведет собственный незаконченный список коробок для поиска. Стек в данном случае особенно удобен, потому что вам не нужно отслеживать коробки самостоятельно — стек делает это за вас.
