В. о ректора А. І. Українець (підпис) 2015 р. Т. М. Горлова к.Є. Бобрівник н. В. Ліманська теорія алгоритмів конспект сторінка 6

62
Отримаємо детальну оцінку для гіршого випадку, використовуючи прийняту методику підрахунку елементарних операцій у вигляді:
F
a
ˆ(N) = 2+N*(3+2)+2+(2
N
-1)*{2+N*(3+5)+1+1+f cnt
+2+2} (7.2)
Для отримання значення fcnt
– кількості операцій, необхідних для збільшення лічильника на «1» розглянемо по кроках проходи циклу While, в якому виконується ця операція:
Х кількість проходів в While операцій
001 1
6+2 010 0
2 011 2
2*6+2 100 0
2 101 1
6+2 110 0
2 111 3
3*6+2
Таким чином:
f
cnt
= (1/2)*(2)+(1/2)*(2)+(1/2)*((1/2)*1*6+(1/4)*2*6+(1/8)*3*6+…) =
=2 + 1/2 * 6 * (1/2
1
+2/2
2
+3/2
3
+…) = 2+ 3 * (
∑
k/2
k
);
Оскільки
∑
k*x
k
= x/(1-x)
2
, [5] то
∑
k*(1/2)
k
= (1/2)/(1-(1/2))
2
= 2,
і, відповідно:
f
х
= 8
(! і не залежить від довжини лічильника)
Підстановка f
х
в (7.2) дає:
Fˆ
A
(N) = 4+5*N+(2
N
-1)*(8*N+16),
і остаточно:
Р-парних
Р-непарних вихід з
While
fˇ
х
=2
fˆ
х
=N*6+2
f
=
Θ(1)
∞ k=1

64
8. РЕКУРСИВНІ ФУНКЦІЇ І АЛГОРИТМИ
8.1 Рекурсивні функції
Однією з ідей процедурного програмування,
яка оформилася на початку шістдесятих років ХХ століття, стало активне застосування в практиці програмування деякого методу, заснованого на організації серій взаємних звернень програм (функцій) один до одного. Питання про ефективність використання даного методу при розробці алгоритмічних моделей актуальні і в даний час, незважаючи на існування різних парадигм програмування, створення нових і вдосконалення існуючих мов програмування. Мова йде про рекурсивному методі в програмуванні, який розглядається альтернативним по відношенню до
ітераційного
По суті один і той же метод, стосовно до різних областей носить різні назви – це індукція, рекурсія і рекурентні співвідношення – відмінності стосуються особливостей використання.
Під індукцією розуміється метод доведення тверджень, який будується на базі індукції при n = 0,1, потім твердження покладається правильним при n
= n b
і проводиться доказ для n +1.
Рекурсія – це визначення об'єкта через звернення до самого себе.
Рекурсивний алгоритм – це алгоритм, в описі якого прямо або побічно міститься звернення до самого себе. У техніці процедурного програмування дане поняття поширюється на функцію, яка реалізує рішення окремого блоку завдання за допомогою виклику зі свого тіла інших функцій, в тому числі і себе самої. Якщо при цьому на черговому етапі роботи функція організовує звернення до самої себе, то така функція є рекурсивною.
Термін рекурентні співвідношення пов'язаний з американським науковим стилем і визначає математичне завдання функції за допомогою рекурсії.
Пряме звернення функції до самої себе припускає, що в тілі функції міститься виклик цієї ж функції, але з іншим набором фактичних параметрів.
Такий спосіб організації роботи називається прямою рекурсією. Наприклад, щоб знайти суму перших n натуральних чисел, треба суму перших (n-1) чисел скласти з числом n, тобто має місце залежність: Sn = Sn-1 + n. Обчислення

