Другие формы рекурсии II Функциональное программирование Григорьева И.В.

Программирование вложенных циклов Соответствующие вложенным циклам процедурного программирования многократные повторения в функциональном программировании осуществляются обычно с помощью двух и более функций, каждая из которых соответствует простому циклу. Вызов такой рекурсивной функции используется в определении другой функции в качестве аргумента ее рекурсивного вызова. Естественно, аргументом рекурсивного вызова в определении функции может быть другой рекурсивный вызов. Это уже будет рекурсией более высокого порядка.

Рассмотрим сначала программирование вложенных циклов с помощью двух различных функций, а затем уже с помощью рекурсии более высокого порядка. Начнем рассматривать программирование вложенных циклов с сортировки списков. Определим сначала функцию ВСТАВЬ, которая добавляет элемент А в упорядоченный список L так, чтобы сохранилась упорядоченность, если порядок любых двух элементов задается предикатом РАНЬШЕ-Р:

_(defun ВСТАВЬ (а l порядок) (cond ((null l) (list a)) ((раньше-р а (саг l) порядок) ((раньше-р а (саг l) порядок) (cons a l)) (t (cons (car l) (t (cons (car l) (ВСТАВЬ a (cdr l) порядок))))) ВСТАВЬ

Предикат РАНЬШЕ-Р проверяет, находится ли элемент А ранее элемента В, в соответствии с расположением определенным порядком следования элементов в списке ПОРЯДОК: _(def tin РАНЬШЕ-Р (a b порядок) (cond ((null порядок) nil) ((eq a (car порядок)) t) ((eq a (car порядок)) t) ((eq b (car порядок)) nil) ((eq b (car порядок)) nil) ( t (РАНЬШЕ-Р a b ( t (РАНЬШЕ-Р a b (cdr порядок))))) (cdr порядок)))))

_(раньше-р 'b 'e '(a b с d e)) Т _(вставь b '(а с d) '(a b c d e)) (А В С D) ВСТАВЬ и РАНЬШЕ-Р образуют двухуровневую вложенную итеративную структуру. Неупорядоченный список можно отсортировать функцией СОРТИРУЙ которая рекурсивно ставит первый элемент списка на соответствующее место в предварительно упорядоченном хвосте списка:

_(defun СОРТИРУЙ (l порядок) (cond ((null l) nil) (t (вставь (саг l) (t (вставь (саг l) (СОРТИРУЙ (cdr l) порядок) порядок)))) (СОРТИРУЙ (cdr l) порядок) порядок))))СОРТИРУЙ _(СОРТИРУЙ '(b а с) '(a b c d е)) (А В С) Теперь рекурсия функций СОРТИРУЙ, ВСТАВЬ и РАНЬШЕ-Р образует уже трехуровневую вложенную повторяющуюся структуру.

Приведем еще функцию РАССТАВЬ, напоминающую своей структурой функцию СОРТИРУЙ и позволяющую элементы списка НОВЫЙ вставить в упорядоченный список L. Функция РАССТАВЬ повторяет процедуру вставки для каждого элемента списка НОВЫЙ:

_(defun РАССТАВЬ (новый l порядок) (cond ((null новый) l) (t (вставь (саr новый) (РАССТАВЬ (cdr новый) l порядок) порядок)))) порядок))))РАССТАВЬ _(расставь '(b c) '(a b d) (a b c d e)) (А В В С D)

Эту рекурсивную по аргументам функцию можно записать и в виде функции, рекурсивной по значению: _(defun РАССТАВЬ (новый l порядок) (cond ((null новый) l) (t (РАССТАВЬ (cdr новый) (вставь (саr новый) l порядок) порядок))))

Рекурсия более высокого порядка Рассмотрим теперь программирование вложенных циклов в такой форме, при которой в определении функции рекурсивный вызов является аргументом вызова этой же самой функции. В такой рекурсии можно выделить различные порядки) в соответствии с тем, на каком уровне рекурсии находится вызов. Такую форму рекурсии будем называть рекурсией более высокого порядка. Функции, которые мы до сих пор определяли, были функциями с рекурсией нулевого порядка.

В качестве классического примера рекурсии более высокого порядка часто приводится функция Аккермана, пользующаяся славой "плохой" функции: _(defun АККЕРМАН (m n) (cond ((= m 0) (+ n 1)) ((= n 0) (АККЕРМАН (- m 1) 1)) ((= n 0) (АККЕРМАН (- m 1) 1)) (t (АККЕРМАН (- m 1) (t (АККЕРМАН (- m 1) (AKKEPHAH m (- n 1)))))) АККЕРМАН _(аккерман 2 2) 7

_(аккерман 3 2) 27 Функция Аккермана является функцией с рекурсией первого порядка. Ее вычисление довольно сложно, и время вычисления растет лавинообразно уже при малых значениях аргумента.

В качестве другого Примера функции с рекурсией первого порядка приведем функцию В-ОДИН-УРОВЕНЬ, располагающую элементы списка на одном уровне, которую мы ранее определили, используя параллельную рекурсию:

_(defun в-один-уровень (l) (выравнять l nil)) В-ОДИН-УРОВЕНЬ _(defun ВЫРОВНЯТЬ (l результат) (cond ((null l) результат) ((atom l) (cons l результат)) (t (ВЫРОВНЯТЬ (car l) (t (ВЫРОВНЯТЬ (car l) (ВЫРОВНЯТЬ (cdr l) результат))))) (ВЫРОВНЯТЬ (cdr l) результат)))))ВЫРОВНЯТЬ

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

