Рекурсия
Понятие рекурсии
Рекурсивным называется объект, частично состоящий или определяемый с помощью самого себя. Факториал – это классический пример рекурсивного объекта. Факториал числа n – это произведение целых чисел от 1 до n. Обозначается факториал числа n так: n!. | Согласно определению: | n!Примеры программ. Поиск файлов.
В качестве примера использования рекурсии рассмотрим задачу поиска файлов. Пусть нужно получить список всех файлов, например, с расширением .bmp, которые находятся в указанном пользователем каталоге и во всех подкаталогах этого каталога.Кривая Гильберта
Следующая программа вычерчивает в диалоговом окне кривую Гильберта. На рис. 12.7 приведены кривые Гильберта первого, второго и третьего порядков. Если присмотреться, то видно, что кривая второго порядка получается путем соединения прямыми линиями четырех кривых первого порядка.Поиск пути
Механизм рекурсии весьма эффективен при программировании задач поиска. В качестве еще одного примера рассмотрим задачу поиска пути между двумя городами. Если несколько городов соединены дорогами, то очевидно, что попасть из одного города в другой можно различными маршрутами.Поиск кратчайшего пути
Обычно задача поиска пути на графе формулируется следующим образом: найти наилучший маршрут. Под наилучшим маршрутом, как правило, понимают кратчайший. Найти кратчайший маршрут можно выбором из всех найденных. Однако совсем не обязательно искать все маршруты.