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

2. Умножение матриц. Даны две квадратные матрицы порядка с элементами из некоторого кольца и требуется найти их произведение. Стандартный алгоритм требует умножений и сложений элементов К. На первый взгляд, кажется, что невозможно сколько-нибудь существенно уменьшить данное число операций, Однако, В. Штрассеном [13] был предложен следующий алгоритм.

Пусть . Тогда произведение матриц находится одним умножением.

Пусть и даны матрицы , . Положим . Тогда матрица может быть вычислена так. Пусть , , , , , , . Тогда находим , , , .

Заметим, в данном алгоритме использовано 7 умножений и 18 сложений и не использована коммутативность умножения.

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

Пусть - число арифметических операций, используемых в алгоритме на матрицах размера . Тогда справедливы соотношения: и . Учитывая эти условия, докажем формулу . При и формула справедлива. Пусть для формула действительно следует из соотношений. Имеем при : т.е. наша формула справедлива и для . Утверждение доказано. Ясно, что выполняется . Значит, представленный алгоритм лучше по порядку исходного алгоритма (заметим, что ).

Рассмотрим теперь в общем виде вопрос о сложности алгоритмов, использующих рекурсию. Из приведенных выше примеров, ясно, что сложность рекурсивных алгоритмов выражается рекуррентными соотношениями. Если в рекурсивном алгоритме используется одна процедура, то значение сложности для задачи размера определяется значениями для аргументов , где . Однако возникающие при этом рекуррентные соотношения решаются в конечном виде в очень редких случаях. При равномерном разбиении задача размера разбивается на подзадач размера , где - некоторая фиксированная константа в рекурсивном алгоритме, при этом функция сложности определяется рекуррентным соотношением вида:

где - константа, , - неотрицательные, целочисленные, монотонные функции, характеризующие сложность получения решения исходной задачи размера из решений подзадач размера . Ясно, что данное соотношение определяет однозначно функцию только при значениях аргументов вида , где . Для практических приложений представляет интерес выделение случаев, когда решение ограничено сверху полиномом от .

Легко доказывается, что если функция удовлетворяет условию: существует , такое, что справедливо соотношение для всех натуральных , то не мажорируется сверху никаким полиномом от [14]. Таким образом, в дальнейшем ограничимся случаем , , где , , - фиксированные целые числа.

Теперь можно доказать, что справедливо следующее утверждение [15]. Пусть дано рекуррентное соотношение

где , , , , - фиксированные константы. Тогда при , где , решением соотношения является выражение

Далее вытекает следствие [16], что в предположениях предыдущего утверждения справедливы соотношения

В некоторых случаях рекурсию для задачи размера удаётся организовать только путем аддитивного уменьшения исходного размера задачи на некоторую константу . Сложность такого типа рекурсивных алгоритмов определяется рекуррентным соотношением вида

где , , , , - фиксированные константы. Например, такая ситуация возникает при решении графических задач. Для такого соотношения при , где , справедлива оценка [17]

В некоторых случаях для организации рекурсии используется «квадратичное» разбиение, при котором исходная задача размера разбивается на подзадач размера . Для сложности рекурсивного алгоритма возникает следующее рекуррентное уравнение

где , , - фиксированные константы. Оно определяет однозначно функцию при  таким выражением [18]

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

Для задачи умножения матриц использование базового алгоритма умножения -матриц с умножениями для построения рекурсивного алгоритма, сводящего умножение -матриц к умножению -матриц приводит к оценкам для сложности :

(в алгоритме Штрассена , ). В. Пан использовал алгоритм с параметрами и и получил . В настоящее время известны и более лучшие алгоритмы. Усилиями ряда математиков (Пан, Виноград, Романи, Шейхаге, Штрассен, Копперсмит) экспонента сложности матричного умножения последовательно принимала значения: , , , , , . Основная проблема - нахождение доказательства равенства еще не решена [19].

Рассмотрим еще один пример применения полученных результатов. Вернемся к задаче умножения чисел в двоичной записи. Зафиксируем натуральное число и рассмотрим два -битовых числа и , где

,

.

Разобьем эти числа на частей

,

.

Здесь каждое и , являются -битовыми числами, . Рассмотрим многочлены

и образуем произведение . Ясно, что выполнено , , . Поэтому, знание многочлена позволяет вычислить произведение за число действий пропорциональное . Чтобы найти коэффициенты многочлена находим значение в точках , то есть . Разрядность чисел (соответственно ) не превышает , где - некоторая константа, зависящая oт . Ясно, что если - сложность умножения -битовых чисел, то сложность умножения -битовых чисел есть для некоторой константы .

Если - сложность умножения -битовых чисел, то справедливо соотношение ( - константа). Отсюда и согласно изложенным ранее результатам, получаем . Поскольку имеем и, обозначая можно записать . Таким образом, доказано, для любого существует алгоритм умножения -битовых чисел, для которого сложность удовлетворяет соотношению .

Имеются и более эффективные алгоритмы умножения чисел, но они используют уже не цифровые операции [20].

Обобщая полученные результаты, нужно отметить, что многие распространённые и важные алгоритмические задачи допускают рекурсивные решения. Несмотря на кажущуюся громоздкость (ведь на каждом шаге количество подалгоритмов меньшей размерности увеличивается в несколько раз) анализ с использованием аппарата теории сложности показывает, что они зачастую менее трудоёмки, чем обычные итерационные. Однако само получение сложностных оценок не так просто. В большинстве случаев функция сложности определяется с помощью рекуррентных соотношений, нахождение явного её вида представляет некоторые трудности. Справиться с этой проблемой удаётся при специально подобранных значениях размерности исходной задачи. Другие значения требуют отдельного исследования и обычно позволяют получить только грубые оценки.

