Примеры рекурсивной обработки массива

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

Таким образом, любая задача по обработке массива может быть решена с помощью рекурсии. Мы возьмем в качестве примера ту же самую задачу сортировки массива, которая рассматривалась выше для итерационного метода. Попутно окажется, что нам потребуется написать нахождение максимума, что также можно сделать рекурсивно5. Следовательно, в итоге у нас будет сразу два примера рекурсивных алгоритмов.

Рассмотрим возможную реализацию программы.

PROGRAM sort_rekurs(INPUT, OUTPUT);

CONST n = 10;

m: ARRAY [1..n] OF INTEGER =

(10,9,8,7,6,5,4,3,2,1);

FUNCTION ind_max(k: INTEGER): INTEGER;

VAR w: INTEGER;

BEGIN IF k > 1 THEN BEGIN w:= ind_max(k - 1);

IF m[k] < m[w] THEN ind_max:= w

ELSE ind_max:= k

END

ELSE ind_max:= 1

END;

PROCEDURE sort2(p: INTEGER);

VAR im,c: INTEGER;

BEGIN im:= ind_max(p);

c:= m[im]; m[im]:= m[p]; m[p]:= c;

FOR c:= 1 TO n DO WRITE(m[c],' '); WRITELN;

IF p > 2 THEN sort2(p - 1)

END;

BEGIN sort2(n)

END.

Описание начнем с рассмотрения рекурсивной функции ind_max для нахождения индекса максимального элемента. Ее рекурсивная логика может быть сформулирована следующим образом. Решение задачи для массива из n элементов весьма трудоемко, поэтому его постепенно сводим к более простому: для n – 1, n – 2
и т.д. элементов (см. вызов ind_max(k-1), который и является рекурсивным вызовом функцией самой себя). Так поступаем до тех пор, пока ответ не станет тривиальным: в массиве из одного элемента индекс максимума равен индексу этого единственного элемента (в нашем случае 1). Далее производится “обратный ход” — зная текущее значение ind_max, соответствующее ему значение максимума сравниваем с текущим элементом массива, после чего индекс наибольшего из сравниваемых элементов запоминаем. Таким образом, отрабатывается последовательная цепочка рекурсивных вызовов и без всякого цикла организуется полный перебор всех элементов массива.

Примечание. Понимание механизма вызова процедур6 делает возможность реализации их “самовызова” абсолютно очевидной; даже просто зная о факте разрешения вызова из одной процедуры другой, можно предсказать существование рекурсивности. Главная же проблема рекурсии заключается в том, чтобы организованный рассматриваемым способом процесс каким-то образом завершался.

Теперь, рассматривая функцию ind_max как единое целое и не обращая внимания на ее внутреннюю логику, обсудим второй рекурсивный алгоритм — сортировку массива, описанную в рекурсивной процедуре sort2. Ее логика работы такова. В массиве размерности n находится максимальный элемент, и он меняется местами с последним. В результате самый последний элемент массива займет свое окончательное место и останется рассортировать массив уже меньшего размера, т.е. n – 1. Аналогичным образом задача последовательно решается для все меньшего и меньшего массива, пока не останется массив из одного элемента, в котором, естественно, сортировка уже не требуется: условие p > 2 предотвращает вызов sort2(1) и процесс рекурсии благополучно завершается.

Примечание. Имеющийся в sort2 цикл вывода массива на экран играет вспомогательную роль. Читатели при желании могут без труда самостоятельно оформить его в виде рекурсивной процедуры (печатаем первый элемент, а затем вызываем процедуру вывода оставшегося массива!), реализовав тем самым чисто рекурсивную программу без единого цикла.

Основная программа состоит из единственной строки sort2(n), которая запускает процесс сортировки, начиная с полного массива.

