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