Главная Промышленная автоматика.

ВЕРШИНА-

фрагмент стека для основной программы

фрагмент стека для процедуры, вызвавшей А

фрагмент стека для этого вызова процедуры А

Рис. 2.11. Стек для вызовов рекурсивной процедуры.

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

3. Когда процедура В кончает работу, управление передается процедуре А с помощью такой последовательности шагов:

(а) адрес возврата извлекается из вершины стека,

(б) если В - функция, то значение, обозначенное выражением из return-оператора, запоминается в ячейке, предписанной адресом значения в стеке,

(в) фрагмент стека процедуры В выталкивается из стека (это ставит в вершину стека фрагмент процедуры А),

(г) выполнение процедуры А возобновляется в ячейке, указанной в адресе возврата.

Пример 2.5. Рассмотрим процедуру ВНУТПОРЯДОК из алгоритма 2.1. Когда, например, она вызывает себя с фактическим параметром ЛЕВЬ1ЙСЫН[УЗЕЛ], она запоминает в стеке адрес нового значения параметра УЗЕЛ вместе с адресом возврата, указывающим, что по окончании работы этого вызова выполнение программы продолжается со строки 2. Таким образом, переменная УЗЕЛ эффективно заменяется на ЛЕВЫЙСЫН УЗЕЛ], где бы ни входил УЗЕЛ в это определение процедуры.

Описанную выше реализацию моделирует в некотором смысле соответствующий вариант без рекурсии (алгоритм 2.2). Однако там мы сделали так, что окончание выполнения вызова ВНУТПОРЯДОК с фактическим параметром ПРАВЫЙСЫН[УЗЕЛ] завершает выполнение и самой вызывающей процедуры. Поэтому нам не обяза-



тельно теперь хранить адрес возврата или УЗЕЛ в стеке, если фактическим параметром является ПРАВЫЙСЫН[УЗЕЛ]. □

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

Для подсчета времени работы алгоритма с рекурсией применяются рекуррентные уравнения. С i-й процедурой связывается функция Ti(n), обозначающая время выполнения i-й процедуры как функцию некоторого параметра п рассматриваемого входа. Обычно рекуррентное уравнение для ТДге) можно записать в терминах времен выполнения процедур, вызываемых процедурой i. Затем полученная система рекуррентных уравнений решается. Часто в алгоритме фигурирует только одна процедура, и Т{п) зависит лишь от значений Т{т) для конечного числа аргументов т, меньших п. В следующем разделе мы изучим решения некоторых часто встречающихся систем рекуррентных уравнений.

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

2.6. РАЗДЕЛЯЙ И ВЛАСТВУЙ

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

Рассмотрим задачу о нахождении наибольшего и наименьшего элементов множества S, содержащего п элементов. Для простоты будем считать, что п есть степень числа 2. Очевидный путь поиска наибольшего и наименьшего элементов состоит в том, чтобы искать их по отдельности. Например, следующая процедура находит наибольший элемент множества S, произведя п-1 сравнений его эле-



ментов:

begin

МАХ •<- произвольный элемент из 5; for все другие элементы из 5 do if jc>MAX then МАХ-д:

Аналогично можно найти наименьший из остальных п-I элементов, произведя п-2 сравнений. Итак, видим, что для нахождения наибольшего и наименьшего элементов при п>2 потребуется 2п-3 сравнений.

Применяя прием "разделяй и властвуй", мы разбили бы множество S на два подмножества Si и по п/2 элементов в каждом. Тогда описанный выше алгоритм нашел бы наибольший и наименьший элементы в каждой из двух половин с помощью рекурсии. Наибольший и наименьший элементы множества 5 можно было бы определить, произведя еще два сравнения - наибольших элементов в Si и Sg и наименьших элементов в них. Сформулируем этот алгоритм более точно.

Алгоритм 2.3. Нахождение наибольшего и наименьшего элементов множества

Вход. Множество S из га элементов, где п - степень числа 2, п>2.

Выход. Наибольший и наименьший элементы множества S.

Метод. К множеству S применяется рекурсивная процедура MAXMIN. Она имеет один аргумент представляющий собой множество S, такое, что S=2* при некотором и вырабатывает пару (а, Ь), где а - наибольший и Ь - наименьший элементы в S. Процедура MAXMIN приведена на рис. 2.12. □

Заметим, что сравнения элементов множества S происходят только на шаге 3, где сравниваются два элемента множества S, из которых оно состоит, и на шаге 7, где сравниваются maxl с тах2 и mini с min2. Пусть Т(п) - число сравнений элементов множества S, которые надо произвести в процедуре MAXMIN, чтобы найти наибольший и наименьший элементы п-элементного множества. Ясно, что Т(2)=1. Если п>2, то Т(п) - общее число сравнений, произведенных в двух вызовах процедуры MAXMIN (строки 5 и 6), работающей на множествах размера п/2, и еще два сравнения в

) Так как здесь подсчитываются только сравнения, способ прохождения аргументов несуществен. Однако, если множество S представлено массивом, можно организовать эффективный вызов MAXMIN, поставив указатели на первый и последний элементы подмножества S, состоящего из последовательных компонент этого массива.





0 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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0021