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

Размещено на http://www.allbest.ru/

Министерство образования Оренбургской области

Государственное автономное профессиональное образовательное учреждение "Педагогический колледж" г. Бузулука

(ГАПОУ "Педколледж" г. Бузулука)

Реферат

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

Выполнил: студентка 1 курса

группы НК 11-20 специальность

44.02.03 Педагогика дополнительного образования

Колесник Ангелина Алексеевна

Проверил: преподаватель ОДБ.10

Алексеев В.С.

г. Бузулук, 2020

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

;

.

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

,

где , , .

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

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

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

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

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

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

Пусть . Тогда произведение матриц находится одним умножением.

Пусть и даны матрицы

, .

Положим

.

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

, , , , , , .

Тогда находим

, , , .

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

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

Пусть - число арифметических операций, используемых в алгоритме на матрицах размера . Тогда справедливы соотношения: и . Учитывая эти условия, докажем формулу . При и формула справедлива. Пусть для формула действительно следует из соотношений. Имеем при : т.е. наша формула справедлива и для . Утверждение доказано. Ясно, что выполняется . Значит, представленный алгоритм лучше по порядку исходного алгоритма (заметим, что ).

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

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

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

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

где , , , , - фиксированные константы. Тогда при , где , решением соотношения является выражение

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

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

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



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

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

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

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

(в алгоритме Штрассена , ). В. Пан использовал алгоритм с параметрами и и получил . В настоящее время известны и более лучшие алгоритмы. Усилиями ряда математиков (Пан, Виноград, Романи, Шейхаге, Штрассен, Копперсмит) экспонента сложности матричного умножения последовательно принимала значения: , , , , , . Основная проблема - нахождение доказательства равенства еще не решена

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

,

.

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

,

.

Здесь каждое и , являются -битовыми числами, . Рассмотрим многочлены

и образуем произведение

.

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

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

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

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

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

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

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

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

Стек - связная структура данных, построенная на принципе "первый пришёл - первый вышел" (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, в которую надлежит поместить значение этой функции (адрес значения).

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

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

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

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

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

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

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

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

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

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



рисунок 2

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

рисунок 3

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Размещено на Allbest.ru

...