ДРУГИЕ ФОРМЫ РЕКУРСИИ I Функциональноепрограммирование Григорьева И.В. - презентация

1 ДРУГИЕ ФОРМЫ РЕКУРСИИ I Функциональноепрограммирование Григорьева И.В.

2 В определении функции рекурсия может принимать различные формы. Ранее мы рассмотрели простую рекурсию, когда одиночный рекурсивный вызов функции встречается в одной или нескольких ветвях. Рассмотрим различные формы рекурсии: Рассмотрим различные формы рекурсии: 1)параллельную рекурсию, когда тело определения функции f содержит вызов некоторой функции g, несколько аргументов которой являются рекурсивными вызовами функции f: (defun f (g...(f...)... (f...)...)

3 2)взаимную рекурсию, когда в определении функции f вызывается некоторая функция g, которая в свою очередь содержит вызов функции f: (defun f (g...)..) (defun g......(f...)...)

4 3) рекурсию более высокого порядка, когда аргументом рекурсивного вызова является рекурсивный вызов: (defun f......(f...(f...)...)

5 Параллельное ветвление рекурсии Рекурсию называют параллельной, если она встречается одновременно в нескольких аргументах функции. Рассмотрим в качестве примера копирование списочной структуры на всех уровнях. Таким образом, мы получим обобщение функции COPY-LIST Коммон Лиспа COPY-TREE. Слово TREE (дерево) в названии функции возникло в связи с тем, что в определении функции список трактуется как соответствующее точечной паре бинарное дерево, у которого левое поддерево соответствует голове списка, а правое поддерево - хвосту:

6 дерево -» NIL; пустое дерево дерево -» NIL; пустое дерево дерево -» атом; лист дерева дерево -» атом; лист дерева дерево -» (дерево. дерево) ; точечная пара – дерево дерево -» (дерево. дерево) ; точечная пара – дерево _(defun C0PY-TREE1 (l) (cond ((null l) nil) ((atom l) l) ((atom l) l) (t (cons (t (cons (COPY-TREE1 (car l)) ; копия головы (COPY-TREE1 (car l)) ; копия головы (COPY-TREE1 (cdr 1)))))); копия xвоста (COPY-TREE1 (cdr 1)))))); копия xвоста COPY-TREE1

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

8 Таким же образом рекурсией по голове и хвосту списка можно проверить логическую идентичность двух списков на основе сравнения структуры и атомов, составляющих список. Определим далее уже известный нам предикат EQUAL через применяемый к символам предикат EQ: (Ограничим наше рассмотрение лишь символами и списками, состоящими из списков.)

9 (defun EQUAL1 (х у) (cond ((null x)(null у)) ((atom x) (cond ((atom у) (eq x y)) (t nil))) ((atom y) nil) (t (and (EQUAL1 (car x) (car у)) (EQUAL1 (cdr x) (cdr y)))))) (EQUAL1 (cdr x) (cdr y))))))

10 Приведем еще один пример параллельной рекурсии. Рассмотрим функцию ОБРАЩЕНИЕ. Эта функция предназначена для обращения порядка следования элементов списка и его подсписков независимо от их места и глубины вложенности. Ранее определенная нами простой рекурсией функция REVERSE оборачивала лишь верхний уровень списка:

11 _defun ОБРАЩЕНИЕ (l) (cond ((atom l) l) ((null (cdr l)) ((null (cdr l)) (cons (ОБРАЩЕНИЕ (car l)) nil)) (t (append (ОБРАЩЕНИЕ (cdr l)) (ОБРАЩЕНИЕ (cons (car l nil)))))) (t (append (ОБРАЩЕНИЕ (cdr l)) (ОБРАЩЕНИЕ (cons (car l nil))))))ОБРАЩЕНИЕ _(ОБРАЩЕНИЕ '(a (b (c (d))))) ((((D) C) B) A) _(setq палиндром ((a (р о з а) (у п а л а) (н a) ( л а п у) (А з о р a))) ( л а п у) (А з о р a))) ((А) (РОЗА)...) _(обращение палиндром) ((A P 0 3 А) (У П А Л) (А Н) (А Л А П У) (А 3 О Р) (А))

12 Применяя параллельную рекурсию, можно списочную структуру (двоичного дерева) ужать в одноуровневый список, т.е. удалить все вложенные скобки. _defun В-ОДИН-УРОВЕНЬ (l) (cond ((null l) nil) ((atom l) (cons (car l) nil)) (t (append (В-ОДИН-УРОВЕНЬ (саг l)) (В-ОДИН-УРОВЕНЬ (cdr l)))))) В-ОДИН-УРОВЕНЬ

13 _(в-один-уровень '(а (((((b)))) (с d) e))) (А В С D Е) _(equal (в-один-уровень палиндром) (в-один-уровень (обращение палиндром))) Т Функция В-ОДИН-УРОВЕНЬ объединяет (функцией APPEND) ужатую в один уровень голову списка и ужатый хвост. Если голова списка является атомом, то из него формируется список, поскольку аргументы функции APPEND должны быть списками.

14 Взаимная рекурсия Рекурсия является взаимной между двумя или более функциями, если они вызывают друг друга. Для примера можно представить ранее определенную нами функцию обращения или зеркального отражения в виде двух взаимно рекурсивных функций следующим образом:

15 (defun ОБРАЩЕНИЕ (l) (cond ((atom l) l) (t (ПЕРЕСТАВЬ l nil)))) (t (ПЕРЕСТАВЬ l nil)))) (defun ПЕРЕСТАВЬ (l результат) (cond ((null l) результат) (t (ПЕРЕСТАВЬ (cdr l) (cons (ОБРАЩЕНИЕ (car l)) результат)))))

16 Функция ПЕРЕСТАВЬ используется в качестве вспомогательной функции с дополнительными параметрами таким же образом, как и ранее вспомогательная функция ПЕРЕНОС использовалась совместно с функцией REVERSE3. В процессе построения обращенного списка она заботится и о том, чтобы возможные подсписки были обращены. Она делает это не сама, а передает эту работу функции ОБРАЩЕНИЕ. Глубина и структура рекурсии зависят от строения списка L. Кроме участия во взаимной рекурсии функция ПЕРЕСТАВЬ рекурсивна и сама о себе.

17 Упражнения Определите функцию, вычисляющую, сколько всего атомов в списке (списочной структуре). Определите функцию, вычисляющую, сколько всего атомов в списке (списочной структуре). Определите функцию, вычисляющую глубину списка (самой глубокой ветви). Определите функцию, вычисляющую глубину списка (самой глубокой ветви). Запрограммируйте интерпретатор ВЫЧИСЛИ, который преобразует инфиксную запись операций (например, +, -, * и /) выражения в префиксную и возвращает значение выражения. Пример: Запрограммируйте интерпретатор ВЫЧИСЛИ, который преобразует инфиксную запись операций (например, +, -, * и /) выражения в префиксную и возвращает значение выражения. Пример: _(ВЫЧИСЛИ '((-2 + 4) * 3)) 6 Определите функцию (ПЕРВЫЙ- СОВПАДАЮЩИЙ х у), которая возвращает первый элемент, входящий в оба списка х и у, в противном случае NIL. Определите функцию (ПЕРВЫЙ- СОВПАДАЮЩИЙ х у), которая возвращает первый элемент, входящий в оба списка х и у, в противном случае NIL.

18 Определите предикат МНОЖЕСТВО-Р, который проверяет, является ли список множеством, т.е. входит ли каждый элемент в список лишь один раз. Определите предикат МНОЖЕСТВО-Р, который проверяет, является ли список множеством, т.е. входит ли каждый элемент в список лишь один раз. Определите функцию МНОЖЕСТВО, преобразующую список в множество. Определите функцию МНОЖЕСТВО, преобразующую список в множество. Определите предикат РАВЕНСТВО- МНОЖЕСТВ, проверяющий совпадение двух множеств (независимо от порядка следования элементов). Подсказка: используйте функцию REMOVE, удаляющую данный элемент из множества. Определите предикат РАВЕНСТВО- МНОЖЕСТВ, проверяющий совпадение двух множеств (независимо от порядка следования элементов). Подсказка: используйте функцию REMOVE, удаляющую данный элемент из множества. Определите функцию ПОДМНОЖЕСТВО, которая проверяет, является ли одно множество подмножеством другого. Определите также СОБСТВЕННОЕ ПОДМНОЖЕСТВО. Определите функцию ПОДМНОЖЕСТВО, которая проверяет, является ли одно множество подмножеством другого. Определите также СОБСТВЕННОЕ ПОДМНОЖЕСТВО.

19 Определите предикат НЕПЕРЕСЕКАЮЩИЕСЯ, проверяющий, что два множества не пересекаются, т.е. у них нет общих элементов. Определите предикат НЕПЕРЕСЕКАЮЩИЕСЯ, проверяющий, что два множества не пересекаются, т.е. у них нет общих элементов. Определите функцию ПЕРЕСЕЧЕНИЕ, формирующую пересечение двух множеств, т.е. множество из их общих элементов. Определите функцию ПЕРЕСЕЧЕНИЕ, формирующую пересечение двух множеств, т.е. множество из их общих элементов. Определите функцию ОБЪЕДИНЕНИЕ, формирующую объединение двух множеств. Определите функцию ОБЪЕДИНЕНИЕ, формирующую объединение двух множеств. Определите функцию СИММЕТРИЧЕСКАЯ- РАЗНОСТЬ, формирующую множество из элементов не входящих в оба множества. Определите функцию СИММЕТРИЧЕСКАЯ- РАЗНОСТЬ, формирующую множество из элементов не входящих в оба множества.