Рекурсивная подпрограмма
Cтраница 2
ЕСЛИ для нерекурсивных вызовов существует одна активация, то для рекурсивных подпрограмм может быть окиль угодно много активаций и поэтому невоэгда можно указать объем памяти для запоминания активационных записей. [16]
Это различие становится очень важным, когда мы обращаемся к рекурсивным подпрограммам и другим более общим структурам управления подпрограммами. Предположим, что имеется подпрограмма А, которая вызывает подпрограмму В, которая затем рекурсивно вызывает А. В существуют две активации А. При выполнении этой активации происходит вызов В, и выполнение А приостанавливается. Аналогично в момент рекурсивного вызова А приостанавливается выполнение активации В. Рекурсивный вызов А создает новую активацию А, совершенно независимую от первоначальной. Можно мыслить эту вторую активацию как абсолютно новую копию А, однако эта копия создается динамически в момент вызова, а не во время трансляции, как в нашем первоначальном правиле копирования. После завершения выполнения второй активации А управление возвращается в Б и затем, вероятно, в первую активацию А. Вызовы подпрограмм во второй активации А могут привести к дальнейшим рекурсивным активациям как А, так и В. Итак, во время выполнения может существовать много различных активаций подпрограммы, каждая из которых образуется как независимая копия одного и того же определения подпрограммы в исходном тексте программы. [17]
Для анализа игры NIM - игры с использованием набора палочек, в которой участвуют два человека, - могут применяться две рекурсивные подпрограммы. Игроки попеременно выбирают палочки из набора; игрок, который берет последнюю палочку, проигрывает. Игра полностью характеризуется двумя параметрами: NHEAP - начальное количество палочек в наборе, NTAKE - максимальное количество палочек, которые игрок может взять при своем очередном ходе; минимальное значение этого параметра равно единице. [18]
В переменной COUNTER сохраняется число обращений к подпрограмме, несмотря на отсутствие в его описании атрибута SAVE: всем локальным переменным, инициализирующимся в подпрограмме, атрибут SAVE назначается автоматически. В рекурсивной подпрограмме значение сохраняемой переменной остается общим для всех уровней вызова. [19]
Являются ли реентерабельные подпрограммы рекурсивными по своей природе. Являются ли рекурсивные подпрограммы реентерабельными. [20]
Многие процедуры, описанные в предыдущих разделах, были рекурсивными. Известно, что организация работы рекурсивных подпрограмм в общем случае оказывается довольно сложным делом. [21]
Как влияют на выбор среды ссылок рекурсивные подпрограммы. В любой момент выполнения у рекурсивной подпрограммы может быть много одновременно существующих активаций. Среды ссылок в различных активациях одной подпрограммы могут в общем случае отличаться друг от друга. Таким образом, перед нами стоит задача определения среды ссылок для каждой активации подпрограммы. [22]
Какое требование является более строгим для подпрограмм: рекурсия или реентерабельность. Другими словами, ответьте на следующие два вопроса: 1) Гарантирована ли правильная работа всех рекурсивных подпрограмм, если они повторно используются другими процессами. Гарантирована ли правильная работа реентерабельных подпрограмм, если они содержат вызовы самих себя. [23]
Считайте при этом, что инструкция CALL всегда создает новую активацию вызываемой подпрограммы, как в случае обычных рекурсивных подпрограмм. Заметьте, что каждая подпрограмма может быть много раз рекурсивно активирована и что выполняющаяся программа может быть первоначально вызвана из одной подпрограммы и позднее возобновлена из другой. [24]
В заключение несколько слов о работе оператора Exit в рекурсивных процедурах. Он срабатывает всегда на один уровень глубины рекурсии. Таким образом, выйти из рекурсивной подпрограммы до ее естественного завершения довольно непросто. [25]
После засылки в стек первого числа и знака операции нам может встретиться как число, так и открывающая скобка. В последнем случае нужно начать еще один вычислительный процесс; другими словами, мы хотим вызвать подпрограмму EVAL. Подпрограмма EVAL, таким образом, представляет собой пример подпрограммы, обращающейся к самой себе - рекурсивной подпрограммы. [26]
При наличии этой структурм рекурсивный алгоритм поиска ключа в BST - дсрСпе становится ОЧСРКЛ-ным: если дерево пусто, ичсст место прочая при поиске; если ключ поиска рдиек ключу н корне, имеет место ТТОПЕШЙНРС при поиске. В противном случае вы по / шлется поиск ( рекурсивно) н соответствующем поддереве. Фуккпнн starchR ti программе 12 8 непосредственно реализует этот алгоритм. Мы вызываем рекурсивную подпрограмму, которая принимает дерево в качестве первою аргумента и ключ н качестве второго начиная L орня лсревд и искомого ключа. [27]
При наличии этой структуры рекурсивный алгоритм поиска ключа в BST-дереве становится очевидным: если дерево пусто, имеет место промах при поиске; если ключ поиска равен ключу в корне, имеет место попадание при поиске. В противном случае выполняется поиск ( рекурсивно) в соответствующем поддереве. Функция searchR в программе 12.8 непосредственно реализует этот алгоритм. Мы вызываем рекурсивную подпрограмму, которая принимает дерево в качестве первого аргумента и ключ в качестве второго, начиная с корня дерева и искомого ключа. На каждом шаге гарантируется, что никакие части дерева, кроме текущего поддерева, не могут содержать элементы с искомым ключом. [29]
Большинство изученных в этой главе механизмов управления последовательностью действий являются механизмами общего назначения в том смысле, что они имеются во многих языках программирования и не зависят от структур данных или операций, используемых в этих языках. Вместе с тем было бы неправильно при изучении механизмов управления последовательностью действий не рассмотреть их тесную взаимосвязь со структурами данных и операциями языка. В то время как разнообразие механизмов управления последовательностью действий может оказывать влияние на общность языка, одним из важнейших факторов, определяющих естественность языка программирования, является возможность выбора механизмов управления последовательностью действий, соответствующих структурам данных и операциям, имеющимся в языке. Например, исключение циклических инструкций из Алгола и Фортрана безнадежно испортило бы эти языки, тогда как АПЛ вполне обходится без циклических инструкций. Аналогично, нельзя представить себе Лисп без рекурсивных подпрограмм, однако в Фортране рекурсия не допускается, а в Алголе рекурсия, хотя и допускается, играет незначительную роль. Чтобы объяснить это, нам нужно учесть то, что циклы удобны для поэлементной обработки массивов, а рекурсия - для обработки списочных структур. [30]
Страницы: 1 2 3