осліджувати загальні алгоритмічні проблеми. Для цього використовується метод характеристик. Він полягає в наступному. За конкретної завданню будується відповідна характеристична функція, яка потім вивчається на вичіслімость. Вичіслімость її дозволяє стверджувати разрешимость вихідної проблеми. Нехай, наприклад, стоїть проблема дозволу предиката [11]. Тобто якщо заданий-місний предикат, то необхідно вказати алгоритм дозволяє отримати значення предиката для кожного набору або довести, що такого алгоритму немає. Складаємо характеристичну функцію: В
Тепер якщо функція не частково рекурсивний, то шуканого алгоритму не існує. А доказ часткової рекурсивності відразу дає рекурсивний алгоритм дозволу предиката.
Аналогічно теоретично можна отримати рекурсивне рішення будь вирішуваною алгоритмічної завдання. Проте практична цінність цього методу невелика, оскільки докази часто неконструктивні, тобто показують існування рішення, але не містять інструкцій, як визначити його явно. Потрібне додаткове дослідження, нерідко надзвичайно трудомістке.
Таким чином, ми з'ясували, що для будь алгоритмічної завдання, що допускає рішення, можна вказати рекурсивний дозволяючий алгоритм. Тобто рекурсивні алгоритми є універсальним засобом у всіх науках використовують поняття алгоритм. З іншого боку з еквівалентності способів формалізації алгоритмів по Тьюрингу і по Черч слід важливий висновок, що для кожного рекурсивного алгоритму можна вказати ітераційний, що дає той же результат.
В В В В В В В В В В В В В В В В В В В В В В В В В
Метрична теорія.
У попередньому пункті було показано, що будь-який алгоритм може бути представлений як у вигляді, що містить рекурсію, так і не містить її. Тоді в кожному конкретному випадку доцільність використання на практиці того чи іншого типу запису, обгрунтовується з використанням метричної теорії алгоритмів, або теорії складності. Потрібно відзначити, що для багатьох практично важливих завдань кращі оцінки складності дають алгоритми, використовують рекурсію. Розглянемо кілька прикладів. p> 1.Умноженіе-розрядних двійкових чисел. Дано два-розрядних двійкових числа і потрібно знайти їх твір. В«НаївнийВ» алгоритм множення "стовпчиком" вимагає бітових операцій. Запропонуємо рекурсивний алгоритм для даної задачі. Нехай і - два-бітових числа і нехай, в іншому випадку доповнюємо числа ліворуч нулями. Розіб'ємо числа і на дві рівні частини у вигляді, і будемо розглядати кожну частину як-розрядне двійкове число. Тоді твір можна представити у вигляді
В
Рівність дає спосіб обчислення добутку за допомогою чотирьох множенні-розрядних чисел і деякого числа додаванні і зрушень (множень на ступінь числа 2). Дійсно, знаходимо
,
деВ ,,. Ясно, що операції додавання і зсуву мають складність .
Зауважимо, що і мають, взагалі кажучи, розрядів. Тоді
запишемо рівності, і, отже,. Твір знаходиться за допомогою рекурсивног...