Примечание для учителей. Вполне возможно, что приведенное решение задачи для некоторых школ покажется слишком сложным. В этом случае вполне можно ограничиться рекурсивным решением ее части — нахождением положения максимума в массиве. Вообще сам факт наличия вопроса о рекурсии7 в тексте официальных “министерских” билетов для выпускных экзаменов в пору, когда слово “программирование” для многих методистов стало едва ли не ругательным, весьма наглядно демонстрирует тот идейный разброд, который внесла в содержание курса информатики энергичная борьба за наполнение школьного курса прикладными офисными технологиями!

Все обсуждавшиеся выше примеры рассматривали одномерные массивы данных. Они являются наиболее простыми и, кроме того, естественным образом согласуются с принципами организации памяти компьютера: согласно классическим идеям фоннеймановской архитектуры, память — это линейный массив пронумерованных ячеек. Следовательно, остается лишь получить формулу пересчета значений индексов в адреса ОЗУ и с элементами такого массива можно легко работать.

В математике, физике и некоторых других науках тем не менее широко используются и многомерные массивы. Поэтому такие структуры не могли не появиться в языках программирования. Фактически есть два способа определения многомерных массивов: непосредственный и создание сложной структуры. Мы ограничимся обсуждением двумерных массивов; обобщение для большей размерности делается аналогично. На языке Паскаль, например, эти два способа описания массивов выглядят так:

m1: ARRAY [1..3, 1..5] OF REAL;

m2: ARRAY [1..3] OF ARRAY [1..5] OF REAL;

Примечание. Обращение к элементам массивов m1 и m2 отличаются: они записываются как m1[i,j] и m2[i][j] соответственно.

В некоторых простых языках программирования типа Basic используется только традиционная математическая (“матричная”) форма представления массивов, а в языках с более развитыми средствами создания данных, в частности Паскале, допустимы обе формы.

Подчеркнем, что если в языке программирования для индексов допустимы не только целочисленные типы (в Паскале в том числе), то индексы многомерных массивов не обязательно имеют одинаковый тип: например, один индекс может быть целочисленным, а другой являться символом.

С математической точки зрения для увеличения размерности массива достаточно формально приписать еще один индекс. Однако для реализации такой структуры в памяти компьютера потребуется как-то приспособить многомерную структуру данных к хранению в одномерной памяти. “За исключением языка Fortran, все языки хранят двумерные массивы как последовательности строк… Такое размещение вполне естественно, поскольку сохраняет идентичность двумерного массива и массива массивов”. [4] Приведенный рисунок поясняет идею формирования двумерного массива данных в “линейном” ОЗУ компьютера.

Учитывая, что все элементы массива однородны (имеют один и тот же тип и, следовательно, занимают одинаковое место в памяти), получить формулу пересчета индексов в требуемый адрес ОЗУ является несложной задачей. И хотя школьных знаний для этого вполне достаточно, мы не будем сейчас этим заниматься. Заметим лишь, что в 32-разрядных процессорах Intel специально предусмотрены аппаратные методы адресации, в которые заложены такие формулы для данных стандартной длины (1, 2, 4 и даже 8 байт), что существенно облегчает для программиста (или для компилятора) доступ к элементам массивов. Заинтересовавшиеся читатели могут познакомиться с формулами для масштабированной базово-индексной адресации (одномерные массивы) и для аналогичного метода со смещением (двумерные), например, по книге [5].

Литература

1. Примеры задач к билетам. Информатика, 2006, № 6, с. 3–16.

2. Примеры задач к билетам. Информатика и образование, 2006, № 3, с. 24–30.

3. Фридланд А.Я. Информатика и компьютерные технологии: Основные термины: Толковый словарь / А.Я. Фридланд, Л.С. Ханамирова, И.А. Фридланд. М.: ООО “Издательство Астрель”: ООО “Издательство АСТ”, 2003, 272 с.

4. Бен-Ари М. Языки программирования. Практический сравнительный анализ. М.: Мир, 2000, 366 с.

5. Гук М. Процессоры Intel: от 8086 до Pentium II. СПб.: Питер, 1997, 224 с.

Дата добавления: 2015-04-23