|
Читайте также: |
Как говорилось выше, рекурсивные вызовы образуют дерево, где каждый узел соответствует вызову одной процедуры. Последовательность выполнения этих процедур соответствует тому или иному алгоритму обхода узлов. Если требуется много раз обойти узлы одного и того же дерева, то можно один раз обойти их рекурсивно, запомнить количество и последовательность узлов, а затем, пользуясь этой информацией, обходить узлы уже нерекурсивно.
Например, в разделе 6.3 обсуждалась задача вычисления арифметических выражений, заданных строкой. Может возникнуть ситуация, когда одно и то же выражение потребуется вычислить много раз при различных значениях переменной x. Синтаксическое дерево, которое требуется обходить при таких вычислениях, не зависит от x. Можно обойти его один раз, построив при этом массив, где каждый элемент будет соответствовать узлу дерева, а их последовательность – порядку обхода. Повторные вычисления при новом x потребуют только нерекурсивного перебора элементов массива.
Заключение
По итогам разностороннего исследования рекурсивных алгоритмов можно сделать ряд важных и, надо сказать, приятных выводов.
Во-первых, рекурсивные алгоритмы есть универсальное средство решения разнообразных алгоритмических проблем. Показано, что любая разрешимая задача такого рода имеет рекурсивное решение, которое при этом отличается изяществом и простотой для восприятия человеком.
Во-вторых, рекурсивные алгоритмы часто имеют более низкую асимптотическую сложность, чем эквивалентные им итерационные. То есть теоретически они быстрее.
В-третьих, развитие современных программных средств сделало практическое использование рекурсии достаточно несложным делом, а новые концепции и технологии программирования преодолели проблему низкой эффективности рекурсивных программ, созданную необходимостью вызова большого количества подпроцедур.
Конечно, после всего вышесказанного не стоит считать рекурсивные алгоритмы панацеей от всех профессиональных болезней программиста. Но в то же время не стоит умалять их значения. Основное – это быстро и качественно найти решение стоящей задачи, и тут следует принимать во внимание и возможность применения рекурсивных алгоритмов.
Список использованных источников:
[1] Кнут Д. Искусство программирования для ЭВМ, т.4.
[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.
Список использованной литературы:
1. Носов В.А. Основы теории алгоритмов и анализа их сложности. – М., 1992.
2. Федер Е. Фракталы. – М.: Мир, 1991.
3. Клейн М. Математика. Утрата неопределённости. – М.: Мир, 1987.
4. Фиошин М. -исчисление. – М., 1990.
5. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. – М., 1983.
6. Емельченков Е.П., Емельченков В.Е. Вычислимость. Введение в теорию алгоритмов. – М., 2000.
7. Глухов М.М. Математическая логика. – М.
8. Мальцев А.И. Алгоритмы и рекурсивные функции. – М.
9. Трахтенброт Б.А. Сложность алгоритмов и вычислений: спецкурс для студентов НГУ. – Новосибирск.
10. Трахтенброт Б.А. Алгоритмы и вычислительные автоматы. – М., 1974.
11. Успенский В.А., Семёнов А.Л. Теория алгоритмов: основные открытия и приложения. – М.
12. Абрамов С.А. Математические построения и программирование. – М.: Наука,.
13. Кнут Д. Искусство программирования для ЭВМ.
14. Шилдт Г. Работа с Турбо Паскалем. – М., 1990.
15. Н. Вирт. Алгоритмы и структуры данных.
Дата добавления: 2015-08-09; просмотров: 135 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Явное использование стека | | | Строение сосудов. |