6. Функциональное программирование Рекурсия. Различные виды рекурсии.

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

Рекурсивная процедура:

во-первых, всегда содержит, по крайней мере, одну рекурсивную ветвь и условие окончания;

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

Будем говорить о рекурсии по значению и рекурсии по аргументам.

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

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

Рассмотрим следующие формы рекурсии:

• простая рекурсия;

• параллельная рекурсия;

• взаимная рекурсия.

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

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

(defun k (x)

(cond ((null x) nil)

(t (cons (car x) (k (cdr x)))))) => k

(k '(a b c)) => (A B C)

(eq '(a b c) (k '(a b c))) => NIL

За работой этой функции можно наблюдать при помощи средств трассировки:

(TRACE имя функции) – включается трассировка функции.

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

(UNTRACE имя функции) – отключение трассировки.

(trace k) => (K)

(k '(a b c))

Entering: K, Argument list: ((A B C))

Entering: K, Argument list: ((B C))

Entering: K, Argument list: ((C))

Entering: K, Argument list: (NIL)

Exiting: K, Value: NIL

Exiting: K, Value: (C)

Exiting: K, Value: (B C)

Exiting: K, Value: (A B C)

(A B C)

Мы видим, что функция вызывается рекурсивно с хвостом списка x в качестве аргумента до тех пор, пока условие выхода из рекурсии не станет истинным и значением функции не станет NIL, который выступает вторым аргументом последнего вызова функции CONS. После этого рекурсивные вызовы будут по очереди заканчиваться и возвращаться на предыдущие уровни, и начнется формирование нового списка от конца к началу. На каждом уровне к возвращаемому с предыдущего уровня хвосту добавляется головная часть с текущего уровня.

Функция MEMBER проверяет, принадлежит ли элемент списку:

(defun member1 (x sp)

(cond ((null sp) nil)

((eql (car sp) x) sp)

(t (member1 x (cdr sp))))) => MEMBER1

(member1 'a '(c a b)) => (A B)

(member1 'd '(c a b)) => NIL

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

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

В предыдущем примере первое условие будет истиной, если список изначально пуст или непустой список в процессе рекурсивных вызовов пройден до конца и требуемый элемент не найден.

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

Функция APPEND объединяет два списка.

Функция APPEND1 – рекурсия по аргументам.

(defun append1 (x y)

(cond ((null x) y)

(t (cons (car x) (append1 (cdr x) y))))) => APPEND1

(append1 '(a b) '(c d)) => (A B C D)

Эта функция строит новый список из значений, сохраняемых на различных уровнях рекурсии. Рекурсивно откладываются вызовы функции CONS с элементами списка x до тех пор, пока он не исчерпается, после чего в качестве результата возвращается указатель на список y и отложенные вызовы, завершая свою работу, формируют результат.

Entering: APPEND1, Argument list: ((A B) (C D))

Entering: APPEND1, Argument list: ((B) (C D))

Entering: APPEND1, Argument list: (NIL (C D))

Exiting: APPEND1, Value: (C D)

Exiting: APPEND1, Value: (B C D)

Exiting: APPEND1, Value: (A B C D)

Как видно из предыдущих определений, APPEND можно использовать для получения копии списка:

> (append '(c v b) nil) => (C V B)

Функция для объединения нескольких списков:

(defun s (&rest x)

(cond ((equal x '(nil)) nil)

(t (append1 (car x) (s (cdr x))))))

>(s '(a b) '(c d) '(e f) '(g h))

(A B (C D) (E F) (G H))

REMOVE удаляет элемент из списка. Функция REMOVE1 удаляет из списка все совпадающие с данным атомом элементы и возвращает в качестве значения список из оставшихся элементов:

(defun remove1 (a l)

(cond ((null l) nil)

((eql a (car l)) (remove1 a (cdr l)))

(t (cons (car l) (remove1 a (cdr l)))))) => REMOVE1

(remove1 '1 '(2 3 1 2)) => (2 3 2)

Список сокращается при удалении всех идентичных элементов и копировании в результирующий список остальных элементов, пока список не пуст.

Предикат сравнения для REMOVE можно задать при вызове ключевым параметром :TEST

> (remove '(a b) '((a b) c d) :test 'equal)

(C D)

Заменяет все вхождения элемента:

> (SUBSTITUTE 'a 'b '(a a a))

(A A A)

(defun ss (nov star l)

(cond ((null l) nil)

((eql star (car l)) (cons nov (ss nov star (cdr l))))

(t (cons (car l) (ss nov star (cdr l))))))

Если первый элемент списка равен заменяемому, то строим новый список, заменяя этот элемент; в противном случае применяем функцию к хвосту списка.

Функция REVERSE обращает список.

Для обращения списка надо добраться до его последнего элемента и поставить его первым элементом обращенного списка. Берем первый элемент, делаем из него одноэлементный список и объединяем его с перевернутым хвостом.

(defun r (l)

(cond ((null l) nil)

(t (append (r (cdr l)) (cons (car l) nil))))) => R

> (r '(v b n m)) => (M N B V)

Для примера напишем функцию вычисления чисел Фибоначчи: (F(1)=1; F(2)=1; F(n)=F(n-1)+F(n-2) при n>2).

(DEFUN FIB (n)

(IF (> n 0)

(IF (OR (=n 1) (= n 2)) 1

(+ (FIB (- n 1)) (FIB (- n 2))))

‘ОШИБКА_ВВОДА))

>FIB 7

> 13

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

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

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

(defun rev1 (L)

(per L nil)) => REV1

(defun per (L rez)

(cond ((null L) rez)

(t (per (cdr L) (cons (car L) rez))))) => PER

(rev1 '(1 2 3 4)) => (4 3 2 1)

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

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

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

(defun F …

… (G… (F…) … (F…) …)

… )

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

Параллельной рекурсии в процедурном программировании соответствуют следующие друг за другом циклы.

Пример. Функция, обращающая список на всех уровнях, т.е. не только верхний уровень списка, но и входящие в него подсписки.

(defun obr (l)

(cond ((atom l) l)

((null (cdr l)) (cons (obr (car l)) nil))

(t (append (obr (cdr l)) (obr (cons (car l) nil)))))) => OBR

(obr '(1 2 3 4)) => (4 3 2 1)

(obr '((1 2) (1 2 3 4))) => ((4 3 2 1) (2 1))

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

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

(defun F …

… (G …) …)

(defun G…

… (F…) …)

Пример. Представим ранее определенную функцию obr в виде двух взаимно рекурсивных функций.

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

В процессе построения обращенного списка она заботится о том, чтобы возможные подсписки были обращены. Она делает это не сама, а передает эту работу функции OBR. Результат получен взаимной рекурсией. Глубина и структура рекурсии зависят от строения списка. Также функция PERESTAV рекурсивна сама по себе.

(defun obr (l)

(cond ((atom l) l)

(t (perestav l nil)))) => OBR

(defun perestav (l rez)

(cond ((null l) rez)

(t (perestav (cdr l) (cons (obr (car l)) rez))))) => PERESTAV

(obr '(1 2 (1 2 3 4)) ) => ((4 3 2 1) 2 1)

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

Пример. Сортировка списков.

Предикат РАНЬШЕ-Р проверяет, находится ли элемент А ранее элемента В, в соответствии с расположением, определенным порядком следования элементов в списке PORADOK :

(defun ranshe-p (a b poradok)

(cond ((null poradok) nil)

((eq a (car poradok)) t)

((eq b (car poradok)) nil)

(t (ranshe-p a b (cdr poradok))))) => RANSHE-P

(ranshe-p 'b 'c '(a b c d)) => T

(ranshe-p 'd 'c '(a b c d)) => NIL

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

(defun vstav (a l poradok)

(cond ((null l) (list a))

((ranshe-p a (car l) poradok) (cons a l))

(t (cons (car l) (vstav a (cdr l) poradok))))) => VSTAV

(vstav 'n '(a b c m) '(a b c d n m)) => (A B C N M)

ВСТАВЬ и РАНЬШЕ-Р образуют двухуровневую вложенную итеративную структуру.

Неупорядоченный список можно отсортировать функцией СОРТИРУЙ, которая рекурсивно ставит первый элемент списка на соответствующее место в предварительно упорядоченном хвосте списка:

(defun sortiruy (l poradok)

(cond ((null l) nil)

(t (vstav (car l)

(sortiruy (cdr l) poradok) poradok)))) => SORTIRUY

(sortiruy '(3 4 1 5 2 6) '(1 2 3 4 5 6)) => (1 2 3 4 5 6)

Теперь рекурсия функций СОРТИРУЙ, ВСТАВЬ и РАНЬШЕ-Р образует уже трехуровневую вложенную повторяющуюся структуру.

Рекурсия более высокого порядка. Рекурсия называется рекурсией более высокого порядка, если аргументом рекурсивного вызова является рекурсивный вызов:

(defun F

… (F… (F…) …)

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

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

Также усложняются и вычисления и могут занимать много времени.

Поэтому обычно в практическом программировании рекурсия более высокого порядка не используется.