Явное использование стека

Стеком называется структура данных, в которой добавление и извлечение данных происходит с одного конца, называемого вершиной стека (рис. 13). Наглядным образом стека может служить стопка тарелок – добавлять или забрать тарелки можно только сверху. Каждая тарелка соответствует элементу данных.

Рис. 13. Наглядное представление стека. Push (проталкивание) – традиционное название для операции добавления данных в стек, Pop (выталкивание) – традиционное название для операции извлечения данных из стека.

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

При рекурсивных вызовах стек вызовов хранит цепочку из данных об одновременно работающих процедурах. Во всех продвинутых средах разработки эту цепочку вместе с запомненными параметрами процедур можно просмотреть во время отладки. Соответствующая команда обычно называется “Call Stack” (в Delphi ей соответствует сочетание клавиш Ctrl – Alt – S).

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

Для начала реализуем в виде класса стек, хранящий параметры процедуры:

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

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

Обратите внимание, что рекурсивные вызовы шли сначала для параметров P2, потом для P3. В нерекурсивной процедуре в стек отправляются сначала параметры P3, а только потом P2. Это связано с тем, что при рекурсивных вызовах в стек, по сути, отправляется недовыполненная часть процедуры, которая в нашем случае содержит вызов Recurs(P3).

Упомянутой выше перестановки можно избежать, если вместо стека использовать очередь – структуру данных, где добавление и извлечение элементов происходит с разных концов. Это будет некоторым отступлением от точной имитации процессов при рекурсивных вызовах. Однако в данном примере это кажется более удобным: каждый рекурсивный вызов будет прямо заменяться добавлением параметров в очередь.