Рекурсивный вызов - подпрограмма
Cтраница 1
Рекурсивный вызов подпрограммы в некоторых языках программирования невозможен, но и в том случае, когда он возможен, эффективность применения рекурсии может быть недостаточно высокой. [1]
Рекурсия в форме рекурсивных вызовов подпрограмм является одной из важнейших структур управления последовательностью действий в программировании. Многие алгоритмы естественнее всего записываются с помощью рекурсии. Более того, в чистом Лиспе итерация не допускается; рекурсия является единственным механизмом для повторения последовательности операций. [2]
В Фортране не разрешены рекурсивные вызовы подпрограмм, но в большинстве реализаций не производится проверок на наличие таких ошибок. Более того, рекурсивный вызов будет выполнен надлежащим образом, но позднее программа зациклится при попытке возвратиться из подпрограммы, вызванной рекурсивно. [3]
Если ослабить требование 1 и допустить рекурсивные вызовы подпрограмм, то программист не заметит значительных отличий на языковом уровне, поскольку обычно рекурсивные и нерекурсивные вызовы подпрограмм не отличаются синтаксически. Однако, хотя рекурсивные вызовы не меняют синтаксис языка, средства моделирования, необходимые для рекурсивных вызовов подпрограмм, будут существенно разными в случае рекурсивных и нерекурсивных вызовов. Аппаратура лишь в редких случаях прямо соответствует структурам рекурсивных вызовов, поэтому последние требуют значительного объема программного моделирования. Это приводит во время выполнения программы к большой разнице в эффективности между нерекурсивными и рекурсивными механизмами. [4]
Так, в чистом Лиспе, имеющем только рекурсивные вызовы подпрограмм, теоретически ничто не потеряно из-за от-сутствия меток и переходов. Ясно, однако, что мы не дали удо-влетворительного ответа. Можем ли мы практически записать любую программу без переходов, и если да, то что следует использовать для управления вместо них. [5]
Содержит ли программа циклы иди рекурсивные вызовы подпрограмм. Влияет ли результат одной команды программы на аргумзнт Другой команды. [6]
Статическое распределение памяти эффективо, поскольку на управление памятью во время выполнения не тратится ни времени, ни памяти. Однако этот метод несовместим с рекурсивными вызовами подпрограмм, со структурами данных, размер которых зависит от вычисляемой или вводимой информации, и со многими другими желательными возможностями языка. Читатель, однако, не должен упускать из вида важность статического метода распределения памяти - для многих программ вполне достаточно статического распределения. Два широко используемых языка программирования, Фортран и Кобол, сконструированы в расчете исключительно на статическое распределение памяти. [7]
Если ослабить требование 1 и допустить рекурсивные вызовы подпрограмм, то программист не заметит значительных отличий на языковом уровне, поскольку обычно рекурсивные и нерекурсивные вызовы подпрограмм не отличаются синтаксически. Однако, хотя рекурсивные вызовы не меняют синтаксис языка, средства моделирования, необходимые для рекурсивных вызовов подпрограмм, будут существенно разными в случае рекурсивных и нерекурсивных вызовов. Аппаратура лишь в редких случаях прямо соответствует структурам рекурсивных вызовов, поэтому последние требуют значительного объема программного моделирования. Это приводит во время выполнения программы к большой разнице в эффективности между нерекурсивными и рекурсивными механизмами. [8]
После умножения выполняется команда возврата RTS. В этот момент в стеке может быть либо адрес возврата в программу, вызвавшую FACTOR, либо очередная двухсловная запись, выполненная при рекурсивном вызове подпрограммы FACTOR. В последнем случае в R1 загружается новое значение N, которое будет умножено на промежуточный результат, хранимый в стеке, и процесс повторится. Если же вычисление факториала закончено, то управление передается в вызывающую программу, а результат остается в стеке. [9]
Рекурсию можно использовать в подпрограммах языка ассемблера, но в этом случае накладываются некоторые ограничения на организацию вызова подпрограммы и соглашения по передаче параметров. Не следует хранить адреса возврата, параметры и локальные переменные в специально выделяемых фиксированных ячейках памяти, поскольку эти данные будут стерты при первом же рекурсивном вызове подпрограммы самой себя. Для устранения такой ситуации необходимо назначать при каждом рекурсивном вызове новую область памяти для адреса возврата, параметров и локальных переменных, а затем после возврата из подпрограммы перераспределять эту область памяти, исходя из имеющихся потребностей. Подходящей структурой для хранения этих элементов данных является стек. [10]
 |
Свободная область памяти организована в виде дека. [11] |
Следует ли это свойство связывать с понятием типа переменной - вопрос особый; лучше, если пользователи не будут углубляться в этот вопрос. На практике во многих случаях в этом нет необходимости, так как память не очень загружена. Например, из-за того, что в языке Фортран рекурсивный вызов подпрограммы не допускается, отношение между вызывающей и вызываемой программами имеет вид типа исходный-порожденный, и все необходимое распределение памяти может быть выполнено при обращении к подпрограмме. [12]
Структура типа стек - это одномерный массив переменной длины, обладающий той особенностью, что включение и исключение элементов ограничено только одним концом массива, называемого вершиной стека. Стек представляет собой структуру ( см. рис. 1.1 6), в которой первым обрабатывается тот элемент данных, который введен последним. Для обработки древовидных структур, о которых речь пойдет ниже, обычно используют рекурсивную обработку, основанную на вызове подпрограммы самой себя. При рекурсивном вызове подпрограммы текущие значения переменных засылаются в стек и переменным присваиваются новые значения. [13]
Управляющие структуры Лиспа относительно просты. Выражения, используемые для составления программ, записываются в строго кембриджской польской форме и могут содержать условное ветвление. Конструкция PROG дает простую структуру для записи последовательности выражений, при этом можно употреблять метки и инструкции goto. Имеются примитивы ( называемые функционалами) для последовательного генерирования элементов списков. В большинстве программ на Лиспе широко используются рекурсивные вызовы подпрограмм. [14]
АПЛ определяется как функция, возвращающая некоторое значение. Управляющие структуры АПЛ совсем просты. Внутри выражений отсутствует иерархия операций и выражения вычисляются справа налево, а не слева направо, как это обычно делается в других языках. Между инструкциями и подпрограммами допускаются только простые goto, номера инструкций в которых могут быть вычисляемыми, разрешаются рекурсивные вызовы подпрограмм. Кроме того, можно задавать различные виды прерываний, которые приоста-наливают выполнение программы и возвращают управление программисту, сидящему за терминалом; прежде чем возобновить выполнение программы с указанной инструкции, он может ввести новые данные, изменить значения старых данных или модифицировать программу. [15]
Страницы: 1