Введение в теорию программирования. Функциональный подход

       

Рекурсивные функции и множества


Построим модель рекурсивных вычислений посредством формальной логики.

Под рекурсивным определением объекта (как в абстрактном теоретическом смысле, так и в аспекте практического программирования) будем понимать такое определение, которое содержит внутри себя ссылку на определяемый объект.

Основными видами объектов, которые будут использоваться в дальнейшем при рекурсивных вычислениях, будут следующие:

  1. функция;
  2. множество;
  3. тип.

Заметим, что рекурсивно определенный (т.е. построенный посредством рекурсии) объект, в свою очередь, носит название рекурсивного.

Заметим также, что определение рекурсивных объектов в математике происходит по индукции. При этом сначала формулируется базис индукции, как рекурсивное определение исключительных случаев при построении типа или множества (или вычисления функции), а затем шаг индукции, как рекурсивное правило построения того же объекта.

Для формализации рекурсивных функций и множеств в дальнейшем будут использоваться комбинаторная логика и теория вычислений Д. Скотта, основанная на понятии домена (последнее уточняется в ходе лекции).

В качестве практической иллюстрации определения понятия рекурсии рассмотрим ряд примеров рекурсивных функций, описанных на языке программирования 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 было упомянуто понятие рекурсивного типа для списков.

Рассмотрим достаточно формальные определения важнейших рекурсивных типов, а именно, списка и дерева, выраженные в словесном виде.



Содержание раздела