Программная реализация рекурсии.

Общие принципы реализации.

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

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

Стек – связная структура данных, построенная на принципе «первый пришёл – первый вышел» (First In – First Out, FIFO). То есть вновь добавляемые объекты помещаются в начало, вершину стека, и выбираются они также только из вершины.

Стек является чрезвычайно удобной структурой данных для многих задач вычислительной техники. Наиболее типичной из таких задач является обеспечение вложенных вызовов процедур. Предположим, имеется процедура A, которая вызывает процедуру B, а та в свою очередь - процедуру C. Когда выполнение процедуры A дойдет до вызова B, процедура A приостанавливается и управление передается на входную точку процедуры B. Когда B доходит до вызова C, приостанавливается B и управление передается на процедуру C. Когда заканчивается выполнение процедуры C, управление должно быть возвращено в B, причем в точку, следующую за вызовом C. При завершении B управление должно возвращаться в A, в точку, следующую за вызовом B. Правильную последовательность возвратов легко обеспечить, если при каждом вызове процедуры записывать адрес возврата в стек. Так, когда процедура A вызывает процедуру B, в стек заносится адрес возврата в A; когда B вызывает C, в стек заносится адрес возврата в B. Когда C заканчивается, адрес возврата выбирается из вершины стека - а это адрес возврата в B. Когда заканчивается B, в вершине стека находится адрес возврата в A, и возврат из B произойдет в A.

Механизм вызова функции или процедуры в языке высокого уровня существенно зависит от архитектуры компьютера и операционной системы. В рамках IBM PC совместимых компьютеров, в микропроцессорах семейства Intel, как и в большинстве современных процессорных архитектур, поддерживается аппаратный стек. Аппаратный стек расположен в ОЗУ, указатель стека содержится в паре специальных регистров SS:SP доступных для программиста. Аппаратный стек расширяется в сторону уменьшения адресов, указатель его адресует первый свободный элемент. Выполнение команд CALL и INT, а также аппаратных прерываний включает в себя запись в аппаратный стек адреса возврата. Как передаваемые в процедуру или функцию фактические параметры, так и возвращаемые из них значения помещаются в аппаратный стек специальными командами процессора. Дополнительно сохраняются значения необходимых регистров. Схематично этот механизм иллюстрирован на рисунке 1.

Выполнение команд RET и IRET включает в себя выборку из аппаратного стека адреса возврата и передачу управления по этому адресу. Пара команд - PUSH и POP - обеспечивает использование аппаратного стека для программного решения других задач.

Системы программирования для блочно-ориентированных языков (PASCAL, C, C++ и др.) используют стек для размещения в нем локальных переменных процедур и иных программных блоков. Стек разбит на фрагменты, представляющие собой блоки последовательных ячеек. Каждый вызов подпрограммы использует фрагмент стека, длина которого зависит от вызывающей подпрограммы. При каждой активизации процедуры память для ее локальных переменных выделяется в стеке; при завершении процедуры эта память освобождается. Поскольку при вызовах процедур всегда строго

рисунок 1

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

Таким образом, в общем случае при вызове процедурой A процедуры B происходит следующее:

1. В вершину стека помещается фрагмент нужного размера. В него входят следующие‚ данные:  (а) указатели фактических параметров вызова процедуры В; (б) пустые ячейки для локальных переменных, определенных в процедуре В; (в) адрес возврата, т.е. адрес команды в процедуре A, которую следует выполнить после того, как процедура B закончит свою работу.
Если B - функция, то во фрагмент стека для B помещается указатель ячейки во фрагменте стека для A, в которую надлежит поместить значение этой функции (адрес значения).

2. Управление передается первому оператору процедуры B.

3. При завершении работы процедуры B управление передается процедуре A с помощью следующей последовательности шагов: (а) адрес возврата извлекается из вершины стека; (б) если B - функция, то ее значение запоминается в ячейке, предписанной указателем на адрес значения; (в) фрагмент стека процедуры B извлекается из стека, в вершину ставится фрагмент процедуры A; (г) выполнение процедуры A возобновляется с команды, указанной в адресе возврата.

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

Этот прием делает возможной легкую реализацию рекурсивных процедур. Когда процедура вызывает сама себя, то для всех ее локальных переменных выделяется новая память в стеке, и вложенный вызов работает с собственным представлением локальных переменных. Когда вложенный вызов завершается, занимаемая его переменными область памяти в стеке освобождается и актуальным становится представление локальных переменных предыдущего уровня. За счет этого в языках PASCAL и C любые процедуры и функции могут вызывать сами себя. В языке PL/1, где по умолчанию приняты другие способы размещения локальных переменных, рекурсивная процедура должна быть определена с описателем RECURSIVE - только тогда ее локальные переменные будут размещаться в стеке.

Рекурсия использует стек в скрытом от программиста виде, но все рекурсивные процедуры могут быть реализованы и без рекурсии, но с явным использованием стека. Пример подобной «развертки» рекурсии можно увидеть в реализации быстрой сортировки Хоара через стек [21].

Один проход сортировки Хоара разбивает исходное множество на два множества. Границы полученных множеств запоминаются в стеке. Затем из стека выбираются границы, находящиеся в вершине, и обрабатывается множество, определяемое этими границами. В процессе его обработки в стек может быть записана новая пара границ и т.д. При начальных установках в стек заносятся границы исходного множества. Сортировка заканчивается с опустошением стека.