Рекурсивные функции и множества
Построим модель рекурсивных вычислений посредством формальной логики.
Под рекурсивным определением объекта (как в абстрактном теоретическом смысле, так и в аспекте практического программирования) будем понимать такое определение, которое содержит внутри себя ссылку на определяемый объект.
Основными видами объектов, которые будут использоваться в дальнейшем при рекурсивных вычислениях, будут следующие:
- функция;
- множество;
- тип.
Заметим, что рекурсивно определенный (т.е. построенный посредством рекурсии) объект, в свою очередь, носит название рекурсивного.
Заметим также, что определение рекурсивных объектов в математике происходит по индукции. При этом сначала формулируется базис индукции, как рекурсивное определение исключительных случаев при построении типа или множества (или вычисления функции), а затем шаг индукции, как рекурсивное правило построения того же объекта.
Для формализации рекурсивных функций и множеств в дальнейшем будут использоваться комбинаторная логика и теория вычислений Д. Скотта, основанная на понятии домена (последнее уточняется в ходе лекции).
В качестве практической иллюстрации определения понятия рекурсии рассмотрим ряд примеров рекурсивных функций, описанных на языке программирования SML.
Начнем с описания известной нам функции факториала на языке SML:
fun fact n = if (n<2) 1 else n*fact(n-1);
Как следует из описания, значением функции является 1, если значение аргумента не превышает 1, и произведение чисел натурального ряда от 2 до заданного в противном случае. Заметим, что идентификатор функции fact явно присутствует как в левой, так и в правой части описания. Отметим также, что настоящий пример, по сути, представляет собой линейный вариант записи математического определения функции факториала по индукции. Наконец, еще одной особенностью рекурсии является многократность вызова одной и той же функции с различными значениями аргумента.
Далее рассмотрим описание функции, которая вычисляет длину списка:
fun length lst = if (lst==[]) 0 else 1 + length(tl(lst));
Заметим, что функция length использует встроенную функцию tl (получение "хвоста" списка) в ходе вычислений. Отметим также, что реализация рекурсивной обработки списка (который, кстати, представляет собой встроенный рекурсивный тип языка SML) выглядит лаконично и является весьма наглядной.
Наконец, рассмотрим рекурсивное определение функции sumpos, суммирующей первые n чисел натурального ряда (и повторяющей отмеченные особенности функции fact):
fun sumpos n = if (n<2) 1 else n + sumpos (n-1);
В ходе обсуждения примеров рекурсивного определения функций на языке программирования SML было упомянуто понятие рекурсивного типа для списков.
Рассмотрим достаточно формальные определения важнейших рекурсивных типов, а именно, списка и дерева, выраженные в словесном виде.
