Применение рекурсии

Теперь, имея некоторое представление о рекурсии, надо попытаться понять, что с ней можно делать, кроме закрашивания изображений. Одним из наиболее распространенных рекурсивных алгоритмов будет так называемый двоичный поиск. Это можно представить себе как игру на больше-меньше. Если кто-то предлагает угадать число от 1 до 100, то, скорее всего, начать лучше с 50. Если партнер скажет, что больше, то можно предположить 75 и т.д. Это можно продолжать, пока число не будет найдено.

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

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

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

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

on_load_lecture()

Перейти к вопросам »

Если Вы заметили ошибку - сообщите нам.

Страницы:

« |

вопросы | »

учебники

для печати и PDA

Телефон: +7 (495) 253-9312, 253-9313, факс: +7 (495) 253-9310, email: info@intuit.ru

Содержание раздела