Рекурсивный код и стек времени исполнения
Функция — это последовательность инструкций, выполняемых в ответ на ее вызов. Процесс выполнения начинается с того, что вызывающий блок заполняет активизирующую запись (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; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!