Cтраница 1
Определение рекурсивных функций на типах данных является простым, систематическим и мощным. [1]
Определение рекурсивной функции, указанной выше, может выглядеть достаточно обоснованным, но итерационное решение ( см., например, программу на рис. 9.9) может оказаться более эффективным. Задачи, которые можно достаточно просто решить с использованием итерационных циклов, следует решать именно этим методом, а рекурсии необходимо применять только в тех случаях, когда задачи наиболее четко формируются с использованием рекурсий или они не имеют очевидного итерационного решения. [2]
Хотя представленные примеры программ являются не чем иным, как множеством определений рекурсивных функций, их можно рассматривать как спецификации сетей взаимосвязанных процессов. Итак, несмотря на то, что они достаточно удобны для вычисления при любой ленивой реализации языка, логические процессы в такой сети можно рассматривать как физические процессы, которые даже могут определять отдельные компоненты аппаратного обеспечения. [3]
В языках программирования высокого уровня, однако, необходимо иметь возможность записывать определение рекурсивных функций. [4]
Поскольку мы можем именовать наши собственные функции с помощью оператора def, то допустимо записать определение рекурсивной функции, сославшись на определяемую функцию внутри ее собственного тела. [5]
Третья семантика также непроцедурная, но она полностью аналогична семантике, обычно задаваемой для программ, написанных на языке определений рекурсивных функций. Ее формализация основывается на несколько более сложных понятиях, чем те, которые потребовались для определения двух других семантик. Эти понятия, по-видимому, лучше всего ввести в связи с простым ( хотя и довольно искусственным) примером. [6]
То, что при замене в терме ху переменной у на О произведение х-у принимает также значение 0, следует прямо из определения рекурсивной функции х-у посредством рекурсивных равенств. [7]
Можно заметить, что при каждом добавлении к сдаче очередной монеты возникает новая задача, подобная рассмотренной, но с другой суммой сдачи и новьш секущим наличием монет. Более того, эта новая задача меньше по объему вычислений, чем прежняя, и тем самым ближе к завершению. Такое пошаговое уменьшение размерности задачи предполагает необходимость определения рекурсивной функции с целью вычисления сдачи, отправляясь от некоторого начального положения. [8]
Было показано, каким образом абстрактные понятия упорядоченных наборов из п элементов и отображений, используемые математиками, соотносятся с нашим понятием функции, используемым в программировании. Мы познакомились также с определением отношения, которое интенсивно используется в теории баз данных. Наконец, было показано, как можно писать ламбда-выражения, преобразующие списковые структуры, не меняя их частей, и применили два различных типа определений рекурсивных функций. [9]
Процесс написания рекурсивного определения распадается на отдельные шаги. Эти определения кажутся очевидными впоследствии, но их не всегда легко придумать. Тем, кто привык программировать, интенсивно используя присваивания, вначале бывает трудно, особенно при использовании нисходящих определений функций. Трудность, по-видимому, в том, что мы должны повторно вызывать определяемую функцию в тот момент, когда еще не знаем, будет ли работать наше определение функции. Здесь следует применить тот же метод, что и при установлении корректности определения рекурсивной функции. [10]