Рекурсивные алгоритмы

Министерство образования Российской Федерации

Ставропольский Государственный университет

Кафедра математического анализа

Курсовая работа на тему:

«Рекурсивные алгоритмы»

Выполнил: студент  3го курса ФМФ специальности ПМИ группы «Б»

Симонян Сергей Олегович

Проверил: Ионисян А. Д.

Ставрополь, 2004 г.

Содержание

Введение.             

Теория рекурсивных алгоритмов.

Дескриптивная теория.

Метрическая теория.

Программная реализация рекурсии.

Общие принципы реализации.

Пример: компилятор Turbo Pascal 7.0.

Заключение.

Список использованной литературы.             

Введение.

Не так давно человечество вступило в новый XXI век – век информации и компьютеров. Благодаря бурному развитию научных, технических и технологических исследований стало возможным хранить огромные объёмы данных и преобразовывать их со скоростями, которые ещё несколько десятилетий назад могли только сниться. При создании сложных информационных систем перед проектировщиками стали нетривиальные задачи, требующие разработки новых концепций программирования.

Для решения проблем такого рода, особенно при учёте человеческого фактора, возникает необходимость обеспечения понятности алгоритма, так называемой «читабельности» исходного кода программы, и как следствие модифицируемости и относительной лёгкости сопровождения конечного программного продукта. Часто этого можно достигнуть включением в  реализацию приложения рекурсивных подпрограмм, механизмы использования которых предоставляются практически всеми современными компиляторами и средами разработки.

Объект называется рекурсивным, если для своего определения или функционирования он прямо или косвенно обращается к объекту в некотором смысле такого же типа. Так, например, в теле рекурсивных подпрограмм, которые будут подробно рассмотрены ниже, в простейшем случае содержится вызов самих себя, но с другими параметрами.

Рекурсия является одним из наиболее мощных и, наверно, самым общим методом научного познания. Она эффективно применяется во многих прикладных и теоретических естественнонаучных дисциплинах, и стала неотъемлемой их частью.

Этому нетрудно найти множество подтверждений, однако один и тот же по сути метод, применительно к различным областям носит различные названия, такие как индукция, рекурсия или рекуррентные соотношения. Различия касаются особенностей использования.

Под индукцией понимается метод доказательства утверждений с формулировкой зависящей от натурального переменного , который строится на базе индукции (правильности утверждения при или ), затем утверждение полагается правильным при и проводится доказательство для .

Термин рекуррентное соотношение связан с американским научным стилем и определяет математическое задание функции с помощью рекурсии.

Важную роль в теории алгоритмов сыграл аппарат рекурсивных функций, разработанный Алонзо Чёрчем и позволивший ему формализовать понятие алгоритма.

Последние двадцать лет получили бурное развитие созданная и глубоко развитая Бенуа Мандельбротом фрактальная геометрия, теория мультифракталов и их приложения. Нужно заметить, что в теориях понятие рекурсии одно из основных. Так, например, многие фрактальные геометрические фигуры, такие как совершенное канторово множество или салфетка Серпинского, определяются рекурсивно [1].

Как видим, понятие рекурсии очень широко и многогранно. В настоящей работе будет освещён лишь один аспект этого понятия, а именно рекурсивные алгоритмы. Они рассмотрены как с позиций теории алгоритмов и теории сложности, так и с точки зрения практического программирования. Читатель сможет узнать, как применять на практике алгоритмы, содержащие рекурсию, а главное когда стоит это делать. Важно сохранять баланс между изящностью и простотой восприятия, присущие рекурсивным алгоритмам, и сложностью его реализации на конкретной вычислительной системе.

Теория рекурсивных алгоритмов.

Дескриптивная теория.

Задача точного определения понятия алгоритма была полностью решена в 30-х годах XX века в двух формах: на основе описания алгоритмического процесса и на основе понятия рекурсивной функции.

Первый подход заключался в том, что был сконструирован формальный автомат, способный осуществлять ограниченный набор строго определённых элементарных операций (машина Тьюринга). Алгоритмом стали называть конечную последовательность таких операций и постулировали предложение, что любой интуитивный алгоритм является алгоритмом и в сформулированном выше смысле. То есть для каждого алгоритма можно подобрать реализующую его машину Тьюринга [2].

Развитие теории конечных автоматов позволило строго доказать алгоритмическую неразрешимость ряда важных математических проблем (10-й проблемы Гильберта [3], проблемы представимости матриц [4]  и др.). Однако её существенным недостатком является невозможность реализации такой полезной конструкции как рекурсия.

Этого недостатка лишён другой подход к формализации понятия алгоритма, развитый Гёделем и Чёрчем. Здесь теория построена на основе широкого класса так называемых частично рекурсивных функций [5].

Замечателен тот факт, что оба данных подхода, а также другие подходы (Марков, Пост) приводят к одному и тому же классу алгоритмически вычислимых функций [6]. Поэтому для дальнейшего изложения мы выберем именно теорию частично рекурсивных функций Чёрча, так как она позволяет доказать не только алгоритмическую разрешимость задач, но и существование для неё рекурсивного алгоритма.

Сначала определим и исследуем сам класс частично рекурсивных функций [7]. Данный класс определяется путем указания конкретных исходных функций и фиксированного множества операций получения новых функций из заданных.

В качестве базисных функций обычно берутся следующие:

1. Нуль- функция: ;

2. Функция следования: ;

3. Функция выбора аргументов: .

Допустимыми операциями над функциями являются операции суперпозиции (подстановки), рекурсии и минимизации.

Операция суперпозиции. Пусть даны -местная функция и функций . Считаем, что функции зависят от одних и тех же переменных .Это можно сделать путем введения фиктивных переменных. Суперпозицией (подстановкой) функций и называется функция