Функция ВЫРОВНЯТЬ работает следующим образом. Результат строится в списке РЕЗУЛЬТАТ. Если L - атом, то его можно непосредственно добавить в начало списка РЕЗУЛЬТАТ. Если L - список и его первый элемент является атомом, то все сводится к предыдущему состоянию на следующем уровне рекурсии, но в такой ситуации, когда список РЕЗУЛЬТАТ содержит уже вытянутый в один уровень оставшийся хвост.

В том случае, когда и голова списка L является списком, то его сначала приводят к одному уровню. Это делается с помощью рекурсивных вызов, погружающихся в головную ветвь до тех пор, пока там не встретится атом, который можно добавить в начало вытянутой к этому моменту в один уровень структуры. Встречающиеся таким образом атомы добавляются по одному к вытянутому хвосту. На каждом уровне при исчерпании списка на предыдущий уровень выдается набранный к данному моменту РЕЗУЛЬТАТ.

Следующее определение функции REVERSE, использующей лишь базовые функции и рекурсию, является примером еще более глубокого уровня рекурсии: _(defun REV (l) (cond ((null l) l) ((null (cdr l)) l) ((null (cdr l)) l) (t (cons (car (REV (cdr l))) (t (cons (car (REV (cdr l))) (REV (cons (car l) (REV (cdr (REV (cdr l) )))))

В определении использована рекурсия второго порядка. Вычисления, представленные этим определением, понять труднее, чем прежние. Сложная рекурсия усложняет и вычисления. В этом случае невозможно вновь воспользоваться полученными ранее результатами, поэтому одни и те же результаты приходится вычислять снова и снова.. Обращение списка из пяти элементов функцией REV требует 149 вызовов. Десятиэлементный список требует уже вызовов и заметное время для вычисления!

Как правило, многократных вычислений можно избежать, разбив определение на несколько частей и используя подходящие параметры для сохранения и передачи промежуточных результатов. Обычно в практическом программировании формы рекурсии более высокого порядка не используются.

Упражнения Определите с помощью упоминавшегося в тексте предиката РАНЬШЕ-Р предикат (АЛФАВИТ-Р х у), определяющий стоят ли слова, заданные списком букв, в алфавитном (словарном) порядке. После этого определите функцию (СЛОВАРЬ х), которая сортирует в алфавитном порядке неупорядоченное множество слов. Пример: Определите с помощью упоминавшегося в тексте предиката РАНЬШЕ-Р предикат (АЛФАВИТ-Р х у), определяющий стоят ли слова, заданные списком букв, в алфавитном (словарном) порядке. После этого определите функцию (СЛОВАРЬ х), которая сортирует в алфавитном порядке неупорядоченное множество слов. Пример: _(словарь '((ф у н к ц и я) (цикл)(р е к у р с и я))) ((Р Е К У Р С И Я) (ФУ Н К Ц И Я) (Ц И К Л)) Определите с их помощью функцию, составляющую из данных слов обратный словарь, т.е. перечень слов, который упорядочен по буквам, начиная от конца слова к его началу:

_(ословарь ((ф у н к ц и я) (цикл) (р е к у р с и я))) ((Ц И К Л) (Р Е К У Р С И Я) (Ф У Н К Ц И Я)) 15. Упорядоченное бинарное дерево состоит из узлов вида: 15. Упорядоченное бинарное дерево состоит из узлов вида: (элемент левое-поддерево правое-поддерево) В каждом узле выполнено следующее условие: все элементы из узлов его левого поддерева в некотором упорядочении (например, по числовой величине или в алфавитном порядке) предшествуют элементу из узла и соответственно элементы из узлов правого поддерева следуют за ним. Пример: (5 (3 (1 nil nil) (4 nil nil)) (7 (6 nil nil) (13 (11 nil nil) (15 nil nil))))

Определите функцию (ИЩИ а дерево), которая ищет в дереве элемент а. Определите функцию (ДОБАВЬ а дерево), которая добавляет в упорядоченное дерево дерево элемент а. (Подсказка: копируйте дерево по пути поиска и подправляйте нужное поддерево). Определите функцию (ДОБАВЬ а дерево), которая добавляет в упорядоченное дерево дерево элемент а. (Подсказка: копируйте дерево по пути поиска и подправляйте нужное поддерево). Определите функции (ПРЕДДЕРЕВО а дерево) и (ПОСЛЕДЕРЕВО а дерево), которые выделяют в отдельное (упорядоченное) дерево из первоначального дерева все узлы, предшествующие данному элементу а и следующие за ним. Определите функции (ПРЕДДЕРЕВО а дерево) и (ПОСЛЕДЕРЕВО а дерево), которые выделяют в отдельное (упорядоченное) дерево из первоначального дерева все узлы, предшествующие данному элементу а и следующие за ним. Определите после этого с их помощью функцию (ОБЪЕДИНИ р q), объединяющую два упорядоченных дерева р и q в одно общее (упорядоченное) дерево. Определите после этого с их помощью функцию (ОБЪЕДИНИ р q), объединяющую два упорядоченных дерева р и q в одно общее (упорядоченное) дерево.