Основы логического и функционального программирования.prn. Основы логического и функционального программирования

• Название: Основы логического и функционального программирования
• Дата: 05.01.2022
• Размер: 410 Kb.
• Имя файла: Основы логического и функционального программирования.prn.doc
• Тип: Учебное пособие; #324347
• страница: 5 из 5

Простая рекурсия

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

Функция является рекурсивной, если в ее определении содержится вызов этой же функции. Рекурсия является простой, если вызов функции встречается в некоторой ветви лишь один раз. Простой рекурсии в процедурном программировании соответствует обыкновенный цикл. Например, задача нахождения значения факториала n! сводится к нахождению значения факториала (n-1)! и умножения найденного значения на n.

Пример: нахождение значения факториала n!.

> (defun factorial (n)

(cond

;факториал 0! равен 1

((= n 0) 1)

;факториал n! равен (n-1)!*n

(t (* (factorial (- n 1)) n))))

FACTORIAL

>(factorial 3)

6

Для отладки программы можно использовать возможности трассировки. Трассировка позволяет проследить процесс нахождения решения.

Для того чтобы включить трассировку можно воспользоваться функцией trace:

Например:

> (trace factorial)

(FACTORIAL)

> (factorial 3)

Entering: FACTORIAL, Argument list: (3)

Entering: FACTORIAL, Argument list: (2)

Entering: FACTORIAL, Argument list: (1)

Entering: FACTORIAL, Argument list: (0)

Exiting: FACTORIAL, Value: 1

Exiting: FACTORIAL, Value: 1

Exiting: FACTORIAL, Value: 2

Exiting: FACTORIAL, Value: 6

6

Для отключения трассировки можно воспользоваться функцией untrace:

Например:

> (untrace factorial)

NIL

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

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

Вот несколько примеров простой рекурсии.

Возведение числа x в степень n с помощью умножения (рекурсия по аргументу):

> (defun power (x n)

(cond

;x⁰=1 (любое число в нулевой степени равно 1)

((= n 0) 1)

;xⁿ=x^(n-1)*n (значение x в степени n вычисляется возведением x в степень n-1

;и умножением результата на n)

(t (* (power x (- n 1)) x))))

> (power 2 3)

8

> (power 10 0)

1

Копирование списка (рекурсия по аргументу):

> (defun copy_list (list)

(cond

;копией пустого списка является пустой список

((null list) nil)

;копией непустого списка является список, полученный из головы и копии

;хвоста исходного списка

(t (cons (car list) (copy_list (cdr list))))))

COPY_LIST

>(copy_list ‘(1 2 3))

(1 2 3)

>(copy_list ())

NIL

Определение принадлежности элемента списку (рекурсия по значению):

> (defun member (el list)

(cond

;список просмотрен до конца, элемент не найден

((null list) nil)

;очередная голова списка равна искомому элементу, элемент найден

((equal el (car list)) t)

;если элемент не найден, продолжить его поиск в хвосте списка

(t (member el (cdr list)))))

MEMBER

> (member 2 '(1 2 3))

T

> (member 22 '(1 2 3))

NIL

Соединение двух списков (рекурсия по аргументу):

> (defun append (list1 list2)

(cond

;соединение пустого списка и непустого дает непустой список

((null list1) list2)

;соединить голову первого списка и хвост первого списка,

;соединенный со вторым списком

(t (cons (car list1) (append (cdr list1) list2)))))

APPEND

> (append '(1 2) '(3 4))

(1 2 3 4)

> (append '(1 2) ())

(1 2)

> (append () '(3 4))

(3 4)

> (append () ())

NIL

Реверс списка (рекурсия по аргументу):

> (defun reverse (list)

(cond

;реверс пустого списка дает пустой список

((null list) nil)

;соединить реверсированный хвост списка и голову списка

(t (append (reverse (cdr list)) (cons (car list) nil)))))

REVERSE

> (reverse '(one two three))

(THREE TWO ONE)

> (reverse ())

NIL

8. 
   Другие виды рекурсии
   

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

1. 
   параллельная рекурсия – тело определения функции function_1 содержит вызов некоторой функции function_2, несколько аргументов которой являются рекурсивными вызовами функции function_1.
   

(defun function_1 … (function_2 … (function_1 …) … (function_1 …) … ) … )

2. 
   взаимная рекурсия – в теле определения функции function_1 вызывается некоторая функции function_2, которая, в свою очередь, содержит вызов функции function_1.
   

(defun function_1 … (function_2 … ) … )

(defun function_2 … (function_1 … ) … )

3. 
   рекурсия более высокого порядка – в теле определения функции аргументом рекурсивного вызова является рекурсивный вызов.
   

(defun function_1 … (function_1 … (function_1 …) … ) … )

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

> (defun full_copy_list (list)

(cond

;копией пустого списка является пустой список

((null list) nil)

;копией элемента-атома является элемент-атом

((atom list) list)

;копией непустого списка является список, полученный из копии головы

;и копии хвоста исходного списка

(t (cons (full_copy_list (car list)) (full_copy_list (cdr list))))))

FULL_COPY_LIST

> (full_copy_list '(((1) 2) 3))

(((1) 2) 3)

> (full_copy_list ())

NIL

Не обойтись без параллельной рекурсии при работе c бинарными деревьями. Бинарное дерево, как и все прочие данные, представляются в Lisp’е в виде списков. Например, упорядоченное бинарное дерево



можно представить в виде списка (4 (2 (1 nil nil) (3 nil nil)) (5 nil nil)). Константы nil представляют пустые деревья. В таком представлении первый элемент списка – это узел дерева, второй элемент списка – левое поддерево и третий элемент списка – правое поддерево. Другой вариант представления дерева– (((nil 1 nil) 2 (nil 3 nil)) 4 (nil 5 nil)). В таком представлении первый элемент списка – это левое поддерево, второй элемент списка – узел дерева и третий элемент списка – правое поддерево. Можно использовать и другие варианты представления деревьев. Рассмотрим простой пример работы с бинарным деревом – обход дерева и подсчет числа узлов дерева. Для работы с элементами дерева, которые являются, по сути, элементами списка, очень удобно использовать стандартные функции Lisp’а, для получения первого, второго и третьего элементов списка – fist, second и third, соответственно.

> (defun node_counter (tree)

(cond

;число узлов пустого дерева равно 0

((null tree) 0)

;число узлов непустого дерева складывается из: одного корня,

;числа узлов левого поддерева и числа узлов правого поддерева

(t (+ 1 (node_counter (second tree)) (node_counter (third tree))))))

NODE_COUNTER

> (node_counter '(4 (2 (1 nil nil) (3 nil nil)) (5 nil nil)))

5

> (node_counter nil)

0

Пример взаимной рекурсии – реверс списка. Так как рекурсия взаимная, в примере определены две функции: reverse и rearrange. Функция rearrange рекурсивна сама по себе.

> (defun reverse (list)

(cond

((atom list) list)

(t (rearrange list nil)))))

REVERSE

> (defun rearrange (list result)

(cond

((null list) result)

(t (rearrange (cdr list) (cons (reverse (car list)) result)))))

REARRANGE

> (reverse '(((1 2 3) 4 5) 6 7))

(7 6 (5 4 (3 2 1)))

Пример рекурсии более высокого порядка – второго. Классический пример функции с рекурсией второго порядка – функция Аккермана.

Функция Аккермана определяется следующим образом:

B (0, n) = n+1

B (m, 0) = B (m-1, 0)

B (m, n) = B (m-1, B (m, n-1))

где m>=0 и n>=0.

> (defun ackerman

(cond

((= n 0) (+ n 1))

((= m 0) (ackerman (- m 1) 1))

(t (ackerman (- m 1) (ackerman m (- n 1))))))

ACKERMAN

> (ackerman 2 2)

7

> (ackerman 2 3)

9

> (ackerman 3 2)

29

Литература

1. 
   Адаменко А.Н., Кучуков А.М. Логическое программирование и Visual Prolog. – СПб.: БХВ-Петербург, 2003. – 992 С.
   
2. 
   Братко И. Программирование на языке Пролог для искусственного интеллекта. – М.: Мир, 1990. – 560 С.
   
3. 
   Ин Ц., Соломон Д. Использование Турбо-Пролога. – М.: Мир, 1993. – 608 С.
   
4. 
   Доорс Дж., Рейблейн А.Р., Вадера С. Пролог ‑ язык программирования будущего. – М.: ФиС, 1990. – 144 С.
   
5. 
   Стерлинг Л., Шапиро Э. Искусство программирования на языке Пролог. – М.: Мир, 1990. – 235 С.
   
6. 
   Клоксин У., Меллиш Д. Программирование на языке Пролог. – М.: Мир, 1987. – 336 С.
   
7. 
   Стобо Дж. Язык программирования Пролог. – М.: Мир, 1993. – 368 С.
   
8. 
   Янсон А. Турбо-Пролог в сжатом изложении. – М.: Мир, 1991. – 94 С.
   
9. 
   Малпас Дж. Реляционный язык Пролог и его применение. – М.: Наука, 1990. – 463 С.
   
10. 
    Хювёнен Э., Сеппянен Й. Мир Лиспа. ‑ М.: Мир, 1990. – 447 С.
    
11. 
    Маурер У. Введение в программирование на языке ЛИСП. – М.: Мир, 1978. – 104 С.
    
12. 
    Хендерсон П. Функциональное программирование: применение и реализация. ‑ М.: Мир, 1983. – 349 С.