Информатика и технология программирования


Особенности программирования рекурсивных функций - часть 2




-фактические параметры рекурсивного вызова представляют начальное состояние для следующего шага, в который производится переход из текущего при рекурсивном вызове;



-автоматические переменные представляют внутренние характеристики процесса на текущем шаге его выполнения;



-внешние переменные представляют глобальное состояние всей системы, через которое отдельные шаги в последовательности могут взаимодействовать между собой.

Из сказанного следует, что формальные параметры рекурсивной функции, внешние и локальные переменные не могут быть взаимозаменяемы, как это иногда делается в обычных функциях. Кроме того, каждый новый рекурсивный вызов порождает новый "экземпляр" формальных параметров и локальных переменных, причем старый "экземпляр" не уничтожается, а сохраняется в стеке по принципу вложенности. Здесь имеет место единственный случай, когда одному имени переменной в процессе работы программы соответствуют несколько ее "экземпляров". Рассмотрим подробнее этот парадокс. Как уже было сказано, рекурсивный вызов функции внешне выглядит как создание в программе ее копии. В действительности же алгоритмическая компонента функции не копируется, а создается копия только с ее локальных данных. Происходит это в такой последовательности :



- в стеке резервируется место для формальных параметров, в которые записываются значения фактических параметров. Обычно это производится в порядке, обратном их следованию в списке ;



- при вызове функции в стек записывается точка возврата - адрес той части программы, где находится вызов функции ;



- в начале тела функции в стеке резервируется место для локальных (автоматических) переменных.

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




Начало  Назад  Вперед