2015-10-22
691
Рекурсивные структуры являются другим видом повторяющихся структур. Цикл означает повторное выполнение набора команд, при этом весь набор команд полностью выполняется, а затем повторяется. Рекурсия же предполагает повторное выполнение набора команд как подзадачу самой себя. В качестве примера можно привести обработку входящих телефонных звонков, когда незаконченный телефонный разговор откладывается и обрабатывается другой входящий звонок. В результате принимаются два звонка. Однако они обрабатываются не один за другим, как в цикле, а один обрабатывается в другом.
Для того чтобы познакомиться с рекурсией, рассмотрим алгоритм двоичного поиска (binary search), в котором в процессе поиска применяется метод разбиения.
Поиск и сортировка
Алгоритмы последовательного и двоичного поиска — это только два алгоритма из множества существующих алгоритмов для осуществления процесса поиска. Точно так же, сортировка методом вставок представляет собой только один из многих алгоритмов сортировки. Другими классическими алгоритмами являются сортировка слиянием (глава 11), сортировка методом отбора (упражнение 5 раздела 4.4), сортировка методом «пузырька» (упражнение 6 раздела 4.4), быстрая сортировка (алгоритм применяет к процессу сортировки методом разбиения) и пирамидальная сортировка (алгоритм использует сложную технику нахождения записей, которые следует переместить в начало списка).
