Основы рекурсии Рекурсивно-логическое программирование Григорьева И.В.
ЯЗЫКИ ПРОГРАММИРОВАНИЯ ПРОЦЕДУРНЫЕ ЯЗЫКИДЕКЛАРАТИВНЫЕ ЯЗЫКИ Basic Cobol Fortran Pascal Ada... ЛОГИЧЕСКИЕ ЯЗЫКИФУНКЦИОНАЛЬНЫЕ ЯЗЫКИ Prolog KLO MandalaLisp APL Nial Logo Krc
Процедурное и функциональное программирование Процедурная программа состоит из последовательности операторов и предложений, управляющих последовательностью их выполнения. Типичными операторами являются операторы присваивания и передачи управления, операторы ввода-вывода и специальные предложения для организации циклов. Из них можно составлять фрагменты программ и подпрограммы. В основе такого программирования лежат взятие значения какой-то переменной, совершение над ним действия и сохранение нового значения с помощью оператора присваивания, и так до тех пор пока не будет получено желаемое окончательное значение.
Функциональная программа состоит из совокупности определений функций. Функции, в свою очередь, представляют собой вызовы других функций и предложений, управляющих последовательностью вызовов. Вычисления начинаются с вызова некоторой функции, которая в свою очередь вызывает функции, входящие в ее определение и т.д. в соответствии с иерархией определений и структурой условных предложений. Функции часто либо прямо, либо опосредованно вызывают сами себя.
"Чистое" функциональное программирование не признает присваиваний и передач управления. Разветвление вычислений основано на механизме обработки аргументов условного предложения. Повторные вычисления осуществляются через рекурсию, являющуюся основным средством функционального программирования.
Списки строятся рекурсивно Рекурсия в Лиспе основана на математической теории рекурсивных функций. Рекурсия хорошо подходит для работы со списками, так как сами списки могут состоять из подсписков, т.е. иметь рекурсивное строение. Для обработки рекурсивных структур совершенно естественно использование рекурсивных процедур.
Списки можно определить с помощью следующих правил Бэкуса-Наура: список -> NIL; список либо пуст, либо это список -> (голова. хвост) ; точечная пара, хвост; которой является списком голова -> атом; рекурсия "в глубину" голова -> список хвост -> список; рекурсия "в ширину"
Списки можно определить и в следующей форме, которая подчеркивает логическую рекурсивность построения списков из атомов и подсписков: список -> NIL список ->(элемент элемент...) элемент -> атом элемент -> список; рекурсия
Лисп основан на рекурсивном подходе В программировании на Лиспе рекурсия используется для организации повторяющихся вычислений. На ней же основано разбиение проблемы и разделение ее на подзадачи, решение которых, насколько это возможно, пытаются свести к уже решенным или в соответствии с основной идеей рекурсии к решаемой в настоящий момент задаче.
Теория рекурсивных функций Теория рекурсивных функций наряду с алгеброй списков и лямбда-исчислением является еще одной опорой, на которой покоится Лисп. В этой области математики изучаются теоретические вопросы, связанные с вычислимостью. Под вычислимыми понимаются такие задачи, которые в принципе можно запрограммировать и решить с помощью вычислительной машины.
Теория рекурсивных функций предлагает наряду с машиной Тьюринга, лямбда-исчислением и другими теоретическими формализмами эквивалентный им формализм алгоритмической вычислимости. Основная идея рекурсивного определения заключается в том, что функцию можно с помощью рекуррентных формул свести к некоторым начальным значениям, к ранее определенным функциям или к самой определяемой функции, но с более "простыми" аргументами. Вычисление такой функции заканчивается в тот момент, когда оно сводится к известным начальным значениям. Например, числа Фибоначчи О, 1, 1, 2, 3, 5,... используя префиксную нотацию Лиспа, можно определить с помощью следующих рекуррентных формул
Класс функций, получаемых таким образом, называют классом примитивно рекурсивных функций. Существуют также функции, не являющиеся примитивно рекурсивными. В качестве примера можно привести функцию Аккермана, которую можно задать следующими рекуррентными формулами: (Ack 0 х у) = (+у х), (Ack 1 х у) = (* у х), (Ack 2 х у) = (^ У х), (Ack (+ z 1) х у) = к значениям у х-1 раз применяется операция (lambda (и v) (Ack z и v))
Заданная с помощью приведенной выше схемы функция Аск не является примитивно рекурсивной, хотя она и вычислимая, т.е. ее можно определить и на основе этого определения вычислить ее значение за конечное время. Можно показать, что существуют функции, значения которых можно вычислить с помощью алгоритма, но которые нельзя алгоритмически описать.
Вычисление такой функции может быть бесконечным. В качестве примера приведем функцию (f n т), результатом которой является 1 в случае, если в десятичной записи числа встречается фрагмент из последовательности повторяющихся цифр m длиной n. Можно показать, что алгоритм вычисления этой функции существует, но нам неизвестно, каков он. Мы можем лишь пытаться вычислять знаки в надежде, что искомая последовательность обнаружится, но определить, закончится ли когда-нибудь вычисление, мы не можем. Такие функции называются общерекурсивными.
Простая рекурсия Мы будем говорить, что рекурсия простая, если вызов функции встречается в некоторой ветви лишь один раз. Простой рекурсии в процедурном программировании соответствует обыкновенный цикл. Определим функцию КОПИЯ, которая строит копию списка. Копия списка логически идентична первоначальному списку:
_(defun КОПИЯ (I) ( cond ( (null I) nil) ;условие окончания (t (cons (car l) ; рекурсия (КОПИЯ (cdr (I)))))) КОПИЯ _(копия'(a b с)) (А В С) ; логическая копия _(eq '(a b с) (копия '(a b с))) NIL ; физически различные списки
Эта функция является рекурсивной по аргументу, поскольку рекурсивный вызов стоит на месте аргумента функции CONS. Условное предложение из тела функции содержит две ветви: ветвь с условием окончания и ветвь с рекурсией, с помощью которой функция проходит список, копируя и укорачивая в процессе этого список по направлению CDR.
Мы можем понаблюдать за работой этой функции при помощи содержащихся в интерпретаторе средств трассировки. Трассировка функции включается при помощи директивы, которая в отличие от обычных функций не вычисляет свой аргумент. (TRACE функция) _(trace копия) Трассировку можно отменить аналогичной по форме директивой UNTRACE.
MEMBER проверяет, принадлежит ли элемент списку В качестве второго примера простой рекурсии возьмем встроенный предикат Лиспа MEMBER. С его помощью можно проверить, принадлежит ли некоторый элемент данному списку или нет. Тело функции состоит из условного предложения, содержащего три ветви. Они участвуют в процессе вычислений в зависимости от возникающей ситуации:
1. ((null I) nil): Аргумент - пустой список либо с самого начала, либо потому, что просмотр списка окончен. 2. ((eql (car I) a) I): Первым элементом является искомый элемент. В качестве результата возвращается список, в котором А - первый элемент. 3. (t (MEMBER1 a (cdr l))): Ни одно из предыдущих утверждений не верно: в таком случае либо элемент содержится в хвосте списка, либо вовсе не входит в список. Эта задача аналогична первоначальной, только она меньше по объему. Поэтому мы можем для ее решения применить сам предикат к хвосту списка.
Порядок следования ветвей в условном предложении существеннен При определении порядка следования условий основным моментом является то, что сначала проверяются всевозможные условия окончания, а затем ситуации, требующие продолжения вычислений. При помощи условий окончания последовательно проверяются все особые случаи и программируются соответствующие результирующие выражения. На исключенные таким образом случаи можно в последующем не обращать внимания.
Рассмотрим в качестве полезного урока вариант предиката MEMBER, в котором условия перечислены в неверном порядке. Для того чтобы была виднее неправильная работа предиката, определим его в отличие от Коммон Лиспа так, чтобы в случае, если элемент найден, он возвращал не хвост списка, а значение Т.
_(defun MEMBER2 (а l) (cond ((eql a (car I)) t) ; сначала EQL ((null I) nil) ; затем NULL (t (MEMBER2 a (cdr l))))) MEMBER2 _(member2 'd '(a b с d)) Т ; результат верен (member2 nil '(nil)) Т ; результат верен (member2nil nil) T ; пустого списка. Ошибка!
Ошибочный результат является следствием того, что в момент применения предиката EQL неизвестно, завершился ли список или проверяется список (NIL.хвост). Причиной возникновения ошибки служит принятое в Лисп-системе соглашение, что головой пустого списка является NIL, а это приводит к тому, что как (CAR NIL), так и (CAR '(NIL. хвост)) возвращают в качестве результата NIL. В "чистом" Лиспе значение формы (CAR NIL) не определено, поскольку NIL - атом.
APPEND объединяет два списка _(defun APPEND1 (x y) (cond ((null x) y) (t (cons (car x) (APPEND1 (cdr x) y))))) APPEND1
Приведем пример: _(append1 '(с л и) '(я н и е)) (с л и я н и е) _(append1 '(а b) nil) (А В) _(append1 '(а b nil) '(nil)) (а b nil nil) Последним аргументом функции APPEND в Коммой Лиспе не обязательно должен быть список. В этом случае результатом будет точечное выражение.
REMOVE удаляет элемент из списка Все предыдущие определения функций содержали лишь один рекурсивный вызов. Рассмотрим в качестве следующего примера содержащую две рекурсивные ветви встроенную функцию REMOVE, которая удаляет из списка все совпадающие с данным атомом (EQL) элементы и возвращает в качестве значения список из всех оставшихся элементов.
_(defun REMOVE1(а l) (cond ((null l) nil) ((eql a (car l)) (REMOVE1 a (cdr l))) (t (cons (car l) (REMOVE1 a (cdr l)))))) REMOVE1 _(remove1 л '(с л о н)) (C 0 H) _(remove1 'b '(a (b c))) (В C) _(remove1 (а b) '((а b) (с d))) ((А В) (СD))
Список L сокращается путем удаления всех идентичных А в смысле EQL элементов (вторая ветвь) и копирования в результирующий список (CONS) остальных элементов (третья ветвь) до тех пор, пока условие окончания (NULL) не станет истинным. Результат формируется в процессе возврата аналогично функции APPEND1.
Замечание: Во многих Лисп-системах функция REMOVE определена с использованием предиката EQUAL вместо EQL, с помощью такой функции можно удалять элементы, являющиеся списками. В Коммон Лиспе предикат сравнения для функции REMOVE можно задать непосредственно при ее вызове ключевым параметром :TEST. Приведем пример: _(remove '(a b) '((a b) (с d)) :test 'equal) ((С D))
SUBSTITUTE заменяет все вхождения элемента Функция SUBSTITUTE, заменяющая все вхождения данного элемента СТАРЫЙ в списке L на элемент НОВЫЙ, работает подобно функции REMOVE. Замена производится лишь на самом верхнем уровне списка L, т.е. рекурсия осуществляется только по хвостовой части списка (в направлении CDR).
Как и при копировании списка процедуру замены элемента можно обобщить так, чтобы список обрабатывался и в глубину, для этого в случае, когда голова списка является списком, нужно осуществить рекурсию и по головной части.
_(defun SUBSTITUTE1 (новый старый l) (cond ((null l) nil) ((eql старый (car l)) (cons новый (SUBSTITUTE1 новый старый (cdr l)))) (t (cons (car l) (SUBSTITUTE1 новый старый (cdr 1)))))) SUBSTITUTE1 _(substitute1 'b 'x '(а х х а)) (А В В A)
REVERSE обращает список В приведенных примерах мы просматривали список в соответствии с направлением указателей в списочных ячейках слева направо. Но что делать, если нужно обрабатывать список справа налево, т.е. от конца к началу?
Рассмотрим для примера функцию REVERSE, которая также является встроенной функцией Лиспа. REVERSE изменяет порядок элементов в списке (на верхнем уровне) на обратный. Для обращения списка мы должны добраться до его последнего элемента и поставить его первым элементом обращенного списка. Хотя нам непосредственно конец списка не доступен, можно, используя APPEND, описать необходимые действия.
_(defun REVERSE1 (l) (cond ((null l) nil) (t (append (REVERSE1 (cdr l) (cons (car l) nil))))) REVERSE1 _(reverse1 (a b c)) (С В А) _(reverse1 '((A B) (CD))) ((CD) (А В))
Идея определения состоит в следующем: берем первый элемент списка (CAR L), делаем из него с помощью вызова (CONS (CAR L) NIL) одноэлементный список и объединяем его функцией APPEND с перевернутым хвостом. Хвост списка сначала обращается рекурсивным вызовом (REVERSE1 (CDR L)). Попробуем проследить, как происходит такое обращение: _(trace reverse1)
Использование вспомогательных параметров Список является несимметричной структурой данных, которая просто проходится слева направо. Во многих случаях для решения задачи более естественны вычисления, производимые справа налево.
Например, то же переворачивание списка было бы гораздо проще осуществить, если бы был возможен непосредственный доступ к последнему элементу списка. Такое противоречие между структурой данных и процессом решения задачи приводит к трудностям программирования и может служить причиной неэффективности.
Cоответствующий механизм можно легко осуществить, используя вспомогательную функцию, у которой нужные вспомогательные переменные являются параметрами. Тогда для функции REVERSE мы получим такое определение:
_(defun reverse2 (l) (ПЕРЕНОС l nil)) REVERSE2 _(defun ПЕРЕНОС (l результат) (cond ((null l) результат) (t (ПЕРЕНОС (cdr l) (cons (car l) результат))))) ПЕРЕНОС
Вспомогательная функция ПЕРЕНОС рекурсивна по значению, так как результирующим выражением ее тела является либо непосредственно рекурсивный вызов, либо готовое значение. С помощью этой функции элементы переносятся таким образом, что на каждом шаге рекурсии очередной элемент переходит из аргумента L в аргумент РЕЗУЛЬТАТ.
Упражнения Определите встроенную функцию LAST, возвращающую последний элемент списка. Определите функцию, удаляющую из списка последний элемент. Определите предикат, проверяющий, является ли аргумент одноуровневым списком. Определите функцию (ЛУКОВИЦА n), строящую N- уровневый вложенный список, элементом которого на самом глубоком уровне является N. Определите функцию ПЕРВЫЙ-АТОМ, результатом которой будет первый атом списка. Пример: _(первый-атом '(((а Ь)) с d)) А
Определите функцию, удаляющую из списка первое вхождение данного элемента на верхнем уровне. Что можно сказать о равенстве значений следующих выражений: (append х (append у z)) (append (append x у) z) Запишите выражение (REVERSE (APPEND X Y)), используя те же функции, в другом виде.
Заполните значениями функций следующую таблицу: fn(fn '(A) NIL) (fn NIL '(A)) append: list: cons: Определите функцию, которая обращает список (а b с) и разбивает его на уровни (((с) b) а). Определите функции, преобразующие список (а Ь с) к виду (а (Ь (с))) и наоборот. Определите функции, осуществляющие преобразования между видами (а b с) и (((а) Ь) с).