Литература Сущность рекурсии

Алгоритм 1: «Быстрая» сортировка (quicksort).
1. Выбирается опорный элемент (например, первый или случайный).
2. Реорганизуем массив так, чтобы сначала шли элементы меньшие опорного, потом равные ему, затем большие. Для этого достаточно помнить, сколько было найдено меньших (m₁) и больших (m₂), чем опорный и ставить очередной элемент на место с индексом m₁, а очередной больший на место с индексом n-1-m₂.
После выполнения такой операции опорный элемент и равные ему стоят на своем месте, их переставлять больше не придется. Между «меньшей» и «большей» часть массива перестановок также быть не может. То есть эти части можно сортировать независимо друг от друга.
3. Если «меньшая» или «большая» часть состоит из одного элемента, то она уже отсортирована и делать ничего не надо. Иначе сортируем эти части с помощью алгоритма быстрой сортировки (то есть, выполняем для нее шаги 1-3).
Как видите, быстрая сортировка состоит из выполнения шагов 1 и 2 и рекурсивного вызова алгоритма для получившихся частей массива.
Алгоритм 2: Сортировка слиянием (merge sort).

1. 
   Делим массив на две части примерно одинакового размера и, если получившаяся половина массива содержит больше одного элемента, то сортируем ее с помощью сортировки слиянием. Как видите, этот пункт содержит рекурсивное обращение ко всему алгоритму в целом.
   
2. 
   Соединяем две отсортированные половины так, чтобы получился один отсортированный массив. Для этого помещаем во вспомогательный массив элементы из первой половины, пока они не превосходят очередного элемента из второй половины. Затем начинаем помещать туда элементы второй половины, пока они не превосходят очередного элемента из первой половины. Затем снова берем элементы первой половины и т.д. Эта операция называется слиянием и требует столько шагов, сколько элементов в обоих соединяемых массивах.
   

Алгоритм 3: Сортировка деревом (tree sort).
Прежде чем переходить к объяснению сути алгоритма введем одно понятие. Двоичным деревом поиска называется бинарное дерево, в узлах которого располагаются числа таким образом, что в левом поддереве каждого узла находятся числа меньшие, чем в этом узле, а в правом поддереве больше или равные тому, что в этом узле. На рис. 10 показано два примера деревьев поиска, составленных из одних и тех же чисел.

Рис. 10. Двоичные деревья поиска, составленные из чисел 1, 3, 4, 6, 7, 8, 10, 13, 14.
Если для каждой вершины высота поддеревьев различается не более чем на единицу, то дерево называется сбалансированным. Сбалансированные деревья поиска также называются АВЛ-деревьями (по первым буквам фамилий изобретателей Г. М. Адельсона-Вельского и Е. М. Ландиса). Как видно на рис. 10а показано сбалансированное дерево, на рис. 10б несбалансированное.
Заметим, что расположение чисел по возрастанию получится, если обходить эти деревья в обратном прядке.
Сортировка деревом получится, если мы сначала последовательно будем добавлять числа из массива в двоичное дерево поиска, а затем обойдем его в обратном порядке.
Если дерево будет близко к сбалансированному, то сортировка потребует примерно n log₂ n операций. Если не повезет и дерево окажется максимально несбалансированным, то сортировка займет n² операций.
6.5. Произвольное количество вложенных циклов
Разместив рекурсивные вызовы внутри цикла, по сути, получим вложенные циклы, где уровень вложенности равен глубине рекурсии.
Для примера напишем процедуру, печатающую все возможные сочетания из k чисел от 1 до n ( ). Числа, входящие в каждое сочетание, будем печатать в порядке возрастания. Сочетания из двух чисел (k=2) печатаются так:

1 2 3

for i1 := 1 to n do for i2 := i1 + 1 to n do writeln(i1, ' ', i2);

Сочетания из трех чисел (k=3) так:

1 2 3 4

for i1 := 1 to n do for i2 := i1 + 1 to n do for i3 := i2 + 1 to n do writeln(i1, ' ', i2, ' ', i3);

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

procedure Combinations( n, k: integer; //Массив, в котором будем формировать сочетания var Indexes: array of integer; //Счетчик глубины рекурсии d: integer); var i, i_min: integer; s: string; begin if d < k then begin if d = 0 then i_min := 1 else i_min := Indexes[d-1] + 1; for i := i_min to n do begin Indexes[d] := i; Combinations(n, k, Indexes, d+1); end; end else begin for i := 0 to k-1 do write(Indexes[i], ' '); writeln; end; end;

6.6. Задачи на графах