65 відбувається за допомогою аналогічних міркувань. Такий ланцюжок взаємних звернень в кінцевому підсумку зведеться до обчислення суми одного першого елемента, яка дорівнює самому елементу.
При непрямому зверненні функція містить виклики інших функцій зі свого тіла. При цьому одна або декілька з викладенихя функцій на певному етапі звертаються до вихідної функції зі зміненим набором вхідних параметрів. Така організація звернень називається непрямою рекурсією.
Наприклад, пошук максимального елемента в масиві розміру n можна здійснювати як пошук максимуму з двох чисел: одне з них – це останній елемент масиву, а інше є максимальним елементом в масиві розміру (n-1).
Для знаходження максимального елемента масиву розміру (n-1) застосовуються аналогічні міркування. У підсумку рішення зводиться до пошуку максимального з перших двох елементів масиву.
Рекурсивний метод в програмуванні передбачає розробку рішення задачі, грунтуючись на властивостях рекурсивності окремих об'єктів або закономірностей. При цьому вхідна задача зводиться до вирішення аналогічних підзадач, які є більш простими і відрізняються іншим набором параметрів.
Розробці рекурсивних алгоритмів передує рекурсивна тріада – етапи моделювання завдання, на яких визначається набір параметрів і співвідношень між ними. Рекурсивну тріаду складають параметризація,
виділення бази і декомпозиція.
На етапі параметризації з постановки задачі виділяються параметри, які описують вхідні дані. При цьому деякі подальші розробки рішення можуть вимагати введення додаткових параметрів, які не обумовлені в умови, але використовуються при складанні залежностей. Необхідність у додаткових параметрах часто виникає також при вирішенні завдань оптимізації рекурсивних алгоритмів, в ході яких скорочується їхня тимчасова складність.
Виділення бази рекурсії припускає знаходження в розв'язуваній задачі тривіальних випадків, результат для яких очевидний і не потребує проведення розрахунків. Вірно знайдена база рекурсії забезпечує завершеність рекурсивних звернень, які в кінцевому підсумку зводяться до базового випадку. Перевизначення бази або її динамічне розширення в ході рішення задачі часто дозволяють оптимізувати рекурсивний алгоритм за рахунок досягнення базового випадку за більш короткий шлях звернень.

66
Декомпозиція являє собою зведення загального випадку до більш простих підзадач, які відрізняються від вихідної задачі набором вхідних даних. Декомпозиційні залежності описують не тільки зв'язок між задачам і підзадачами, а й характер зміни значень параметрів на черговому кроці. Від обраних відносин залежить трудомісткість алгоритму, так як для однієї і тієї ж задачі можуть бути складені різні залежності. Перегляд відносин декомпозиції доцільно проводити комплексно, тобто паралельно з коригуванням параметрів і аналізом базових випадків.
Існує декілька категорій завдань, що допускають рекурсивні визначення.
Одна з категорій – математичні формули, визначення яких рекурсивне за своєю суттю.
Основним завданням дослідження рекурсивних функцій є отримання
F(n) в явній або як ще кажуть «замкнутій» формі, тобто у вигляді аналітично заданої функції.
Класичний приклад функції, визначення якої може задаватися в рекурсивної формі, F (n) = n!
F(n)=n*(n-1)*…*1, 0!=1
Рекурсивне визначення цієї функції має вид:
1,
0
( )
* (
1),
0
n
F n
n F n
n
=

= 
− >

де F(n-1)=(n-1)!
Другий приклад – це опис синтаксису конструкцій мов програмування за допомогою Бэкуса Наура форми (БНФ).
Приклад.
Визначення ідентифікатора в мові Паскаль: зараз С++
<літера>::=a|b|…|z,
<цифра>::=0|1|…|9;
<ідентифікатор>::=<літера>|<ідентифікатор><літера>|<ідентифікатор><цифра>.
8.2.
Рекурсивні процедури і функції
Категорії задач, що дозволяють рекурсивні визначення:

67 1.
Задачі, математичні моделі яких записуються у вигляді рекурсивно визначених функцій.
2.
Структура даних задачі визначаться рекурсивним чином. Наприклад: графи, дерева, списки.
3.
Методи рішення задачі допускають рекурсивне визначення (ігри, головоломки тощо)
Рекурсивні алгоритми реалізуються у вигляді підпрограм, які визначаються в програмі, як процедури або функції.
Підпрограма називається рекурсивною, якщо в її визначенні присутній прямо або побічно виклик самої обумовленої підпрограми.
Явна рекурсія характеризується існуванням у визначеній підпрограмі оператора звернення до неї самої.
Неявна (непряма) рекурсія характеризується тим, що одна підпрограма звертається до іншої, яка через ланцюжок викликів інших підпрограм рекурсивно звертається до першої.
Реалізація рекурсивних підпрограм
Стек – структура даних, яка містить впорядкований набір елементів.
Якщо в стек заноситься новий елемент, він додається в кінець упорядкованого набору (на вершину стека). При видаленні елемента він теж вибирається з кінця набору (з вершини стека).
В основі реалізації рекурсивної підпрограми лежить структура даних, що називається стеком, в якому зберігаються всі не глобальні дані, що беруть участь у всіх викликах підпрограми, при яких вона ще не завершила свою роботу.
Стек складається з фрагментів, які становлять блоки послідовних осередків.
Кожен виклик підпрограми використовує фрагмент стека, довжина якого залежить від підпрограми, що викликається.
У загальному випадку при виклику процедурою А процедури В відбувається наступне:
1.
В вершину стека поміщається фрагмент потрібного розміру. До нього входять такі, дані:
(
а) показники фактичних параметрів виклику процедури В;
(б) порожні комірки для локальних змінних, визначених у процедурі В;
(
в) адреса повернення (АВ), тобто адреса команди в процедурі А, яку слід виконати після того, як процедура В закінчить свою роботу.

