Рассмотрим первую форму – рекурсивный спуск на примере нахождения факториала натурального числа.
Для реализации универсального алгоритма вычисления факториала, работающего на спуске, в рекурсивную функцию требуется дополнительно ввести два параметра: 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):
| Текущий уровень рекурсии
| Рекурсивный спуск
| Рекурсивный возврат
|
|
| 
| Ввод (n=5)
|
| Fact_Dn (1,1,5)
| Вывод n:= 120
|
|
|
|
| Mult := 1*1
| i := 1
| Fact_Dn (1,2,5)
| Fact_Dn := 120
|
|
|
|
| Mult := 1*2
| i := 2
| Fact_Dn (2,3,5)
| Fact_Dn := 120
|
|
|
|
| Mult := 2*3
| i := 3
| Fact_Dn (6,4,5)
| Fact_Dn := 120
|
|
|
|
| Mult := 6*4
| i := 4
| Fact_Dn (24,5,5)
| Fact_Dn := 120
|
|
|
|
| Mult := 24*5
| i := 5
| i = 120
| Fact_Dn := 120
|
|
