Читать онлайн «Теория рекурсии для программистов»

УДК 519. 6 ББК 22. 19 Г61 Г о л о в е ш к и н В. А. , У л ь я н о в М. В. Теория рекурсии для програм­ мистов. - М. : ФИЗМАТЛИТ, 2006. - 296 с. - ISBN 5-9221-0721-6. Книга является учебным пособием по теории рекурсии в аспекте ее при­ менения в области программирования. В ней рассматриваются основы теории рекурсии и ее использование в области разработки и анализа рекурсивных алгоритмов. Приводятся основные сведения о рекурсивных последовательно­ стях и функциях, даны примеры рекурсивных алгоритмов, разработанных на основе рекуррентных соотношений, метода декомпозиции и метода ди­ намического программирования, излагаются методы разработки рекурсивных алгоритмов и их теоретического анализа, в том числе элементы теории ре­ сурсной эффективности вычислительных алгоритмов. Детально изложены ме­ тоды анализа рекурсивных алгоритмов, проиллюстрированные целым рядом примеров. Приложение содержит тексты программ, реализующих рекурсивные алгоритмы, рассмотренные в основном тексте книги, и результаты экспери­ ментальных исследований. Учебное пособие ориентировано на специалистов в области информатики и анализа алгоритмов, разработчиков алгоритмического обеспечения и предназначено для студентов, аспирантов и преподавателей вузов, специализирующихся в области математической информатики, теории рекурсии, разработки, анализа и исследования рекурсивных алгоритмов. © ФИЗМАТЛИТ, 2006 ISBN 5-9221-0721-6 © В. А. Головешкин, М. В. Ульянов, 2006  ОГЛАВЛЕНИЕ Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Г л а в а 1. Введение в теорию рекурсии . . . . . . . . . . . . . . . . . . . . 11 § 1. Основные понятия и определения . . . . . . . . . . . . . . . . . . . . . . 11 § 2. Рекурсивно заданные последовательности и функции . . . . . . . . . 23 § 3. Классификация рекурсивно заданных последовательностей и функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 § 4. Методы исследования и решения рекуррентных соотношений . . . 36 Задачи и упражнения к главе 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 50 Список литературы к главе 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 Г л а в а 2. Рекурсивные алгоритмы и особенности их программных реализаций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 § 1. Рекурсивные алгоритмы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 § 2. Особенности программных реализаций рекурсивных алгоритмов 56 § 3.