Файл: Рекурсивные алгоритмы.doc

Введение. 9

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Носов В.А. Основы теории алгоритмов и анализа их сложности. – М., 1992. 11

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

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

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

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

. 12

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

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

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

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

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

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

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

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

Стек является чрезвычайно удобной структурой данных для многих задач вычислительной техники. Наиболее типичной из таких задач является обеспечение вложенных вызовов процедур. Предположим, имеется процедура 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. 25

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

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

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

27

рисунок 1 27

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

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

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

2. Управление передается первому оператору процедуры B. 28

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

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

Этот прием делает возможной легкую реализацию рекурсивных процедур. Когда процедура вызывает сама себя, то для всех ее локальных переменных выделяется новая память в стеке, и вложенный вызов работает с собственным представлением локальных переменных. Когда вложенный вызов завершается, занимаемая его переменными область памяти в стеке освобождается и актуальным становится представление локальных переменных предыдущего уровня. За счет этого в языках PASCAL и C любые процедуры и функции могут вызывать сами себя. В языке PL/1, где по умолчанию приняты другие способы размещения локальных переменных, рекурсивная процедура должна быть определена с описателем RECURSIVE - только тогда ее локальные переменные будут размещаться в стеке. 28

Рекурсия использует стек в скрытом от программиста виде, но все рекурсивные процедуры могут быть реализованы и без рекурсии, но с явным использованием стека. Пример подобной «развертки» рекурсии можно увидеть в реализации быстрой сортировки Хоара через стек . 28

Один проход сортировки Хоара разбивает исходное множество на два множества. Границы полученных множеств запоминаются в стеке. Затем из стека выбираются границы, находящиеся в вершине, и обрабатывается множество, определяемое этими границами. В процессе его обработки в стек может быть записана новая пара границ и т.д. При начальных установках в стек заносятся границы исходного множества. Сортировка заканчивается с опустошением стека. 28

Хочется заметить, что для сортировки используется именно реализация на основе массива. Действительно, основное требование к сортировке - быстрота, а операции с массивом выполняются значительно быстрее, нежели переход по указателям. Память же, требуемая под стек в данном алгоритме - , константа мала, так что для сортировки 1 Гб информации требуется лишь около 1 Кб стек. 29

Здесь перед нами встаёт вопрос практической оценки сложности алгоритма, которая теперь будет зависеть и от используемой вычислительной системы и от программных механизмов. Анализ трудоемкости рекурсивных реализаций алгоритмов, очевидно, связан как с количеством операций, выполняемых при одном вызове функции, так и с количеством таких вызовов. Графическое представление порождаемой данным алгоритмом цепочки рекурсивных вызовов называется деревом рекурсивных вызовов. Более детальное рассмотрение приводит к необходимости учета затрат как на организацию вызова функции и передачи параметров, так и на возврат вычисленных значений и передачу управления в точку вызова. 29

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

Рассмотрим пример для функции вычисления факториала: дерево рекурсии при вычислении 5! (рисунок 2) 29

30

рисунок 2 30

Дерево рекурсивных вызовов может иметь и более сложную структуру, если на каждом вызове порождается несколько обращений – фрагмент дерева рекурсий для чисел Фибоначчи представлен на рисунке 3: вычисление 5-ого числа Фибоначчи Fb(5). 30

30

рисунок 3 30

Упомянутый анализ практической сложности программ показывает, что часто асимптотически более сложные итеративные алгоритмы, на практике становятся более эффективными. Так, сравнивая скорость вычисления чисел Фибоначчи с помощью итеративной и рекурсивной функции можно заметить, что итеративная функция выполняется почти «мгновенно», не зависимо от значения . При использовании же рекурсивной функции уже при заметна задержка при вычислении, а при больших результат появляется весьма не скоро. Причина, как уже было сказано, кроется в том, что в теории не учтена зависимость времени работы программы от количества вызовов вложенных подпрограмм. Неэффективность рекурсии проявляется в том, что одни и те же вычисления производятся много раз. Особенно сильно это проявляется в методе, который был самым востребованным при построении теоретически быстрых рекурсивных алгоритмов, - методе бинарного разбиения на независимые подзадачи. Когда подзадачи независимы, это часто приводит к недопустимо большим затратам времени, так как одни и те же подзадачи начинают решаться по многу раз. 31

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

