Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського» ЗВІТ до лабораторної роботи № 2 з дисципліни «Програмування складних алгоритмів» Тема «Рекурсивні алгоритми» Варіант № 11 Лабораторна робота № 1: Рекурсивні алгоритми Мета: набуття практичних навичок з рекурсивними функціями. Завдання до лабораторної роботи Розробити програми згідно з алгоритмом з використанням рекурсивної функції та без використання рекурсивної функції. Оцінити час виконання та складність алгоритму. Завдання відповідно до варіанту: / Теоретичні відомості Рекурсія – це побудова методу таким чином, що він викликає сам себе. Рекурсивні виклики методу мають завершуватись при досягненні деякої умови. В іншому випадку відбудеться переповнення пам’яті і програма “зависне” не досягнувши обчислення необхідного результату. Рекурсивний метод – це метод, який сам себе викликає. У рекурсивному методі міститься виклик цього ж методу за його іменем. Послідовний процес рекурсивних викликів методу є подібний до циклічного процесу. Як працює рекурсивний виклик методу? Якщо метод викликає сам себе, то в пам’яті відбуваються наступні процеси: в системному стеку виділяється пам’ять для нових локальних змінних і параметрів; програмний код методу виконується з початку з новими локальними змінними і параметрами. Ці локальні змінні та параметри отримують нові початкові значення. Самий програмний код методу не копіюється; при поверненні з рекурсивного методу відбувається відновлення старих локальних змінних та параметрів а також їх значень у точці виклику цього методу. Рекурсія завжди порівнюється з ітерацією. Для багатьох задач, рекурсія дає наступні взаємопов’язані переваги: при виклику рекурсивної функції не потрібно додатково зберігати тимчасові значення локальних змінних. Компілятор будує код рекурсивної функції таким чином, що тимчасові значення локальних змінних автоматично зберігаються при кожному рекурсивному виклику; у деяких випадках рекурсивні алгоритми виглядають більш спрощено та більш наочно ніж ітераційні. Це пов’язано з тим, що в ітераційних алгоритмах для запам’ятовування проміжних результатів потрібно вводити додаткові змінні, які можуть ускладнити сприйняття ходу виконання самого алгоритму. Порівняно з ітераційними викликами, побудова рекурсивних викликів має такі недоліки: для заданого алгоритму рекурсивні виклики працюють повільніше ніж ітераційні. Це пов’язано з додатковими затратами системних ресурсів на неодноразові виклики методів; багаторазовий виклик методів може призвести до переповнення системного стеку. У цьому випадку середовище CLR згенерує відповідну виключну ситуацію. Тому, важливо, щоб рекурсивний метод був розроблений таким чином, щоб в ньому оголошувалась мінімально можлива кількість параметрів та локальних змінних. Приклад 1. Використання рекурсії для обчислення факторіала числа: int factorial(int i) {   if (i==0) return 1;   else return i*factorial(i-1); } Приклад 2. Приклад обчислення суми ряду: int S(int n) { if (n == 1)     return 5;     else         return 5 * n + S(n - 1); } Результати роботи Без рекурсивної функції: З клавіатури задаємо граничне значення n. Умовним оператором if() перевіряємо це число. Воно має бути більшим 0. Тепер за допомогою циклу for() рахуємо добуток ряду. Обчислюємо часову складність алгоритму. З використанням рекурсивної функції: З клавіатури задаємо граничне значення n. Умовним оператором if() перевіряємо це число. Воно має бути більшим 0. Створюємо функцію func() і передаємо значення n. Рахуємо добуток ряду. У головній функції main() викликаємо func(). Обчислюємо часову складність алгоритму. n Складність Час алгоритму  Без рекурсії 10  O(n) 2.169* 10 −5   20  2.555* 10 −5   50  3.21* 10 −5  З рекурсією 10  2.721* 10 −5   20  2.803* 10 −5   50  3.526* 10 −5   1.4. Лістинг програми та результати роботи Без рекурсії: #include <iostream> #include <cmath> #include <chrono> using namespace std; int main() { double p = 1; int n = 0; cout << "Enter the number:" << endl; cin >> n; if (n <= 0) cout << "Error!" << endl; auto start = chrono::high_resolution_clock::now(); for (int k = 1; k <= n; k++) { p *= sin (k) / k; } auto end = chrono::high_resolution_clock::now(); chrono::duration<float> duration1 = end - start; cout << "Result of algorithm:" << p << endl; cout << "The operating time of the first algorithm: " << duration1.count() << endl; return 0; } Результат роботи програми:/ З рекурсією: #include <iostream> #include <cmath> #include <chrono> using namespace std; double func(int n); int main() { int n = 0; cout << "Enter the number:" << endl; cin >> n; if (n <= 0) cout << "Error!" << endl; auto start = chrono::high_resolution_clock::now(); double p = func(n); auto end = chrono::high_resolution_clock::now(); chrono::duration<float> duration1 = end - start; cout << "Result of algorithm: " << p << endl; cout << "The operating time of the first algorithm: " << duration1.count() << endl; return 0; } double func(int n) { if (n == 0) return 1; else return func(n - 1) * (sin (n) / n); } Результат роботи програми: / 1.5. Висновок У ході виконання лабораторної роботи розроблено програми з використанням та без використання рекурсивної функції. Порівняно часову складність обох алгоритмів, оцінено час виконання та складність алгоритму. Досліджено, що програма без рекурсії працює швидше, ніж інша.