Лекция: Рекурсивный спуск

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

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, в которой рекурсивный вызов и оператор накопления факториала разделены явным образом.