Рекурсивный спуск
Рассмотрим первую форму – рекурсивный спуск на примере нахождения факториала натурального числа.
Для реализации универсального алгоритма вычисления факториала, работающего на спуске, в рекурсивную функцию требуется дополнительно ввести два параметра: Mult – для выполнения до рекурсивного вызова (т.е. на спуске) операции умножения накапливаемого значения факториала на очередной множитель; m - для обеспечения независимости рекурсивной функции от имени конкретной глобальной переменной, т. е. для повышения универсальности функции.
Program FDOWN;
Var n:integer;
Function Fact_Dn(Mult:longint;I,m:integer):logint;
begin
Mult:=Mult*i; {Накопление факториала стоит до }
{оператора рекурсивного вызова, }
{отсюда следует, вычисление на спуск.}
if i=m then Fact_Dn:=Mult
else Fact_Dn:=Fact+Dn(Mult,i+1,m);
end;
Begin
write(‘ввести число n:’);
readln(n);
writeln(‘факториал n!=’,Fact_Dn(1,1,n));
End.
Ниже представлена таблица трассировки значений ее параметров по уровням рекурсии (для n=5):
|
Текущий уровень рекурсии |
Рекурсивный спуск |
Рекурсивный возврат |
||||
|
0 |
|
Ввод (n=5) |
|
Fact_Dn (1,1,5) |
Вывод n:= 120 |
|
|
1 |
|
Mult := 1*1 |
i := 1 |
Fact_Dn (1,2,5) |
Fact_Dn := 120 |
|
|
2 |
|
Mult := 1*2 |
i := 2 |
Fact_Dn (2,3,5) |
Fact_Dn := 120 |
|
|
3 |
|
Mult := 2*3 |
i := 3 |
Fact_Dn (6,4,5) |
Fact_Dn := 120 |
|
|
4 |
|
Mult := 6*4 |
i := 4 |
Fact_Dn (24,5,5) |
Fact_Dn := 120 |
|
|
5 |
|
Mult := 24*5 |
i := 5 |
i = 120 |
Fact_Dn := 120 |
|
Рекурсивный возврат
Рассмотренная в начале лекции программа выполняет вычисление на возврате. Но это не совсем очевидно, так как в функции рекурсивный вызов и операция умножение совмещены в одном операторе присваивания.
Для более понятной демонстрации работы на возврате запишем следующую программу.
Program FactorialUp;
Var n: integer;
Function Fact_Up(I: integer):logint;
Var Mult: longint;
begin
if i=1 then Mult:=1
else Mult:= Fact_Up (i-1);
Fact_Up:= Mult*i;
end;
Begin
write(‘ввести число n:’);
readln(n);
writeln(‘факториал n!=’,Fact_Up(n));
End.
Можно провести следующую аналогию. Представим себе, что мы проходим анфиладу комнат, выполняя предписанные нам действия, распахиваем двери во все новые и новые комнаты, в каждой из которых оставляем записку себе на память. Пройдя комнаты до конца, мы возвращаемся, выполняя указания, записанные на оставленных нами записках, и плотно закрывая за собой двери. Заметим, что указания выполняются в порядке, обратном тому, в котором они оставлялись.
|
Текущий уровень рекурсии |
Рекурсивный спуск |
Рекурсивный возврат |
||||
|
0 |
|
Ввод (n=5) |
Fact_Up(5) |
Вывод n:= 120 |
|
|
|
1 |
|
i := 5 |
Mult := Fact_Up(4) |
Fact_Up := 24*5 |
(120) |
|
|
2 |
|
i := 4 |
Mult := Fact_Up(3) |
Fact_Up := 6*4 |
(4) |
|
|
3 |
|
i := 3 |
Mult := Fact_Up(2) |
Fact_Up := 2*3 |
(6) |
|
|
4 |
|
i := 2 |
Mult := Fact_Up(1) |
Fact_Up := 1*2 |
(2) |
|
|
5 |
|
i := 1 |
Mult := 1 |
Fact_Up := 1*1 |
(1) |
|
