Прямая рекурсия на примере вычисления факториала

1. Математическая модель функции вычисления факториала.

F(0) = 1,

F(k) = 1*2*3*...*(k-2)*(k-1)*k = F(k-1)*k, для всех k>0

2. Блок-схема алгоритма функции вычисления факториала.

Самостоятельно!

3. Реализация алгоритма функции вычисления факториала на языке PASCAL.

Самостоятельно!

В этом алгоритме новое значение F формируется через предыдущее, т. е. F находится в левой и правой частях оператора присваивания, являясь в правой части составной частью выражения. Из-за этого возникает неоднозначная трактовка: чем является F - переменной или обращением к функции? Для устранения этой неоднозначности принято следующее правило:

если имя функции появляется в выражении, то это – вызов функции;

если имя функции – в левой части оператора присваивания, то это – переменная, в которой формируется результат функции (переменная-результат).

Вызов подпрограммы может использоваться при выполнении этой же подпрограммы. Такая ситуация называется рекурсивным обращением к подпрограмме.

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

Рассмотрим вычисление 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).

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

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