ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.04.2019
Просмотров: 2336
Скачиваний: 1
71
рекурсії. Воно являє собою граф, вершинами якого є набори фактичних
параметрів при всіх викликах функції, починаючи з першого звернення до
неї, а ребрами – пари таких наборів, відповідних взаємним викликам. При
цьому вершини дерева рекурсії відповідають фактичним викликам
рекурсивних функцій. Слід зауважити, що одні й ті ж набори параметрів
можуть відповідати різним вершинам дерева. Корінь повного дерева
рекурсивних викликів – це вершина повного дерева рекурсії, відповідна
початковим зверненням до функції.
Важливою характеристикою рекурсивного алгоритму є глибина
рекурсивних викликів – найбільше одночасне кількість рекурсивних
звернень функції, що визначає максимальну кількість шарів рекурсивного
стека, в якому здійснюється зберігання відкладених обчислень. Кількість
елементів повних рекурсивних звернень завжди не менше глибини
рекурсивних викликів. При розробці рекурсивних програм необхідно
враховувати, що глибина рекурсивних викликів не повинна перевершувати
максимального розміру стека використовуваного обчислювального
середовища.
При цьому обсяг рекурсії – це одна з характеристик складності
рекурсивних обчислень для конкретного набору параметрів, що представляє
собою кількість вершин повного рекурсивного дерева без одиниці.
8.4
Рекурсивна реалізація алгоритмів
Більшість сучасних мов високого рівня підтримують механізм
рекурсивного виклику, коли функція, як елемент структури мови
програмування, що повертає обчислене значення по своєму імені, може
викликати сама себе з іншим аргументом. Ця можливість дозволяє
безпосередньо реалізовувати рекурсивне обчислення певних функцій.
Рекурсивний алгоритм може бути реалізований ітераційною
послідовністю дій.
Розглянемо приклад рекурсивної функції, що обчислює факторіал: F(n).
If n=0 or n=1
(перевірка можливості прямого обчислення)
Then
F
←
1
Else F
←
n*F(n-1);
( рекурсивний виклик функції)
Return (F);
End;
72
Аналіз трудомісткості рекурсивних реалізацій алгоритмів, очевидно,
пов'язаний як з кількістю операцій, виконуваних при одному виклику
функції, так і з кількістю таких викликів. Графічне представлення
породжуваної даними алгоритму ланцюжка рекурсивних викликів
називається деревом рекурсивних викликів. Більш детальний розгляд
призводить до необхідності врахування витрат як на організацію виклику
функції та передачі параметрів, так і на повернення обчислених значень і
передачу управління в точку виклику.
Можна помітити, що деяка гілка дерева рекурсивних викликів
обривається при досягненні такого значення переданого параметра, при
якому функція може бути обчислена безпосередньо. Таким чином, рекурсія
еквівалентна конструкції циклу, в якому кожен прохід є виконанням
рекурсивної функції з заданим параметром.
Розглянемо приклад для функції обчислення факторіалу (рис 8.1):
Рис 8.1. Дерево рекурсії при обчисленні факторіалу – F(5)
73
Дерево рекурсивних викликів може мати і більш складну структуру,
якщо на кожному виклику породжується кілька звернень – фрагмент дерева
рекурсій для чисел Фібоначчі представлений на рис 8.2.
Рис 8.2. Фрагмент дерева рекурсії при обчисленні чисел Фібоначчі – F(5)
Механізм виклику функції або процедури в мові високого рівня суттєво
залежить від архітектури комп'ютера і операційної системи. У рамках IBM
PC сумісних комп'ютерів цей механізм реалізований через програмний стек.
Які передаються в процедуру або функцію фактичні параметри, так і які
повертаються з них значення, поміщаються в програмний стек спеціальними
командами процесора. Додатково зберігаються значення необхідних регістрів
і адреса повернення в процедуру.
Схематично цей механізм ілюстрований на рис 8.3.
Для підрахунку трудомісткості виклику будемо вважати операції
поміщення слова в стек і вибірку його з стека елементарними операціями у
формальній системі. Тоді при виклику процедури або функції в стек
поміщається адреса повернення, стан необхідних регістрів процесора, адреси
повернених значень і передані параметри. Після цього виконується перехід за
адресою на викликувану процедуру, яка витягує передані фактичні
параметри, виконує обчислення, поміщає їх за вказаними в стеці адресами, і
при завершенні роботи відновлює регістри, виштовхує з стека адресу
повернення і здійснює перехід за цією адресою.
Позначимо через:
m –
кількість фактичних параметрів, що передаються,
k –
кількість значень, що повертаються процедурою,
r –
кількість регістрів в стеку, що оберігаються,
74
маємо:
f
виклик
= m+k+r+1+m+k+r+1 = 2*(m+k+r+1)
елементарних операцій на один виклик і повернення.
Аналіз трудомісткості рекурсивних алгоритмів в частині трудомісткості
самого рекурсивного виклику можна виконувати різними способами в
залежності від того, як формується підсумкова сума елементарних операцій –
розглядом окремо ланцюжка рекурсивних викликів і повернень, або сукупно
по вершинах дерева рекурсивних викликів.
8.5
Аналіз трудомісткості алгоритму обчислення факторіала
Для розглянутого вище рекурсивного алгоритму обчислення факторіала
кількість вершин рекурсивного дерева одно, очевидно, n, при цьому
передається і повертається по одному значенню (m = 1, k = 1), в припущенні
про збереження чотирьох регістрів – r = 4, а на останньому рекурсивному
виклику значення функції обчислюється безпосередньо – в результаті:
fA (n) = n * 2 * (1 + 1 + 4 + 1) + (n-1) * (1 + 3) + 1 * 2 = 18 * n – 2
Відзначимо, що n – параметр алгоритму, а не кількість слів на вході.
75
Рис. 8.3. Механізм виклику процедури з використанням програмного стека
8.6
Питання для
самоконтролю
1) Поняття індукції і рекурсії.
2) Приклади рекурсивного завдання функцій.
3) Рекурсивна реалізація алгоритмів.
4) Трудомісткість механізму виклику функції в мові високого рівня.
5) Рекурсивне дерево, рекурсивні виклики і повернення.
6) Аналіз трудомісткості рекурсивного алгоритму обчислення
факторіала.