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

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

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

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

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

рисунок 2

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

рисунок 3

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

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

Технология, называемая восходящим динамическим программированием (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.

28

[1] Федер Е. Фракталы. – М.: Мир, 1991.

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

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

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

[5] Фиошин М. -исчисление. – М., 1990.

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

[7] Там же.

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

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

[10] Там же.

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

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

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

[14] Там же.

[15] Там же.

[16] Там же.

[17] Там же.

[18] Там же.

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

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

[21] Кнут Д. Искусство программирования для ЭВМ, т.3. – М.: Мир, 1994.

[22] Кнут Д. Искусство программирования для ЭВМ, т.4.