Технология, называемая восходящим динамическим программированием (bottom-up dynamic programming) основана на том, что значение рекурсивной функции можно определить, вычисляя все значения этой функции, начиная с наименьшего, используя на каждом шаге ранее вычисленные значения для подсчета текущего значения. Она применима к любому рекурсивному вычислению при условии, что мы можем позволить себе хранить все ранее вычисленные значения. Это в результате позволит уменьшить временную зависимость с экспоненциальной на линейную! 31

Нисходящее динамическое программирование (top-down dynamic programming) – еще более простая технология. Она позволяет выполнять рекурсивные функции при том же количестве итераций, что и восходящее динамическое программирование. Технология требует введения в рекурсивную программу неких средств, обеспечивающих сохранение каждого вычисленного значения и проверку сохраненных значений во избежание их повторного вычисления. 32

Таким образом, современные информационные технологии содержат достаточно средств, чтобы сделать теоретически эффективные рекурсивные алгоритмы, также эффективными и широко используемыми на практике. 32

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

Широкие возможности использования рекурсивных процедур даёт среда программирования Turbo Pascal 7.0. Механизм этого процесса реализован здесь согласно общим принципам – с помощью стека. 33

Пользователь может полностью контролировать преобразование данных в стеке, появление и завершение рекурсивных вызовов, для чего нажатием клавиш Ctrl+F3 открывается окно «Call Stack». В нём содержится вся информация о текущем состоянии стека. 33

Размер стека по умолчанию – 16 Кб, а максимальный размер – 64Кб. Если незавершенных рекурсивных вызовов слишком много (по ошибке в программе может возникнуть и бесконечной рекурсией), то система выдаст сообщение «Stack overflow» («Переполнение стека»). Это одна из самых распространённых ошибок при программировании рекурсивных алгоритмов. В первую очередь необходимо проверить рекурсию, используемую в программе, на наличие условия завершения (так называемой базовой задачи), чтобы убедиться в отсутствии бесконечной рекурсии. В других случаях есть смысл увеличить размер стека, используя меню «Options | Memory Sizes ”. 33

При необходимости можно манипулировать стеком с помощью директивы компилятора $M, содержащей три параметра. Размер стека определяется первым параметром директивы. Второй и третий ее параметры – нижняя и верхняя границы области динамически выделяемой памяти (кучи, heap). Однако нужно помнить, что эти установки будут действовать только для данной программы. 33

Сам рекурсивных вызов осуществляется по обычным синтаксическим правилам вызова подпрограмм. 33

Видим, что использование рекурсии стало простым и понятным. Это создаёт дополнительный стимул для активного её применения в практическом программировании. 33

Заключение. 34

По итогам разностороннего исследования рекурсивных алгоритмов можно сделать ряд важных и, надо сказать, приятных выводов. 34

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

Во-вторых, рекурсивные алгоритмы часто имеют более низкую асимптотическую сложность, чем эквивалентные им итерационные. То есть теоретически они быстрее. 34

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

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

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

1.Носов В.А. Основы теории алгоритмов и анализа их сложности. – М., 1992. 35

2.Федер Е. Фракталы. – М.: Мир, 1991. 35

3.Клейн М. Математика. Утрата неопределённости. – М.: Мир, 1987. 35

4.Фиошин М. -исчисление. – М., 1990. 35

5.Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. – М., 1983. 35

6.Емельченков Е.П., Емельченков В.Е. Вычислимость. Введение в теорию алгоритмов. – М., 2000. 35

7.Глухов М.М. Математическая логика. – М., 1982. 35

8.Мальцев А.И. Алгоритмы и рекурсивные функции. – М., 1965. 35

9.Трахтенброт Б.А. Сложность алгоритмов и вычислений: спецкурс для студентов НГУ. – Новосибирск, 1967. 35

10.Трахтенброт Б.А. Алгоритмы и вычислительные автоматы. – М., 1974. 35

11.Успенский В.А., Семёнов А.Л. Теория алгоритмов: основные открытия и приложения. – М., 1987. 35

12.Абрамов С.А. Математические построения и программирование. – М.: Наука, 1978. 35

13.Кнут Д. Искусство программирования для ЭВМ. 35

14.Шилдт Г. Работа с Турбо Паскалем. – М., 1990. 35