Рассмотренная в начале лекции программа выполняет вычисление на возврате. Но это не совсем очевидно, так как в функции рекурсивный вызов и операция умножение совмещены в одном операторе присваивания.
Для более понятной демонстрации работы на возврате запишем следующую программу.
Program FactorialUp;
Var n: integer;
Function Fact_Up(I: integer):logint;
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.
Можно провести следующую аналогию. Представим себе, что мы проходим анфиладу комнат, выполняя предписанные нам действия, распахиваем двери во все новые и новые комнаты, в каждой из которых оставляем записку себе на память. Пройдя комнаты до конца, мы возвращаемся, выполняя указания, записанные на оставленных нами записках, и плотно закрывая за собой двери. Заметим, что указания выполняются в порядке, обратном тому, в котором они оставлялись.
| Текущий уровень рекурсии
| Рекурсивный спуск
| Рекурсивный возврат
|
|
| 
| Ввод (n=5)
| Fact_Up(5)
| Вывод n:= 120
|
|
|
|
|
| i := 5
| Mult := Fact_Up(4)
| Fact_Up := 24*5
| (120)
|
|
|
|
| i := 4
| Mult := Fact_Up(3)
| Fact_Up := 6*4
| (4)
|
|
|
|
| i := 3
| Mult := Fact_Up(2)
| Fact_Up := 2*3
| (6)
|
|
|
|
| i := 2
| Mult := Fact_Up(1)
| Fact_Up := 1*2
| (2)
|
|
|
|
| i := 1
| Mult := 1
| Fact_Up := 1*1
| (1)
|
|
