Cтраница 2
Например, при вычислении функции factorial ( 3) в соответствии с рекурсивным описанием нужно вычислить factorial ( 2), factorial ( 1) и factorial); в этом случае рекурсия имеет глубину в три уровня. Для факториальной функции глубина рекурсии при любом заданном значении аргумента видна сразу. Однако это - исключение, а обычно глубина рекурсии не является очевидной даже при простейших описаниях. Например, рассмотрим алгоритм Эвклида для вычисления наибольшего общего делителя ( НОД) двух положительных целых чисел. [16]
Например, при вычислении функции factorial ( 3) в соответствии с рекурсивным описанием нужно вычислить factorial ( 2), factorial ( 1) и factorial ( 0); в этом случае рекурсия имеет глубину в три уровня. Для факториальной функции глубина рекурсии при любом заданном значении аргумента видна сразу. Однако это - исключение, а обычно глубина рекурсии не является очевидной даже при простейших описаниях. Например, рассмотрим алгоритм Эвклида для вычисления наибольшего общего делителя ( НОД) двух положительных целых чисел. [17]
Разумеется, все сказанное относится не только к нашему PROLAN / F: скажем, рекурсивные описания были разрешены в процедурном языке Алгол-60 ( 1960 г.) и их возможность стала после этого обязательным свойством для любого взрослого языка. Заметим во избежание казусов, что при ( полной) рекурсии необходимо выполнение в процедурных ( алгоритмических) языках двух требований. [18]
В терминах унарной операции о бинарные операции сложения и умножения в множестве Р без труда определяются следующими рекурсивными описаниями. [19]
Не всегда описания функций с использованием PROG, но без рекурсий оказываются столь близкими по структуре к рекурсивным описаниям, как в случае функции ME MB. [20]
Мы замечаем, что третий вариант в приведенных выше определениях описывает именную группу через самое себя. Метод рекурсивного описания может успешно применяться и к синтаксису языка программирования. Общеизвестным примером является формальное описание языка АЛГОЛ-60 [2], которое дано в записи, получившей известность под названием нормальной формы Бэ-куса. [21]
Три выражения, разделенные двоеточиями, служат также для следующего описания функции: выр-ажение из середины выполняется первым; если его значение есть нуль, то выполняется первое выражение, в противном случае выполняется последнее выражение. Эта форма удобна для рекурсивных описаний, в которых функция используется для своего собственного описания. [22]
Если известно, что точка принадлежит внутренней части области, то ее можно использовать в качестве своего рода затравочного пиксела, окрашивая в ее цвет смежные пикселы до тех пор, пока не встретится контур. Если для этого алгоритма воспользоваться рекурсивным описанием, то выглядит оно достаточно просто. Пусть с цвет затравочного пиксела 5 и F - заполняемая область, степень заполнения которой соответствует шагу алгоритма. На первом шаге задается F S, затем на каждом шаге к области F добавляются все те пикселы, которые окрашены в цвет с и имеют непосредственного соседа в F. Таким образом, заполнение контура осуществляется на основе связности. Для обозначения этого процесса используют и название алгоритм засеивания. Допущение, что имеется такой затравочный пиксел, при работе на интерактивных графических системах является вполне реалистичным, поскольку в этом случае пользователь может указать этот пиксел, воспользовавшись световым пером или введя световой указатель внутрь контура. То же относится и к системам, в которых трехмерный объект задается вершинами аппроксимирующего его многогранника и на экране отображаются различные проекции этого объекта. При этом нетрудно определить точки, расположенные внутри получающихся в результате такого отображения многоугольников. [23]
Это определение формально эквивалентно предыдущему. На практике алгоритм, применяемый для синтаксического анализа, обычно предопределяет выбор способа записи рекурсивных описаний. Более сложным примером является описание арифметических выражений. [24]
Им предложены методы анализа 180 ] и синтеза [81] абстрактных автоматов. Важным результатом является доказательство алгоритмической неразрешимости проблемы распознавания регулярности события, рассмотренное в [87], что означает отсутствие алгоритма, определяющего по произвольному событию, заданному рекурсивным описанием, представимо ли оно в конечном автомате или нет. [25]
МНОГОКРАТНАЯ РЕКУРСИЯ - вид рекурсии, в к-рой участвуют сразу несколько переменных. Наборы значений этих переменных упорядочиваются лексикографически. Под это определение подходят многочисленные конкретные рекурсивные описания. Если в таком описании искомая функция не подставляется сама в себя, то оно сводится к примитивной рекурсии. [26]
Здесь заштрихованный прямоугольник представляет весь процесс вычисления факториальной функции. Это эквивалентно процедуре на языке АЛГОЛ, которая рекурсивно обращается к себе. Таким образом, существуют некоторые рекурсивные описания, которые не могут быть прямо переведены этим способом в итеративные процедуры. Из этого не следует, что существуют математические функции, которые могут быть вычислены только вычислительными системами, допускающими рекурсию. Мы должны четко уяснить разницу между математическим описанием функции и программой, вычисляющей эту функцию. [27]
На первый взгляд, выбор функций 0 ( х), s ( x) и s ( х) в качестве исходных может показаться случайным. Однако весьма примечательным и глубоким является то обстоятельство, что даже при нашем бедном выборе исходных функций можно получать рекурсивные описания для всех функций, наиболее употребительных в арифметике и в теории чисел: следовательно, расширение запаса исходных функций за счет присоедине пня других естественно напрашивающихся кандидатов не приведет к расширению класса функций, допускающих рекурсивные описания - Мы ограничимся здесь еще некоторыми иллюстрациями широты класса рекурсивных а значит и класса функций, вычислимых по Тьюрингу. [28]
Следует также отметить, что в случае добавления к основным функциям системы ( Z) каких-либо дополнительных вычислимых функций вместе с верифицируемыми аксиомами для них, аккер-мановская оценка будет нуждаться в соответствующей корректировке. По поводу таких расширений нашей формальной системы в начале изложенного доказательства1) специально отмечалось, что они не составляют препятствий для применимости этого доказательства. Приспособление упомянутой оценки к такого рода расширениям тоже не представляет принципиальных трудностей, но вновь добавляемые основные функции ( или по крайней мере наиболее быстро растущие из них) будут участвовать в рекурсивном описании этой оценки, и определение максимальной степени терма должно быть соответственным образом изменено. [29]
На первый взгляд, выбор функций 0 ( х), s ( x) и s ( х) в качестве исходных может показаться случайным. Однако весьма примечательным и глубоким является то обстоятельство, что даже при нашем бедном выборе исходных функций можно получать рекурсивные описания для всех функций, наиболее употребительных в арифметике и в теории чисел: следовательно, расширение запаса исходных функций за счет присоедине пня других естественно напрашивающихся кандидатов не приведет к расширению класса функций, допускающих рекурсивные описания - Мы ограничимся здесь еще некоторыми иллюстрациями широты класса рекурсивных а значит и класса функций, вычислимых по Тьюрингу. [30]