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

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

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

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

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

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

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

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

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

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

Содержание

 TOC o "1-2" f h z u Введение. h 3

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

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

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

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

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

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

Заключение. h 27

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

Введение.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

;

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

Операция минимизации. Пусть задана  и рассмотрим уравнение относительно

.

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

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

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

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

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

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

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

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

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

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

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

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

Равенство дает способ вычисления произведения  с помощью четырех умножении

,

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

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

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

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

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

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

2. Умножение матриц. Даны две квадратные матрицы порядка  с элементами из некоторого кольца  и требуется найти их произведение. Стандартный алгоритм требует  умножений и К. На первый взгляд, кажется, что невозможно сколько-нибудь существенно уменьшить данное число операций, Однако, В. Штрассеном [13] был предложен следующий алгоритм.

Пусть

Пусть  и даны матрицы  может быть вычислена так. Пусть , .

Заметим, в данном алгоритме использовано 7 умножений и 18 сложений и не использована коммутативность умножения.

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

Пусть  - число арифметических операций, используемых в алгоритме на матрицах размера  и  и  формула справедлива. Пусть для  формула действительно следует из соотношений. Имеем при  т.е. наша формула справедлива и для

Рассмотрим теперь в общем виде вопрос о сложности алгоритмов, использующих рекурсию. Из приведенных выше примеров, ясно, что сложность рекурсивных алгоритмов выражается рекуррентными соотношениями. Если в рекурсивном алгоритме используется одна процедура, то значение сложности  для аргументов где  разбивается на  подзадач размера  - некоторая фиксированная константа в рекурсивном алгоритме, при этом функция сложности  определяется рекуррентным соотношением вида:

где  - константа,  - неотрицательные, целочисленные, монотонные функции, характеризующие сложность получения решения исходной задачи размера  из  решений подзадач размера  только при значениях аргументов  вида  Для практических приложений представляет интерес выделение случаев, когда решение  ограничено сверху полиномом от

Легко доказывается, что если функция  удовлетворяет условию: существует  для всех натуральных  не мажорируется сверху никаким полиномом от  [14]. Таким образом, в дальнейшем ограничимся случаем где  - фиксированные целые числа.

Теперь можно доказать, что справедливо следующее утверждение [15]. Пусть дано рекуррентное соотношение

где  - фиксированные константы. Тогда при

Далее вытекает следствие [16], что в предположениях предыдущего утверждения справедливы соотношения

В некоторых случаях рекурсию для задачи размера  удаётся организовать только путем аддитивного уменьшения исходного размера задачи  на некоторую константу  такого типа рекурсивных алгоритмов определяется рекуррентным соотношением вида

где  - фиксированные константы. Например, такая ситуация возникает при решении графических задач. Для такого соотношения при [17]

В некоторых случаях для организации рекурсии используется «квадратичное» разбиение, при котором исходная задача размера  разбивается на  подзадач размера  рекурсивного алгоритма возникает следующее рекуррентное уравнение

где   - фиксированные константы. Оно определяет однозначно функцию  при   таким выражением [18]

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

Для задачи умножения матриц использование базового алгоритма умножения  умножениями для построения рекурсивного алгоритма, сводящего умножение

(в алгоритме Штрассена  и  и получил  еще не решена [19].

Рассмотрим еще один пример применения полученных результатов. Вернемся к задаче умножения чисел в двоичной записи. Зафиксируем натуральное число  и рассмотрим два  и

Разобьем эти числа на  частей

.

Здесь каждое  и

и образуем произведение Поэтому, знание многочлена  позволяет вычислить произведение  за число действий пропорциональное  находим значение  в  точках  (соответственно ) не превышает , где  - некоторая константа, зависящая oт . Ясно, что если  - сложность умножения  для некоторой константы

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

Имеются и более эффективные алгоритмы умножения чисел, но они используют уже не цифровые операции [20].

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

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

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

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

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

Стек – связная структура данных, построенная на принципе «первый пришёл – первый вышел» (First In – First Out, FIFO). То есть вновь добавляемые объекты помещаются в начало, вершину стека, и выбираются они также только из вершины.

Стек является чрезвычайно удобной структурой данных для многих задач вычислительной техники. Наиболее типичной из таких задач является обеспечение вложенных вызовов процедур. Предположим, имеется процедура A, которая вызывает процедуру B, а та в свою очередь - процедуру C. Когда выполнение процедуры A дойдет до вызова B, процедура A приостанавливается и управление передается на входную точку процедуры B. Когда B доходит до вызова C, приостанавливается B и управление передается на процедуру C. Когда заканчивается выполнение процедуры C, управление должно быть возвращено в B, причем в точку, следующую за вызовом C. При завершении B управление должно возвращаться в A, в точку, следующую за вызовом B. Правильную последовательность возвратов легко обеспечить, если при каждом вызове процедуры записывать адрес возврата в стек. Так, когда процедура A вызывает процедуру B, в стек заносится адрес возврата в A; когда B вызывает C, в стек заносится адрес возврата в B. Когда C заканчивается, адрес возврата выбирается из вершины стека - а это адрес возврата в B. Когда заканчивается B, в вершине стека находится адрес возврата в A, и возврат из B произойдет в A.

Механизм вызова функции или процедуры в языке высокого уровня существенно зависит от архитектуры компьютера и операционной системы. В рамках IBM PC совместимых компьютеров, в микропроцессорах семейства Intel, как и в большинстве современных процессорных архитектур, поддерживается аппаратный стек. Аппаратный стек расположен в ОЗУ, указатель стека содержится в паре специальных регистров SS:SP доступных для программиста. Аппаратный стек расширяется в сторону уменьшения адресов, указатель его адресует первый свободный элемент. Выполнение команд CALL и INT, а также аппаратных прерываний включает в себя запись в аппаратный стек адреса возврата. Как передаваемые в процедуру или функцию фактические параметры, так и возвращаемые из них значения помещаются в аппаратный стек специальными командами процессора. Дополнительно сохраняются значения необходимых регистров. Схематично этот механизм иллюстрирован на рисунке 1.

Выполнение команд RET и IRET включает в себя выборку из аппаратного стека адреса возврата и передачу управления по этому адресу. Пара команд - PUSH и POP - обеспечивает использование аппаратного стека для программного решения других задач.

Системы программирования для блочно-ориентированных языков (PASCAL, C, C++ и др.) используют стек для размещения в нем локальных переменных процедур и иных программных блоков. Стек разбит на фрагменты, представляющие собой блоки последовательных ячеек. Каждый вызов подпрограммы использует фрагмент стека, длина которого зависит от вызывающей подпрограммы. При каждой активизации процедуры память для ее локальных переменных выделяется в стеке; при завершении процедуры эта память освобождается. Поскольку при вызовах процедур всегда строго

рисунок 1

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

Таким образом, в общем случае при вызове процедурой A процедуры B происходит следующее:

1. В вершину стека помещается фрагмент нужного размера. В него входят следующие‚ данные:  (а) указатели фактических параметров вызова процедуры В; (б) пустые ячейки для локальных переменных, определенных в процедуре В; (в) адрес возврата, т.е. адрес команды в процедуре A, которую следует выполнить после того, как процедура B закончит свою работу. Если B - функция, то во фрагмент стека для B помещается указатель ячейки во фрагменте стека для A, в которую надлежит поместить значение этой функции (адрес значения).