НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №2 з навчальної дисципліни “Програмування складних алгоритмів” Тема: Рекурсивні алгоритми Варіант 13 Мета: Метою лабораторної роботи є набуття практичних навичок з рекурсивними функціями. Завдання до лабораторної роботи: Розробити програми згідно з алгоритмом з використанням рекурсивної функції та без використання рекурсивної функції. Оцінити час виконання та складність алгоритму. Теоретична частина У програмуванні рекурсія — виклик підпрограми (функції чи процедури) з неї самої (звичайно з іншими значеннями вхідних параметрів) безпосередньо чи через інші функції (наприклад, функція А викликає функцію B, а функція B — функцію A). Кількість вкладених викликів функції чи процедури називається глибиною рекурсії. Міць рекурсивного визначення об'єкта в тім, що таке кінцеве визначення здатне описувати нескінченно велике число об'єктів. За допомогою ж рекурсивної програми можливо описати нескінченне обчислення, причому без явних повторень частин програми. Існує спеціальний тип рекурсії, називаний «хвостовою рекурсією». Інтерпретатори і компілятори функціональних мов програмування, що підтримують оптимізацію коду (вихідного та/або такого, що виконується), реалізують хвостову рекурсію в обмеженому обсязі пам'яті за допомогою ітерацій. Варто уникати надлишкової глибини рекурсії, бо це може викликати переповнення стека викликів. Завдання / Результат роботи / Програмний код private static double getRecursedMulti(int b, int n) { if (b > n) return 1.0; return (double)(1.0/(2.0*b - 1)) * getRecursedMulti(b+1, n); } private static double getNotRecursedMulti(int b, int n) { double multi = 1.0; for (; b <= n; b++) { multi *= 1.0/(2.0*b - 1); } return multi; } Висновки: Розроблено алгоритм з використанням та без використання рекрсії. При однаковій складності рекурсивної або безрекурсивної розробки час виконання у наносекундах повинен різнитись, але, на жаль, відомі методи вимірювання часу не здібні відловити різницю у часі через примітивність алгоритму (різниця є меншою за мілісекунду).