68
Якщо В – функція, то у фрагмент стеку для В поміщається покажчик осередку у фрагменті стека для А, в якій належить помістити значення цієї функції (адреса значення).
2. Управління передається першому оператору процедури В.
3.
При завершенні роботи процедури В управління передається процедурі А за допомогою наступної послідовності кроків:
(
а) адреса повернення витягується з вершини стеку;
(б) якщо В – функція, то її значення запам'ятовується в комірці, на яку вказує покажчик адреси значення;
(
в) фрагмент стека процедури В витягується з стека, в вершину ставиться фрагмент процедури А;
(г) виконання процедури А поновлюється з команди, зазначеної в адресі повернення.
При виклику підпрограмою самої себе, тобто в рекурсивному випадку, виконується та ж сама послідовність дій.
Рекурсивне визначення складається з двох незалежних частин: базової і
рекурсивної.
Базова частина не є рекурсивним ствердженням, вона задає визначення для деякої фіксованої групи об'єктів і визначає умову закінчення рекурсії. У першому прикладі в базовій частині стверджується, що об'єкт 0! = 1.
Рекурсія і ітерація
Не завжди рекурсивне рішення задачі є кращим, більш прості рішення можуть бути знайдені за допомогою ітерації. Клас функцій, що мають визначення виду
1
( ),
0,
( )
(
( )),
0.
n
n
G x
если n
F x
H F
x
если n
−
=

= 
>

може завжди бути виражений ітеративно так, що застосування рекурсії необов'язково.
Приклад. Необхідно скласти визначення функції для обчислення значений деяких поліномів, визначення яких має наступний вигляд:

69 1
2 0,
0,
( )
2 ,
1,
2 1
( )
( ),
n>1 1
2
n
n
n
если n
S x
x
если n
n
n
S
x
S
x
если
n
n
−
−


=

=
=


−

+
−

Розглянемо ряд прикладів: б) Приклади рекурсивних функцій
1.
ƒ(0)=0
ƒ(n)= ƒ(n-1)+1
Зрозуміло, що ƒ(n)=n.
2.
ƒ(0)=1
ƒ(n)= n*ƒ(n-1)
Послідовна підстановка дає – f(n) = 1*2*3* ... *n = n!
Для повноти відомостей наведемо формулу Стірлінга для наближеного обчислення факторіала для великих n:
n!
≈
(2
π
n)
1/2
*(n
n
)/(e
n
)
3.
ƒ(0)=1
ƒ(1)=1
ƒ(n)= ƒ(n-1)+ ƒ(n-2), n
≥
2
Ця рекурсивна функція визначає числа Фібоначчі: 1 1 2 3 5 8 13, які досить часто виникають при аналізі різних завдань, у тому числі і при аналізі алгоритмів. Відзначимо, що асимптотично f (n) » [1,618 n] [8].
4.
ƒ(0)=1
ƒ(n)= ƒ(n-1)+ ƒ(n-2)+…+1 =
∑
ƒ(i)+1
Для отримання функції в явному вигляді розглянемо її послідовні значення: ƒ(0)=1, ƒ(1)=2, ƒ(2)=4, ƒ(3)=8, що дозволяє припустити, що
ƒ(n)=2
n
, точний доказ виконується по індукції.

70 5.
ƒ(0)=1
ƒ(n)= 2*ƒ(n-1)
Ми маємо справу з прикладом того, що одна і та ж функція може мати різні рекурсивні визначення – f(n) = 2n, як і в прикладі 4, що перевіряється елементарною підстановкою.
6.
ƒ(0)=1
ƒ(1)=2
ƒ(n)= ƒ(n-1)*ƒ(n-2)
У цьому випадку ми можемо отримати рішення в замкнутій формі, зіставивши значенням функції відповідають ступені двійки:
ƒ(2) = 2 = 2
1
ƒ(3) = 4 = 2
2
ƒ(4) = 8 = 2
3
ƒ(5) = 32 = 2
5
ƒ(6) = 256 = 2
8
Позначаючи через F
n
– n -
ое число Фібоначчі, маємо: ƒ(n)=2
Fn
.
8.3
Аналіз трудомісткості рекурсивних алгоритмів методом
підрахунку вершин дерева рекурсії
Рекурсивні алгоритми відносяться до класу алгоритмів з високою ресурсоємністю, так як при великій кількості самовивозу рекурсивних функцій відбувається швидке заповнення стекової області. Крім того, організація зберігання та закриття чергового шару рекурсивного стека є додатковими операціями, які вимагають тимчасових витрат. На трудомісткість рекурсивних алгоритмів впливає і кількість переданих функцією параметрів.
Розглянемо один з методів аналізу трудомісткості рекурсивного алгоритму, який будується на основі підрахунку вершин рекурсивного дерева.
Для оцінки трудомісткості рекурсивних алгоритмів будується повне дерево

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 – кількість регістрів в стеку, що оберігаються,