Выполнение действий на рекурсивном спуске

   
На этом шаге мы рассмотрим рекурсивный спуск.

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

   
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. Трассировка значений параметров

   
На следующем шаге мы рассмотрим рекурсивный возврат.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий