Рекурсивный код и стек времени исполнения

Функция — это последовательность инструкций, выполняемых в ответ на ее вызов. Процесс выполнения начинается с того, что вызывающий блок заполняет активизирующую запись (activation record), которая включает спи­сок параметров и местоположение следующей инструкции, подлежащей вы­полнению после возврата из блока.

 

 

При вызове функции данные из активизирующей записи заталкиваются в стек, организуемый системой (стек времени исполнения). Данные объеди­няются с локальными переменными и образуют активизирующий фрейм” доступный функции.

 

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

 

Стек времени исполнения

С помощью примера вычисления факториала от 4 мы проиллюстрируем использование активизирующих записей и стека, создаваемого во время вы полнения рекурсивной функции. Начальный вызов факториала производите! из главной программы. После выполнения функции управление возвращается в точку RetLockl, где переменной N присваивается значение 24(4!):

void main (void)

{

 int n;

// поместить в стек запись с помощью вызова FACTORIAL(4)

// RetLockl - адрес присвоения n = FACTORIAL(4)

 n=FACTORIAL(4);

­ RetLockl                                                 *

}

Рекурсивные вызовы в функции FACTORIAL возвращают управление я точку RetLock2, где вычисляется произведение п * (п-1)!. Результат вычисления запоминается в переменной temp, чтобы помочь читателю проследить код и продемонстрировать стек времени исполнения:

long FACTORIAL(long n)

{

 int temp;

 if(n=0}

return 1;

// вытолкнуть из стека активизирующую запись

 else

 {

 // поместить в стек активизирующую запись с помощью вызова

 // FACTORIAL(n-1)

 // Retlock2 - адрес вычисления n * FACTORIAL(n-1).

temp=n*FACTORIAL(n-1);

­ RetLock2

return temp; // вытолкнуть из стека активизирующую запись

}

Для функции FACTORIAL активизирующая запись имеет два поля.

Выполнение FACTORIAL(4) инициирует последовательность из пяти вызовов. На рис. 10.5 показаны активизирующие записи для каждого вызова. Записи входят в стек снизу вверх вместе с вызовом из главной процедуры, занимая нижнюю часть стека.

При обращении к функции FACTORIAL с параметром 0 возникает условие останова, и начинается выполнение последовательности операторов возврата. Когда из стека выталкивается самая верхняя активизирующая запись, управление передается в точку возврата. Очистка стека от активизирующих записей описывается следующими операциями.

 

---

Дата добавления: 2018-10-26; просмотров: 185; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!