Рекурсивная функция

Cтраница 4

Один способ классификации рекурсивных функций восходит к истокам теории алгоритмов и связан с порождением тех или иных классов рекурсивных функций из множеств ( обычно конечных) достаточно простых исходных функций посредством различных вычислимых операций. Так строятся классификации Петер, Гжегорчика, Акста, Клини. При этом обычно возникает растущая иерархия ( цепочка) классов по некоторому трансфинитному типу. [46]

Программа Factol демонстрирует рекурсивную функцию факториала. [47]

Мы часто пользуемся рекурсивной функцией, называемой SUBSET, для определения, все ли атомы, указанные в списке фрагментов, имеются в молекуле. [48]

Однако в этом формализме рекурсивные функции ( за исключением тех из них, которые могут быть построены с помощью сложения и умножения) непосредственно не изобразимы, а только могут быть представлены в некотором смысле этого слова. [49]

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

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

Последовательность состояний ленивой SECD-машииы при вычислении выражения hd ( cons ( x, у. [52]

Вспомним также, что простые рекурсивные функции, такие, как факториал, могут теперь применяться без использования модифицированного У-комбинатора, а условные функции не нуждаются в таких замысловатых механизмах, как энергичная реализация. [53]

В листинге 12.1 приведена рекурсивная функция вычисления факториала. [54]

Страницы: 1 2 3 4