Реклама:

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

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

Особый интерес представляет рекурсивная процедура, которая вызывает саму себя либо непосредственно, либо через цепочку других процедур. Изучение рекурсивных процедур очень полезно для понимания того, как реализуются вызовы процедур и что в действительности представляют собой локальные переменные, поэтому давайте рассмотрим пример рекурсивной процедуры.

Ханойская башня - это название древней задачи, которая благодаря рекурсии имеет простое решение. В одном монастыре в Ханое есть три золотых колышка. На первый из них надето 64 концентрических золотых диска. Диаметр дисков уменьшается снизу вверх. Второй и третий колышки пусты. Монахи должны по одному перенести все диски на третий колышек, используя при необходимости второй колышек, но при этом после каждой итерации ни на одном из колышков диск большего диаметра не может оказаться на диске меньшего диаметра. Говорят, что когда они закончат, наступит конец света. Если вы хотите потренироваться, можете использовать пластиковые диски, и не 64, а поменьше. (Будем надеяться, что когда вы решите эту задачу, ничего страшного не произойдет. Чтобы произошел конец света, требуются именно 64 диска, причем обязательно золотых.) На рис. 5.23 показана начальная конфигурация для случая, когда число дисков (п) равно 5.

Чтобы переместить п дисков с колышка 1 на колышек 3, нужно сначала перенести 72-1 дисков с колышка 1 на колышек 2, затем перенести один диск с колышка 1 на колышек 3, потом перенести п - 1 диск с колышка 2 на колышек 3. Решение этой задачи для трех дисков иллюстрирует рис. 5.24.

Для решения задачи нам нужна процедура, которая позволяет переместить п дисков с колышка i на колышек j:

towers (n, i, j)

Процедуры

Рис. 5.23. Исходное положение дисков в задаче "Ханойская башня" для пяти дисков

Процедуры

Рис. 5.24. Решение задачи "Ханойская башня" для трех дисков

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

Все решение представлено в листинге 5.6. Рассмотрим такой вызов процедуры:

towers (3, 1, 3)

Этот вызов порождает еще три вызова:

towers (2, 1, 2) towers (1, 1, 3) towers (2, 2, 3)

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

Листинг 5.6. Процедура для решения задачи "Ханойская башня"

public void towers (int n, int i, int j) { int k; if (n == 1)

System.out.printlnCTlepeMecTMTb диск с " + i + "на" + j); else { k=6-i-j;

towers(n-l, i, k); towers (1, i, j); towers (n-1, k. j);

}

}

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

Помимо указателя стека (Stack Pointer, SP), который указывает на вершину стека, удобно иметь указатель фрейма (Frame Pointer, FP), указывающий на заданное место во фрейме, например, на связующий указатель, как в IJVM, или на первую локальную переменную.

На рис. 5.25 изображен стековый фрейм для машины с 32-разрядным словом. При первом вызове процедуры towers в стек помещаются значения n, i и j, а затем выполняется команда CALL, которая помещает в стек адрес возврата, 1012. Вызванная процедура сохраняет в стеке старое значение FP (1000) в ячейке 1016, а затем передвигает указатель стека для обозначения места хранения локальных переменных.

При наличии только одной 32-разрядной локальной переменной (к), указатель стека увеличивается на 4 - до 1020. На рис. 5.25, а показан результат всех этих действий.

Процедуры

Рис. 5.25. Состояние стека во время выполнения программы из листинга 5.6

Первое, что должна сделать процедура после вызова, - сохранить предыдущее значение FP (так, чтобы его можно было восстановить при выходе из процедуры), скопировать значение SP в FP и, возможно, увеличить SP на одно слово, в зависимости от того, куда указывает FP нового фрейма. В этом примере FP указывает на первую локальную переменную (хотя в IJVM регистр LV указывал на связующий указатель). Разные машины оперируют указателем фрейма немного по-разному, иногда помещая его в самый низ стекового фрейма, иногда - в вершину, а иногда - в середину, как на рис. 5.25. В этом отношении стоит сравнить рис. 5.25 с рис. 4.10, чтобы познакомиться с двумя разными способами обращения со связующим указателем. Возможны и другие способы. Но в любом случае обязательно должна быть возможность выйти из процедуры и восстановить предыдущее состояние стека.

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

А теперь вернемся к Ханойской башне. Каждый вызов процедуры добавляет новый фрейм в стек, а каждый выход из процедуры удаляет фрейм из стека. Посмотрим, как используется стек при реализации рекурсивных процедур, и начнем с вызова

towers (3, 1. 3)

На рис. 5.25, а показано состояние стека сразу после вызова процедуры. Сначала процедура проверяет, равно ли п единице, а установив, что п = 3, заполняет к и совершает вызов

towers (2, 1, 2)

Состояние стека после завершения этого вызова показано на рис. 5.25, 6. Далее процедура выполняется снова (вызванная процедура всегда начинается с начала). На этот раз условие n = 1 снова не подтверждается, поэтому процедура снова заполняет к и совершает вызов

towers (1, 1, 3)

Состояние стека после этого вызова показано на рис. 5.25, в. Счетчик команд указывает на начало процедуры. На этот раз условие подтверждается, и на экран выводится строка. Затем совершается выход из процедуры. Для этого удаляется один фрейм, а значения FP и SP переопределяются (рис. 5.25, г). Далее продолжается выполнение процедуры с адреса возврата:

towers (1, 1, 2)

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

towers (3, 1. 3)

Последовательный поток управления и переходы || Оглавление || Сопрограммы