Виконання дій на рекурсивному повернені

Для більш детальної демонстрації роботи при повернені, розглянемо програму 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

Writeln (‘Введіть число n’);

Readln (n);

Writeln (‘Факторіал n! = ’, Fact_Up (n));

End.

Таблиця трасування по рівням рекурсії

Поточний рівень рекурсії	Рекурсивний спуск		Рекурсивне повернення
0		Введення (n=5) Fact_Up(5)	Виведення: n!=120;
1		i=5 Mult:=Fact_Up(4);	Fact_Up:=24*5 (120)
2		i=4 Mult:=Fact_Up(3);	Fact_Up:=6*4 (24)
3		i=3 Mult:=Fact_Up(2);	Fact_Up:=2*3 (6)
4		i=2 Mult:=Fact_Up(1);	Fact_Up:=1*2 (2);
5		i=1 Mult:=1;	Fact_Up:=1*1 (1);

Виконання дій як при рекурсивному спуску, так і при повернені

Третю форму рекурсивних підпрограм розглянемо на прикладі наступної задачі.

Приклад .

Вивести на друк символи введеного слова в оберненому порядку. Рішення даної задачі виконано у вигляді програми Reverse_String, яка використовує рекурсивну процедуру Reverse.

Текст програми:

Program Reverse_String;

Procedure Reverse;

Var Ch: Char;

Begin

If Not EоLn Then

Begin

Read (Ch);

Reverse;

Write (Ch)

End

End;

Begin

Writeln (‘Введіть слово ’);

Reverse

End.

Результат виконання програми:

Введіть слово

рон

нор

Приклад.

Написати програму, яка буде друкувати нескінчену кількість разів наступні слова: «Рекурсія, Функція, Процедура». Для виведення цих слів скористатись рекурсивною процедурою.

Текст програми:

Program EndLess1;

Procedure PopeAndDog1;

Begin

Writeln (‘РЕКУРСІЯ’);

Writeln (‘ФУНКЦІЯ’);

Writeln (‘ПРОЦЕДУРА’);

PopeAndDog1;

End;

Begin

PopeAndDog1

End.

Якщо оператор виклику процедури поставити перед виведенням тексту, то така програма нічого не надрукує, хоча і буде працювати безперервно. Це пояснюється тим, що оператор виклику процедури стоїть першим і відповідно виклик нової копії процедури PopeAndDog2 виникне раніше, ніж виведення тексту. В наступній копії процедури будуть виконані аналогічні дії, і так далі. В результаті виникнуть нескінченні виклики процедури PopeAndDog2 без виведення тексту, хоча оператор виведення в процедурі присутній. При виконані на комп‘ютері такі нескінченні звернення до процедури призведуть до переповнення стеку та виникненню помилки виконання програми.

Program EndLess2;

Procedure PopeAndDog2;

Begin

PopeAndDog2;

Writeln(‘РЕКУРСІЯ’);

Writeln(‘ФУНКЦІЯ’);

Writeln(‘ПРОЦЕДУРА’);

End;

Begin

PopeAndDog2

End.