Рекурсивные определения и алгоритмы

Сортировка файлов. Рекурсия

Сортировка массивов

Сортировка данных

Как отмечалось выше, сортировка данных – фундаментальная программистская задача. Существуют два вида сортировки, принципиально отличающиеся друг от друга: сортировка массивов и сортировка файлов (Рис. 11.4).

Рис. 15.4. Виды сортировки.

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

Условимся, что сортировка должна выполняться "на том же месте", т.е. без заведения второго массива такого же размера.

Сортировка методом прямого включениясостоит в том, что каждый элемент массива вставляется на свое место, при этом все прочие элементы сдвигаются, освобождая место для вставляемого элемента:

FOR I:=2 TO n DO
BEGIN
x := a[I];
включение х на свое место среди a[1]…a[n]
END;

Такой алгоритм легко реализовать:

FOR i := 2 TO n DO
BEGIN
x := a[i]; a[0] := x; j := i;
WHILE (x<a[j-1]) DO
BEGIN
a[j] := a[j-1];
DEC(j)
END;
a[j] : = x
END;

Увы, этот алгоритм весьма неэффективен – приходится "двигать" большие объемы данных.

Метод прямого перебора (его чаще всего самостоятельно изобретают начинающие программисты) работает лучше: в нем меняются местами пары элементов массива и общее число "передвижек" оказывается значительно меньшим:

FOR i := 1 TO n-1 DO
BEGIN
k := минимальный элемент среди a[i] … a[n];
поменять местами a[i] и a[k]
END;

Программируется метод прямого перебора с помощью двух вложенных циклов:

FOR I := 1 TO n-1 DO
BEGIN
k := I; x : = a[I];
FOR j := I+1 TO n DO
IF a[j]<x THEN
BEGIN
k := j;
x := a[k]
END;
a[k] := a [I];
a[I] := x
END;

Сортировка файлов, требующая рекурсии, будет рассмотрена на следующей лекции.

Из математики известно, что рекурсивный объект– объект, частично состоящий или определяемый с помощью самого себя. Данное определение достаточно невразумительно и скорее заставляет представить что-то вроде змеи, кусающей свой собственный хвост. Попробуем разобраться с рекурсивными объектами на примерах.

Пример 1: Натуральные числа.
а) 0 есть натуральное число;
б) число, следующее за натуральным, есть натуральное число.

Пример 2: Факториал n!=1×2×3… n.
а) 0! = 1
б) при n>0 n! = n× (n-1)!

Очень важно то, что рекурсивное определение конечным высказыванием задает бесконечное множество объектов (скажем, бесконечное множество натуральных чисел).

В программировании рекурсивная процедура или функция вызывает САМУ СЕБЯ. В Паскале это разрешено:

FUNCTION fact(n:WORD):LONGINT;
BEGIN
IF n=0 THEN
fact := 1
ELSE
fact := n*fact(n-1)
END;

Как такое может быть? Как же реализованы вызовы процедурой самой себя? Дело в том, что при каждом рекурсивном вызове в памяти создается новый набор локальных переменных рекурсивной процедуры/функции (Рис. 16.1).

Рис. 16.1. Рекурсивные вызовы.

Если при каждом вызове в памяти образуется новый набор локальных переменных, а в цикле таких вызовов можно организовать тысячи, то, очевидно, что рекурсивные алгоритмы очень активно потребляют память. Если локальные переменные занимают хотя бы 100 байт, то уже на 656 итерации рекурсивного цикла их суммарный объем превысит 64Кб – максимальный размер сегмента памяти - и возникнет ошибка. Особенно опасно зацикливание рекурсии.