Процессор

Поддержка возможности рекурсивного вызова

Подробности

Родительская категория: Процессор

Категория: Управление вычислительным процессом

Рекурсивный вызов (когда ПП вызывает сама себя) иногда бывает полезен. Классический пример — вычисление факториала с использованием соотношения

N ! = N * (N-1) !

Другой пример — решение задачи о "Ханойской башне".

Рекурсия при вызове подпрограммы может быть как прямая (ПП вызывает сама себя) так и цепная (подпрограмма A вызывает подпрограмму B, та, в свою очеред,ь вызывает подпрограмму C, а затем подпрограмма C вызывает подпрограмму A).

Проблем при рекурсивном вызове несколько:

1. Запоминание адресов возврата: каждый экземпляр ПП имеет свой адрес возврата;
2. Каждый экземпляр ПП должен иметь собственные наборы внутренних переменных;
3. Иногда требуется, чтобы экземпляры ПП, вызванные позднее, имели доступ к внутренним переменным ранее вызванных экземпляров.

Решение всех этих проблем обеспечивается, когда при вызове ПП в стеке выделяется блок ячеек (стековый кадр) для параметров и временных переменных очередного экземпляра ПП (как в примере, рассмотренном выше). Адресацию внутри стекового кадра удобно делать относительно какого-либо его адреса. Для этого перед вызовом ПП параметры помещаются в стек:

push par1
push par2
call subr

Вначале ПП применяется, как мы уже видели, типовая последовательность команд:

subr: push bp; запоминание старого значения регистра базы bp
mov bp,sp; передача в bp адреса начала стекового кадра

Теперь можно к локальным переменным ПП обращаться, используя адресацию относительно регистра базы:

mov ax,[bp+4]
mov bx,[bp+6]

Для обеспечения возможности использовать параметры и переменные "внешних" экземпляров ПП при рекурсивном вызове стековый кадр должен содержать ссылки на "предыдущие" стековые кадры. В системе команд процессора могут быть команды, облегчающие формирование стекового кадра. Например, в х86 есть команды ENTER и LEAVE:

enter frmsiz, level

Первый параметр команды определяет количество байтов, требуемых в стеке для временных (локальных) переменных. Второй параметр показывает уровень "рекурсивности" (для самого внешнего уровня level=1). Для доступа к элементам стекового кадра используется адресный регистр BP, который указывает на начало (самый старший адрес) стекового кадра.

Структура стекового кадра в х86 включает три компонента (см. рисунок ниже):

• указатель на начало предыдущего стекового кадра (динамическая связь);
• таблица указателей на начала каждого из ранее созданных кадров (индикатор);
• локальные переменные.

Выполнение команды ENTER:

При выполнении команды делаются следующие действия (описание делается в предположении, что происходит рекурсивный вход в подпрограмму):

1. TmpREG = SP; Запомнить адрес начала следующего стекового кадра
2. BP -> в стек; Создание динамической связи
3. Повторить (level-1) раз:; Создание индикатора BP -=2, [BP] -> в стек; Копирование элементов индикатора из предыдущего
   кадра
4. TmpREG -> в стек; Добавление в индикатор ссылки на данный кадр
5. BP = TmpREG; Установить BP на начало создаваемого кадра
6. SP -= frmsiz; Выделение в стеке блока под временные переменные

• < Назад