else if ( number == 0 )
return 1;
for ( ; number > 0; number-- )
product *= number;
return product;
}
94
Фрагмент программы 4.1b.
Конечно, вопрос о том, какая реализация конкретной функции более понятна,
довольно спорный. Обычно в итерационную функцию приходится включать больше
локальных переменных, например, в первом примере был добавлен массив
"chars[MAX_ARRAY_LENGTH]", а во втором примере –целочисленная переменная
"product". Другими словами, в итеративных функциях память тратится на локальные
переменные, а рекурсивных функциях –на организацию вызовов.
6. Рекурсия в структурах данных
На практике рекурсия чаще встречается в структурных типах данных, а не в
функциях. Рекурсивная структура данных уже использовалась в предыдущей лекции
для определения узла связного списка. В структуре "узел" хранится указатель струк-
туру такого же типа:
struct node
{
char word[MAX_WORD_LENGTH];
node *ptr_to_next_node;
};
В последующих лекциях будут более подробно рассматриваться другие приме-
ры рекурсивных структур данных и особенности их описания на Си++.
7. Рекурсивная реализация алгоритма быстрой сортировки
В завершающей части этой лекции кратко рассмотрим известный пример ре-
курсивного алгоритма –алгоритм быстрой сортировки QuickSort. Этот рекурсивно
определенный алгоритм предназначен для упорядочения значений, хранящихся в
массиве, по возрастанию или по убыванию.
Предположим, что 11 элементов массива имеют следующие значения (рис. 6).
Рис. 6.. Начальное состояние массива.
Идея алгоритма основана на рекурсивном выполнении разбиения массива на
две части и переупорядочении элементов в этих частях. Разбиение выполняется путем
выбора некоторого элемента, который будем называть граничным. После разбиения
две части массива обрабатываются так, чтобы в одной части располагались значения,
меньшие или равные граничному элементу, а в другой части –только большие или
равные.
Например, если выбрать в качестве граничного элемента значение 8, то после
переупорядочения массив окажется в состоянии, показанном на рис. 7. Затем тот же
самый процесс независимо выполняется для левой и правой частей массива.
Рис. 7.. Массив после разделения на две части и переупорядочения элементов в них.
Процесс разбиения и переупорядочения частей массива можно реализовать ре-
курсивно. Индекс граничного элемента вычисляется как индекс среднего элемента:
95
(first + last)/2
где "first" и "last" являются индексами первого и последнего элементов обрабаты-
ваемой части массива.
Далее подробно рассматривается процедура переупорядочения элементов мас-
сива.
Индексы "left_arrow" и "right_arrow" определим как индексы крайних элемен-
тов обрабатываемой части массива (которая подвергается разбиению, см. рис. 8).
Рис. 8.. Значения индексов "left_arrow" и "right_arrow" перед нача-
лом процедуры переупорядочения.
В процессе переупорядочения индексы "left_arrow" и "right_arrow" смещают-
ся в направлении граничного элемента. Так, "right_arrow" перемещается влево, пока
значение элемента не окажется меньше или равно граничному значению (рис. 9).
Рис. 9.. Обнаружение левого и правого элементов для обмена.
Аналогично, "left_arrow" смещается вправо, пока не встретится элемент,
больший или равный граничному. В нашем примере этот элемент расположен в нача-
ле массива (рис. 9). Теперь значения двух найденных элементов массива меняются
местами (рис. 10).
Рис. 10.. Состояние массива после обмена двух элементов.
После обмена двух элементов "right_arrow" продолжает смещаться влево.
Смещение прекращается, когда находится очередной элемент, меньший или равный
граничному (рис. 11).
Рис. 11.. Справа обнаружен элемент для обмена.
Индекс "left_arrow" смещается вправо, пока не встретится элемент, требую-
щий перестановки (рис. 12).
Рис. 12.. Слева обнаружен элемент для обмена.
Значения найденных элементов меняются местами (рис. 13).
96
Рис. 13.. Состояние массива после обмена второй пары элементов.
Переупорядочение частей массива прекращается после выполнения условия
"left_arrow > right_arrow". В состоянии на рис. 13 это условия ложно, поэтому
"right_arrow" продолжает смещаться влево, пока не окажется в положении, показан-
ном на рис. 14.
Рис. 14.. Справа обнаружен элемент для обмена.
Перемещение "left_arrow" приведет к состоянию, показанному на рис. 15. По-
скольку при перемещении вправо надо найти элемент, больший или равный "pivot",
то "left_arrow" прекращает перемещение после достижения граничного элемента.
Рис. 15.. Левый элемент для обмена совпадает с граничным.
Теперь выполняется обмен, включающий граничный элемент (такой обмен до-
пустим), и массив переходит в состояние, показанное на рис. 16.
Рис. 16.. Состояние массива после обмена третьей пары элементов.
После обмена элементов "right_arrow" перемещается влево, а "left_arrow" –
вправо (рис. 17).
Рис. 17.. Переупорядочение прекращается после прохождения индексами се-
редины массива.
В состоянии, показанном на рис. 17, становится истинным условие завершения
процедуры переупорядочения "left_arrow > right_arrow". Поэтому первую процеду-
ру разбиения и переупорядочения массива можно считать выполненной.
Ниже приведена функция на Си++, в которой рекурсивно реализован алгоритм
сортировки QuickSort:
void quick_sort( int list[], int left, int right )
{
int pivot, left_arrow, right_arrow;
97
left_arrow = left;
right_arrow = right;
pivot = list[(left + right)/2];
do {
while ( list[right_arrow] > pivot )
right_arrow--;
while ( list[left_arrow] < pivot )
left_arrow++;
if ( left_arrow <= right_arrow )
{
swap( list[left_arrow], list[right_arrow] );
left_arrow++;
right_arrow--;
}
} while ( right_arrow >= left_arrow );
if ( left < right_arrow )
quick_sort( list, left, right_arrow );
if ( left_arrow < right )
quick_sort( list, left_arrow, right );
}
Программа 7.1.
8. Сводка результатов
На Си++ можно писать рекурсивные функции. В лекции кратко описан порядок
выполнения рекурсивных функций и назначение стека. Для любой рекурсивной
функции можно разработать итерационный аналог. В лекции указаны преимущества
и недостатки рекурсивной реализации. В качестве примера приведен известный алго-
ритм быстрой сортировки QuickSort и его рекурсивная реализация на Си++.
9. Упражнения
Упражнение 1
Последовательность чисел Фибоначчи может быть определена следующим образом:
•a(1) = 1
•a(2) = 1
•для всех n>2 a(n) = a(n-1) + a(n-2)
Это определение позволяет сгенерировать такую последовательность:
1, 1, 2, 3, 5, 8, 13, 21, ...
Напишите на Си++ функцию "fibonacci(...)", которая вычисляет числа Фи-
боначчи по их порядковому номеру, например, fibonacci(7)==13.
Упражнение 2
Для выполнения этого упражнения используйте программу 5.1 из 7-й лекции.
а) Напишите две рекурсивных функции "print_list_forwards(...)" и
"print_list_backwards(...)", которые должны печатать на экране содержимое
связного списка, рассмотренного в 7-й лекции, соответственного _______в прямом и
98
обратном порядке. (Функция "print_list_forwards(...)" должна вести себя
точно так же, как и функция "print_list(...)" из 7-й лекции). Измените про-
грамму 5.1 из 7-й лекции так, чтобы проверить свои функции. Ваша программа
должна выдавать на экран следующие сообщения:
Введите первое слово (или '.' для завершения списка): это
Введите следующее слово (или '.' для завершения списка): короткое
Введите следующее слово (или '.' для завершения списка): тестовое