Этапы выполнения рекурсивной функции вычисления факториала.

Рассмотрим вычисление y=3! с использованием рекурсивной функции F. Необходимо выполнить оператор y:=F(3). При выполнении этого оператора в оперативной памяти существует участок для хранения значения y.

1) По правилам выполнения оператора присваивания в начале вычисляется выражение, стоящее справа от знака присваивания, что производится с помощью специально отведенного участка статической памяти, в который заносятся все операнды и знаки операций, участвующие в вычислении.

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

Таким образом, при вычислении выражения F(3) порождается динамический экземпляр данных функции F, т. е. под результат работы функции (переменную-результат F) и под параметр-значение k выделяются поименованные участки памяти.

3) В поле параметра-значения передается значение выражения, подставленное на место формального параметра при обращении к функции (т. е. 3).

Если также присутствуют формальные параметры-переменные, то в подпрограмму на их место передаются адреса фактических переменных (в данном примере формальные параметры-переменные отсутствуют).

4) Затем выполняются действия вызванной подпрограммы:

· в функции F выполняется условный оператор: условие 3=0 имеет значение ложь (3≠0), поэтому выполняется оператор присваивания F:=F(k-1)*k;

· вычисляется выражение F(k-1)*k, т. е. возникает новый динамический экземпляр данных функции F, в который передается число 2 как значение параметра-значения, и начинает выполняться функция F, но вычисление выражения F(2)*3 не закончено;

· условие 2=0 имеет значение ложь, поэтому при выполнении оператора F:=F(k-1)*k, вычисляется выражение F(1)*2, т. е. появляется новый динамический экземпляр данных функции F;

· условие 1=0 имеет значение ложь, поэтому при выполнении оператора F:=F(k-1)*k, вычисляется выражение F(0)*1, т. е. порождается новый динамический экземпляр данных функции F;

· условие 0=0 имеет значение истина, поэтому переменной-результату функции присваивается значение 1 – таким образом, функция F(0) выполнилась; значение 1 поступило для вычисления выражения F(0)*1, и динамический экземпляр данных для функции F(0) удалился из памяти;

· вычисляется выражение 1*1, получается 1 – функция F(1) выполнилась; значение 1 поступило для вычисления выражения F(1)*2, и динамический экземпляр данных для функции F(1) удалился из памяти;

· вычисляется выражение 1*2, получается 2 – функция F(2) выполнилась; значение 2 поступило для вычисления выражения F(2)*3, и динамический экземпляр данных для функции F(2) удалился из памяти;

· вычисляется выражение 2*3, получается 6 – функция F(3) выполнилась, динамический экземпляр данных для функции F(3) удалился из памяти.

Значение 6 является результатом вычисления выражения F(3) и записывается в память под именем y (y=6).

Таким образом, рекурсия свойственна циклическим итерационным алгоритмам.

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