ті затвердження при абоВ ), Потім твердження покладається правильним при і проводиться доказ для.
Термін рекурентне співвідношення пов'язаний з американським науковим стилем і визначає математичне завдання функції за допомогою рекурсії.
Важливу роль в теорії алгоритмів зіграв апарат рекурсивних функцій, розроблений Алонзо Черчем і дозволив йому формалізувати поняття алгоритму.
Останні двадцять років отримали бурхливий розвиток створена і глибоко розвинута Бенуа Мандельброт фрактальна геометрія, теорія мультіфракталов та їх додатки. Потрібно зауважити, що в теоріях поняття рекурсії одне з основних. Так, наприклад, багато фрактальні геометричні фігури, такі як вчинене канторова безліч або серветка Серпінського, визначаються рекурсивно [1].
Як бачимо, поняття рекурсії дуже широко і багатогранно. У справжній роботі буде висвітлено лише один аспект цього поняття, а саме рекурсивні алгоритми. Вони розглянуті як з позицій теорії алгоритмів і теорії складності, так і з точки зору практичного програмування. Читач зможе дізнатися, як застосовувати на практиці алгоритми, що містять рекурсію, а головне коли стоїть це робити. Важливо зберігати баланс між вишуканістю і простотою сприйняття, властиві рекурсивним алгоритмам, і складністю його реалізації на конкретній обчислювальної системі.
В В
Теорія рекурсивних алгоритмів.
В
Дескриптивная теорія.
Завдання точного визначення поняття алгоритму була повністю вирішена в 30-х роках XX століття в двох формах: на основі опису алгоритмічного процесу і на основі поняття рекурсивної функції.
Перший підхід полягав у тому, що був сконструйований формальний автомат, здатний здійснювати обмежений набір строго певних елементарних операцій (машина Тьюринга). Алгоритмом стали називати кінцеву послідовність таких операцій і постулювали пропозицію, що будь інтуїтивний алгоритм є алгоритмом і у сформульованому вище сенсі. Тобто для кожного алгоритму можна підібрати реалізовує його машину Тьюринга [2]. p> Розвиток теорії кінцевих автоматів дозволило строго довести алгоритмічну нерозв'язність ряду важливих математичних проблем (10-й проблеми Гільберта [3], проблеми представимости матриць [4] та ін.) Однак її істотним недоліком є ​​неможливість реалізації такої корисної конструкції як рекурсія.
Цього недоліку позбавлений інший підхід до формалізації поняття алгоритму, розвинений Геделем і Черчем. Тут теорія побудована на основі широкого класу так званих частково рекурсивних функцій [5].
Чудовий той факт, що обидва даних підходу, а також інші підходи (Марков, Пост) призводять до одного й того ж класу алгоритмічно вичіслімих функцій [6]. Тому для подальшого викладу ми виберемо саме теорію частково рекурсивних функцій Черча, так як вона дозволяє довести не тільки алгоритмічну розв'язність завдань, а й існування для неї рекурсивного алгоритму.
Спочатку визначимо і д...
