Міністерство освіти і науки Національний університет “Львівська політехніка” Кафедра ЕОМ / Звіт з лабораторної роботи № 4 з дисципліни: “Алгоритми та методи обчислень” на тему: “Побудова та аналіз складності рекурсивних алгоритмів” Мета лабораторної роботи Вивчити основні методи організації рекурсивних алгоритмів та дослідження їх ефективності. Теоретичні відомості Термін рекурсія дуже популярний у математиці і програмуванні. У широкому смислі, рекурсія — це звертання до самого себе (цей термін походить від латинського слова recursio — повернення). Популярність рекурсії в програмістів у значній мірі пояснюється тим, що вона робить стиль програмування більш декларативним. Це означає, що при складанні алгоритму рішення задачі програміст іноді може схитрувати — звести рішення цієї задачі до рішення тієї ж самої задачі, але при більш простих початкових умовах. Тим самим, він як би «перекладає на плечі» комп'ютера складання дрібних деталей алгоритму. Якщо ж складання всіх навіть самих дрібних деталей алгоритму програміст залишає за собою, його стиль програмування називають не декларативним, а процедурним. Як приклад розглянемо задачу знаходження максимального серед N чисел. Можна запропонувати наступний спосіб її розв'язання: Якщо чисел всього два, то їх треба порівняти і взяти більше. Якщо ж чисел більше, ніж два, треба взяти кожне з них (перше, що трапилося), вирішити вихідну задачу обрахування максимального числа серед чисел, що залишилися, порівняти результат з першим числом і взяти більше. На перший погляд у цьому рішенні є якась недомовленість — для знаходження максимального серед N чисел пропонується знайти максимальне серед N-1 числа. Але, як це не парадоксально, представлений рекурсивний алгоритм рішення даної задачі є цілком коректним. А програма, у якій цей алгоритм реалізований, видає правильний результат. Індивідуальне завдання Варіант 12 Написати програму для ітераційної та рекурсивної форм обчислення значення функції згідно з варіантом Для рекурсивної форми обчислення використати рекурсивну функцію з виконанням дій на рекурсивному під’омі (для парних варіантів) або на рекурсивному спуску (для непарних варіантів). Порівняти ефективності ітераційної та рекурсивної форм обчислення значення функції. Обчислити значення функції:
Код програми #include <iostream> #include <conio.h> #include <cmath> using namespace std; unsigned long long factorial(int value) { if (value < 0) throw "value < 0"; if (value == 0) return 1; else return value * factorial(value - 1); } long long recursion(int n, unsigned long long factorial) { if (n < 0) throw "n < 0"; if (n == 0) return 0; else { if (n & 1) return recursion(n - 1, factorial / n) + factorial; else return recursion(n - 1, factorial / n) - factorial; } } inline long long recursion(int n) { return recursion(n, factorial(n)); } void main() { try { for (int i = 1; i <= 10; i++) { cout << "n = " << i << ": " << recursion(i) << endl; } cout << "n = -1: "; cout << recursion(-1) << endl; } catch (char str[]) { cout << "Error: " << str << endl; } _getch(); } Результат виконання програми / Висновок Я вивчив основні методи організації рекурсивних алгоритмів та дослідив їх ефективність.