Использование стека для организации рекурсивных вызовов

Стек — абстрактный тип данных, представляющий собой список элементов, организованных по принципу ПП-ПВ (от англ. LIFO — «last in — first out»), «последним пришёл — первым вышел».

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

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

В процессорах стек может быть (и обычно бывает) организован на аппаратном уровне, его называют аппаратный стек. Он расположен в ОЗУ, а указатели стека — в специальных регистрах, запись в которые доступна системному программисту.