.

Функция на наборе переменных определена тогда и только тогда, когда определены все функции и функция определена на наборе . Операцию суперпозиции обозначают: .

Операция рекурсии (точнее: примитивной рекурсии). Пусть заданы -местная функция и -местная функция . Определим -местную функцию индуктивным образом с помощью соотношений:

;

.

Ясно, что данные соотношения однозначно определяют функцию . считается определённой в том и только в том случае, когда определены  и при . Значит, если неопределено, то и неопределено при . Про функцию говорят, что она получена рекурсией из функций и , и обозначают: .

Операция минимизации. Пусть задана -местная функция . Зафиксируем набор и рассмотрим уравнение относительно :

.

Будем решать данное уравнение, вычисляя последовательно , , и т.д. и сравнивая с . Наименьшее , для которого выполнено уравнение обозначим . При этом считаем, что определено, если определено при всех . В противном случае считаем, что неопределено. Значение есть функция от переменных , про которую говорят, что она получена из минимизацией и обозначают: .

Функция называется частично-рекурсивной, если она может быть получена из базисных функций , , применением конечного числа раз операций суперпозиции, рекурсии и минимизации.

Какая же связь между  частично рекурсивными функциями и теорией алгоритмов? Эту связь устанавливает «тезис Чёрча» [8], для формулировки которого введём понятие вычислимой функции.

Определение [9]. Функция называется алгоритмически вычислимой, если существует алгоритм нахождения значения функции при любом допустимом значении аргумента.

Очевидно, что функции , и алгоритмически вычислимы. Можно доказать, что операции суперпозиции, рекурсии и минимизации сохраняют свойство вычислимости [10]. Значит, все частично рекурсивные функции вычислимы. Тезис Чёрча утверждает, что класс алгоритмически вычислимых функций совпадает с классом всех частично рекурсивных функций. То есть выполняется и обратное включение: все вычислимые функции частично рекурсивны. Принятие данного тезиса позволяет истолковывать доказательство, что некоторая функция не является частично рекурсивной, как доказательство отсутствия алгоритма вычисления ее значений.

Аппарат частично рекурсивных функций позволяет исследовать общие алгоритмические проблемы. Для этого используется метод характеристик. Он заключается в следующем. По конкретной задаче строится соответствующая характеристическая функция, которая затем изучается на вычислимость. Вычислимость её позволяет утверждать разрешимость исходной проблемы. Пусть, например, стоит проблема разрешения предиката [11]. То есть если задан -местный предикат , то необходимо указать алгоритм позволяющий получить значение предиката для каждого набора или доказать, что такого алгоритма нет. Составляем характеристическую функцию:

Теперь если функция не частично рекурсивна, то искомого алгоритма не существует. А доказательство частичной рекурсивности сразу даёт рекурсивный алгоритм разрешения предиката.

Аналогично теоретически можно получить рекурсивное решение любой разрешимой алгоритмической задачи. Однако практическая ценность этого метода невелика, так как доказательства часто неконструктивны, то есть показывают существование решения, но не содержат инструкций, как определить его явно. Требуется дополнительное исследование, нередко чрезвычайно трудоёмкое.

Таким образом, мы выяснили, что для любой алгоритмической задачи, допускающей решение, можно указать рекурсивный разрешающий алгоритм. То есть рекурсивные алгоритмы являются универсальным средством во всех науках использующих понятие алгоритм. С другой стороны из эквивалентности способов формализации алгоритмов по Тьюрингу и по Чёрчу следует важный вывод, что для каждого рекурсивного алгоритма можно указать итерационный, дающий тот же результат.

Метрическая теория.

В предыдущем пункте было показано, что любой алгоритм может быть представлен как в виде, содержащем рекурсию, так и не содержащем её. Тогда в каждом конкретном случае целесообразность использование на практике того или иного типа записи, обосновывается с использованием  метрической теории алгоритмов, или теории сложности. Нужно отметить, что для многих практически важных задач лучшие оценки сложности дают алгоритмы, использующие рекурсию. Рассмотрим несколько примеров.

1.Умножение -разрядных двоичных чисел. Даны два -разрядных двоичных числа и требуется найти их произведение. «Наивный» алгоритм умножения «столбиком» требует битовых операций. Предложим рекурсивный алгоритм для данной задачи. Пусть и - два -битовых числа и пусть , в противном случае дополняем числа слева нулями. Разобьем числа и на две равные части в виде  , и будем рассматривать каждую часть как -разрядное двоичное число. Тогда произведение можно представить в виде

Равенство дает способ вычисления произведения с помощью четырех умножении -разрядных чисел и некоторого числа сложении и сдвигов (умножений на степень числа 2). Действительно, находим

,

где , , . Ясно, что операции сложения и сдвига имеют сложность .

Заметим, что и имеют, вообще говоря, разрядов. Тогда

запишем равенства , и,  следовательно, . Произведение находится с помощью рекурсивного алгоритма на задачах размера . Остальные вычисления можно выполнить за время , поскольку они содержат один из аргументов либо единственный бит или , либо степень числа 2.

Таким образом, число используемых операций ограничено сверху

где - постоянная, отражающая число сложений и сдвигов в алгоритме. Докажем по индукции, что отсюда следует формула . Очевидно, что при начальные условия выполнены. Пусть для формула есть решение рекурсивного соотношения. Тогда имеем (здесь использовано равенство ).).Таким образом явная формула справедлива для . Утверждение доказано.

Ясно, что и данный алгоритм лучше по порядку исходного «наивного» алгоритма. Заметим, что для данной задачи известны и более лучшие алгоритмы [12].