Тема_3: Розширені можливості підпрограм (продовження)
План.
Рекурсивні підпрограми.
Випереджувальне оголошення підпрограм.
Процедурний тип даних.
Побічні ефекти при використанні підпрограм.
1. Рекурсивні підпрограми.
Рекурсивним називаються підпрограми, які містять звернення до себе, тобто, самі себе викликають.
Програми, в яких використовуються рекурсивні підпрограми відрізняються простотою, наочністю і компактністю тексту. Проте за цю простоту доводиться розплачуватися неекономним використанням оперативної пам'яті, оскільки виконання рекурсивних підпрограм вимагає значно більшого розміру оперативної пам'яті під час виконання, ніж не рекурсивних.
Максимальне число рекурсивних викликів процедури без повернень, що виникає під час виконання програми, називається глибиною рекурсії. Число рекурсивних викликів в кожен конкретний момент часу, називається поточним рівнем рекурсії.
Головна вимога до рекурсивних підпрограм полягає в тому, що виклик рекурсивної підпрограми повинен виконуватися за умовою, яка на певному рівні рекурсії стане помилковою. Поки умова істина, то рекурсивний запуск продовжується, в противному випадку запуск закінчується і починається рекурсивне повернення зі всіх викликаних на даний момент копій рекурсивної підпрограми.
Форми рекурсивних підпрограм.
У загальному випадку будь-яка рекурсивна підпрограма (назвемо її Rec) включає певну кількість операторів S і один або кілька операторів рекурсивного виклику.
Структура рекурсивної процедури може мати три різні форми:
Форма з виконанням дій до рекурсивного виклику (з виконанням дій на рекурсивному запуску).
Procedure Rec;
Begin
S;
If умова Then Rec
End;
Форма з виконанням дій після рекурсивного виклику (з виконанням дій під час рекурсивного повернення).
Procedure Rec;
Begin
If умова Then Rec;
S;
End;
Форма з виконанням дій як до, так і після рекурсивного виклику (з виконанням дій як на рекурсивному спуску, так і при рекурсивному поверненні).
Procedure Rec;
Begin
S1;
If умова Then Rec;
S2;
End;
або
Procedure Rec;
Begin
If умова Then
Begin S1;
Rec;
S2;
End;
End;
Усі форми рекурсивних процедур знаходять своє застосування на практиці. Існує багато задач, в тому числі знаходження факторіала, яким не має різниці, яка форма рекурсивної процедури використовується. Але існують класи задач, при вирішення яких програмісту необхідно свідомо управляти ходом роботи рекурсивних процедур і функцій. Такими являються задачі, які використовують спискові та деревоподібні структури даних. Наприклад, при розробці трансляторів широко застосовуються, так звані, атрибутивні дерева розбору, робота з якими потребує від програміста вміння свідомо направляти хід рекурсії: одні дії можна виконувати лише при запуску, а інші – лише при поверненні.
Виконання дій при рекурсивному запуску
Для реалізації універсального алгоритму обчислення факторіала в рекурсивну функцію необхідно ввести два додаткових параметра: Mult – для виконання до рекурсивного виклику (тобто при запуску) операції множення накопичуваного значення факторіала на черговий множник;
Приклад. Програма Factorial_Down, що використовує рекурсивну функцію Fact_Dn для обчислення при запуску.
Текст програми:
Program Factorial_Down;
Var n: Integer;
Function Fact_Dn (Mult: Longint; i, m : Integer) : Integer;
Begin
Mult := Mult * i; {Накопичення факторіала стоїть до оператора рекурсивного виклику. Обчислення виконується при спуску}
If i = m Then Fact_Dn:= Mult
Else Fact_Dn:= Fact_Dn (Mult, i+1, m);
End;
Begin
Writeln (‘Введіть число n’);
Readln (n);
Writeln (‘Факторіал n! = ’, Fact_Dn (1, 1, n));
End.
Дії, які виконує функція Fact_Dn, наведені у таблиці трасування значень її параметрів за рівнями рекурсії. В даній таблиці розглядається конкретний випадок для n = 5.
Поточний рівень рекурсії |
Рекурсивний спуск
|
Рекурсивне повернення
|
||
0 |
|
Введення (n=5) Fact_Dn(1,1,5) |
Виведення: n!=120; |
|
1 |
|
Mult:=1*1 (1) i=1 Fact_Dn(1,2,5) |
Fact_Dn:=1; |
|
2 |
|
Mult:=1*2 (2) i=2 Fact_Dn(2,3,5) |
Fact_Dn:=2; |
|
3 |
|
Mult:=2*3 (6) i=3 Fact_Dn(6,4,5) |
Fact_Dn:=6; |
|
4 |
|
Mult:=6*4 (24) i=4 Fact_Dn(24,1,5) |
Fact_Dn:=24; |
|
5 |
|
Mult:=24*5 (120) i=5 Fact_Dn:=120; |
Fact_Dn:=120; |
|
