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

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

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

   

program Factorial_Up;
var
  n : Integer;
  function Fact_Up   (i :Integer) : Longint;
  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.

   
Приведем таблицу трассировки по уровням рекурсии, аналогичную таблице для функции Fact_Dn:


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

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



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

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