“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи № 2 з навчальної дисципліни “Програмування складних алгоритмів” Тема: РЕКУРСИВНІ АЛГОРИТМИ Варіант 15 Мета роботи: Метою лабораторної роботи є набуття практичних навичок з рекурсивними функціями. Теоретична частина: Рекурсія – це виклик підпрограми (функції чи процедури) з неї самої (звичайно з іншими значеннями вхідних параметрів) безпосередньо чи через інші функції (наприклад, функція А викликає функцію B, а функція B — функцію A). Кількість вкладених викликів функції чи процедури називається глибиною рекурсії. Суть рекурсивного визначення об'єкта в тім, що таке кінцеве визначення здатне описувати нескінченно велике число об'єктів. За допомогою ж рекурсивної програми можливо описати нескінченне обчислення, причому без явних повторень частин програми. Але є один нюанс, варто уникати надлишкової глибини рекурсивного алгоритму, тому що це може призвети до переповнення стеку викликів. Непряма рекурсія – це виклик першою функцією іншої(наприклад вкладеної, а іншою функцією виклик першої. Завдання до лабораторної роботи: Розробити програми згідно з алгоритмом з використанням рекурсивної функції та без використання рекурсивної функції. Оцінити час виконання та складність алгоритму. Завдання о 15-го варіанту: / Блок-схема до рекурсивної функції: / Блок-схема до звичайної реалізації: / Результати роботи програми: Рекурсивна реалізація: Значення n Час виконання, мкс  5 234  10 289  30 295   Нерекурсивний алгоритм: Значення n Час виконання, мкс  5 289  10 384  30 400   / / / Код програми можна переглянути за посиланням на replit: https://replit.com/join/utqmbfvxyc-tr-15fundamient Висновок: Під час виконання даної лабораторної роботи було здобуто практичних навичок у використанні рекурсії. Було реалізовано добуток за допомогою рекурсивної функції, та написано аналог за допомогою нерекурсивної функції. Проведено їх порівняння, та оцінювання часової складності алгоритму. Алогритми виконані вірно, згідно умови. Копія коду: #include <iostream> #include <chrono> using namespace std; long long int recursion(int n) { long long int a = 2*n; if(n > 1) { return a * recursion(n-1); } else { return a; } } long long int defaultAlg(int n) { long long int sum = 1; for(int i = 1; i <= n; i++) { sum *= 2*i; } return sum; } int main() { auto start1 = chrono::steady_clock::now(); cout << "recursive function: " << recursion(5) << endl; auto end1 = chrono::steady_clock::now(); cout << "Elapsed time: " << chrono::duration_cast<chrono::microseconds>(end1 - start1).count() << " ms" << endl; auto start2 = chrono::steady_clock::now(); cout << "Non-recursive function: " << defaultAlg(5) << endl; auto end2 = chrono::steady_clock::now(); cout << "Elapsed time: " << chrono::duration_cast<chrono::microseconds>(end2 - start2).count() << " ms" << endl; }