НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №2 з навчальної дисципліни “Програмування складних алгоритмів” Тема: Рекурсивні алгоритми Варіант 7 Київ 20____ Мета: Метою лабораторної роботи є набуття практичних навичок з рекурсивними функціями. Теоретична частина Процес, у якому функція викликає себе прямо чи опосередковано, називається рекурсією, а відповідна функція називається рекурсивною. Використовуючи рекурсивний алгоритм, деякі проблеми можна вирішити досить легко. Рекурсія буває прямою та непрямою. Пряма рекурсія визиває сама себе у функції. А в непрямій рекурсії є дві функції, які по черзі викликають один одного(в функції А() викликається функція В(), а в В() викликається функція А()). Приклад використання рекурсивного алгоритму для знаходження факторіала: int fact(int n) { if (n <= 1) // base case return 1; else return n*fact(n-1); } У наведеному вище прикладі визначено базовий випадок для n <= 1. Більше значення числа можна розв’язати шляхом перетворення до меншого, доки не буде досягнуто базового випадку. Загальне завдання / Завдання по варіанту / Оцінка складності алгоритму Складність алгоритму в обох випадках – O(N). З рекурсією  Величина m Кількість ітерацій Час виконання  10 10 8100нс  50 50 12700нс  500 500 120700нс   Без рекурсії  Величина m Кількість ітерацій Час виконання  10 10 4300нс  50 50 7600нс  500 500 24200нс   Результат роботи / Блок-схема Main: / Рекурсивна функція: / Ітераційна функція: / Висновок: написано програму, що обраховує значення математичної функції двома способами. Один спосіб використовує метод рекурсії для множення, а інший використовує цикл для тієї ж задачі. Було визначено, що використовуючи цикл алгоритм працює бистріше. Але потрібно зауважити що використання рекурсії все одно доречно використовувати в деяких ситуаціях. Програмний код import java.util.*; public class LR2 { public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.print("Введіть кінцеве значення m: "); int m = scan.nextInt(); System.out.print("Введіть початкове значення n: "); int i = scan.nextInt(); System.out.println("Формула: (3i-2)/3i"); long firstTime = System.nanoTime(); double rec = recursion(i, m, 1); firstTime = System.nanoTime() - firstTime; System.out.println("Результат з використанням рекурсії:\n"+rec + "\nЧас виконання: " + firstTime + " наносекунд"); long secondTime = System.nanoTime(); double notRec = notRecursion(i, m); secondTime = System.nanoTime() - secondTime; System.out.println("Результат без використання рекурсії:\n"+notRec + "\nЧас виконання: " + secondTime + " наносекунд"); } public static double recursion(int i, int m, double res) { if(i<=m) return recursion(i+1, m, res * (3*i-2)/(3*i)); return res; } public static double notRecursion(int i, int m) { double res = 1; for(int j=i;j<=m;j++){ res = res * (3*j-2)/(3*j); } return res; } }