Задания № 23, 26 · ЕГЭ

Стек рекурсивных вызовов

Как компьютер хранит незавершённые рекурсивные вызовы
3 мин чтенияСложность: Обновлено 29 сентября 2026

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

Стек рекурсивных вызововНазвание связано с принципом LIFO (Last In, First Out — «последним вошёл, первым вышел»).
Стек рекурсивных вызовов — структура данных, в которой для каждого активного вызова сохраняются параметры, локальные переменные, адрес возврата и промежуточный результат. Вызовы добавляются в стек при углублении рекурсии и удаляются в обратном порядке — последний добавленный вызов завершается первым.

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

\[\text{размер стека} \approx \text{текущая глубина рекурсии}\]
№
Пример: факториал

Вызов factorial(3) порождает цепочку factorial(3) → factorial(2) → factorial(1). В стеке сначала находятся данные для factorial(3), затем для factorial(2), затем для factorial(1). После достижения базового случая \(1!=1\) вызовы завершаются в порядке \(1\), затем \(2\), затем \(3\). Это соответствует дереву рекурсивных вызовов, если рассматривать единственную ветвь.

!
Не путайте со всей памятью программы

Стек вызовов хранит только активные, ещё не завершённые вызовы. Уже завершённый вызов удаляется из стека. Поэтому число всех вызовов за время работы алгоритма может быть намного больше, чем максимальный размер стека. Максимальное число одновременно активных кадров связано с глубиной рекурсии.

Проверка

Что происходит со стеком, когда рекурсивный вызов достигает базового случая?

Главное за минуту

Главное

  • Стек рекурсивных вызовов хранит данные незавершённых вызовов.
  • Кадры добавляются и удаляются по принципу LIFO: последний вызов завершается первым.
  • Максимальный размер стека обычно соответствует максимальной глубине рекурсии.