СТРУКТУРА звіту з лабораторної роботи НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №2 з навчальної дисципліни “Програмування складних алгоритмів” Тема: Рекурсивні алгоритми Мета роботи: метою лабораторної роботи є набуття практичних навичок з рекурсивними функціям. Теоретична частина. Рекурсія (лат. recursio) — метод визначення класу чи об'єкту через попереднє задання одного чи декількох (зазвичай простих) його базових випадків чи методів, а потім заданням на їхній основі правила побудови класу, який визначається. Приклади де використовують рекурсію: факторіал, числа Фібоначчі, геометричні фрактали, задача ‘Ханоївська вежа’. Є також вужче визначення для рекурсії саме для програмування. Рекурсія — виклик підпрограми (функції чи процедури) з неї самої (звичайно з іншими значеннями вхідних параметрів) безпосередньо чи через інші функції. Прямою рекурсією називається рекурсія, при якій всередині тіла деякої функції міститься виклик тієї ж функції. Непрямою рекурсією називається рекурсія, що здійснює рекурсивний виклик функції шляхом ланцюга викликів інших функцій. При цьому всі функції ланцюга, що здійснюють рекурсію, вважаються рекурсивними. Завдання до лабораторної роботи: Розробити програми згідно з алгоритмом з використанням рекурсивної функції та без використання рекурсивної функції. Оцінити час виконання та складність алгоритму. / Опис алгоритму Нерекурсивний алгоритм: нерекурсивний алгоритм реалізується через цикл for. Спочатку програма просить у користувача значення k – верхня межа підсумовування, потім через цикл for k разів виконує обчислення q й додає до минулого значення q. Рекурсивний алгоритм: спочатку програма так само просить ввести k, а потім передає це значення у заздалегідь створену функцію sum. Вміст цієї функції замінює цикл for, який є у алгоритмі без рекурсії. Після обрахунків функцією sum, результат повертається в main, де виводиться за допомогою cout. Складність алгоритму Нерекурсивний алгоритм Значення k Час виконання  5 4.5ns  20 5.2ns  100 10.48ns   Рекурсивний алгоритм Значення k Час виконання  5 4.7ns  20 5.75ns  100 5.91ns   Результати роботи програми Рекурсивна / Нерекурсивна / Програмний код Нерекурсивна / Рекурсивна / Висновок: Виконано завдання двома способами: з використанням цикла for та з використанням рекурсії. Аналіз тривалості виконання обох версій програми показав, що рекурсію краще застосовувати для великої кількості операцій. Оформлений звіт, згідно з вимогами.