Рекурсивный спуск

Для реализации универсального алгоритма вычисления факториала, работающего на спуске, в рекурсивную функцию требуется дополнительно ввести два параметра:

Mult - для выполнения до рекурсивного вызова (то есть на спуске) операции умножения накапливаемого значения факториала на очередной множитель;

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

Программа Factorial_Down, которая использует рекурсивную функцию Fact_Dn, выполняющую вычисления на спуске, имеет такой вид:

Program Factorial_Down;

var n: Integer;

function Fact_Dn(Mult: Longint; i, m: Integer):Longint;

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.

Для демонстрации выполняемых функцией Fact_Dn действий приведем таблицу трассировки значений ее параметров по уровням рекурсии. В этой таблице рассмотрен конкретный случай для n = 5.

Рис.1. Трассировка значений параметров

Рассмотренная выше программа Factorial, использующая рекурсивную функцию Fact, выполняет вычисление факториала на возврате. Но это не совсем очевидно, поскольку в функции Fact рекурсивный вызов и операция умножения совмещены в одном операторе присваивания. Для более понятной демонстрации работы на возврате, приведем программу Factorial_Up, использующую функцию Fact_Up, в которой рекурсивный вызов и оператор накопления факториала разделены явным образом.