В определении функции (или чаще в определениях вызывающих друг друга функций) рекурсия может принимать различные формы. Ранее мы рассмотрели простую рекурсию, когда одиночный рекурсивный вызов функции встречается в одной или нескольких ветвях. В этой главе мы продолжим изучение различных форм рекурсии, в том числе:
параллельную рекурсию, когда тело определения функции f содержит вызов некоторой функции g, несколько аргументов которой являются рекурсивными вызовами функции f:
(… defmethod f …
(… g … (… f …) … (… f …) …) …)
взаимную рекурсию, когда в определении функции f вызывается некоторая функция g, которая в свою очередь содержит вызов функции f:
(… defmethod f …
(… g …) …)
(… defmethod g …
(… f …) …)
рекурсию более высокого порядка, когда аргументом рекурсивного вызова является рекурсивный вызов:
(… defmethod f …
(… f … (… f …) …) …)
Рекурсию называют параллельной, если она встречается одновременно в нескольких аргументах функции.
Рассмотрим в качестве примера копирование списочной структуры на всех уровнях. Ранее уже был представлен пример функции, копирующей список в направлении rest на верхнем уровне: функция copy строила копию верхнего уровня списка. На возможные подсписки не обращалось внимания, и они не копировались, а брались как и атомы в том виде, как они есть (т.е. как указатель). Если нужно скопировать список целиком как в направлении rest, так и в направлении first, то рекурсия должна распространяться и на подсписки. Таким образом, мы получим обобщение функции copy как copy-tree. Слово tree в названии функции возникло в связи с тем, что в определении функции список трактуется как соответствующее точечной паре бинарное дерево, у которого левое поддерево соответствует голове списка, а правое поддерево - хвосту:
| дерево → nil | ; пустое дерево |
| дерево → атом | ; лист дерева |
| дерево → ( дерево . дерево ) | ; точечная пара - дерево |
>(nil defmethod copy-tree () this)
(lambda nil this)
>('cons defmethod copy-tree ()
(nil cons
((this first) copy-tree) ; копия головы
((this rest) copy-tree))) ; копия хвоста
(lambda nil (nil cons ((this first) copy-tree) ((this rest) copy-tree)))
Функция copy-tree отличается от copy тем, что рекурсия применяется как к голове, так и к хвосту списка. Поскольку рекурсивные вызовы представляют собой два аргумента вызова одной функции (cons), то мы имеем дело с параллельной рекурсией. Заметим, что параллельность является временной, так как вычисление ветвей запускается одновременно.
Таким же образом рекурсией по голове и хвосту списка можно проверить логическую идентичность двух списков на основе сравнения структуры и атомов, составляющих список. Определим далее уже известный нам предикат =:
>('cons defmethod = (x)
(nil if (nil consp x)
(nil if
(nil and
((this first) = (x first)) ; идентичные головы
((this rest) = (x rest))) ; идентичные хвосты
this)))
(lambda (x) (nil if (nil consp x) (nil if (nil and ((this first) = (x first)) ((this rest) = (x rest))) this)))
Приведём ещё один пример параллельной рекурсии. Рассмотрим функцию обращение. Эта функция предназначена для обращения порядка следования элементов списка и его подсписков независимо от их места и глубины вложенности. Ранее определённая нами простой рекурсией функция reverse оборачивала лишь верхний уровень списка:
>(nil defmethod обращение () this)
(lambda nil this)
>('cons defmethod обращение ()
(nil let ((голова (nil list ((this first) обращение))))
(nil if (nil atom (this rest))
голова
(((this rest) обращение) + голова))))
(lambda nil (nil let ((голова (nil list ((this first) обращение)))) (nil if (nil atom (this rest)) голова (((this rest) обращение) + голова))))
>('(a (b (c (d)))) обращение)
((((d) c) b) a)
>('палиндром set '((а) (р о з а) (у п а л а) (н а) (л а п у) (а з о р а)))
((а) (р о з а) (у п а л а) (н а) (л а п у) (а з о р а))
>(палиндром обращение)
((а р о з а) (у п а л) (а н) (а л а п у) (а з о р) (а))
Функция обращение обращает голову списка, формирует из него список и присоединяет к нему спереди обращённый хвост.
Применяя параллельную рекурсию, можно списочную структуру (двоичного дерева) ужать в одноуровневый список, т.е. удалить все вложенные скобки. Сделать это при помощи структурных преобразований довольно сложно, но с помощью рекурсии это осуществляется просто:
>(nil defmethod в-один-уровень ()
(nil if (nil not (nil = this))
(nil list this)))
(lambda nil (nil if (nil not (nil = this)) (nil list this)))
>('cons defmethod в-один-уровень ()
(((this first) в-один-уровень) + ; сначала голову
((this rest) в-один-уровень))) ; потом хвост
(lambda nil (((this first) в-один-уровень) + ((this rest) в-один-уровень)))
>('(a (((((b))))) (c d) e) в-один-уровень)
(a b c d e)
>((палиндром в-один-уровень) = ((палиндром обращение) в-один-уровень))
(а р о з а у п а л а н а л а п у а з о р а)
Функция в-один-уровень объединяет (функцией +) ужатую в один уровень голову списка и ужатый хвост. Если голова списка является атомом, то из него формируется список, поскольку аргументы функции + должны быть списками.
Рекурсия является взаимной между двумя или более функциями, если они вызывают друг друга. Для примера можно представить ранее определённую нами функцию обращения или зеркального отражения в виде двух взаимно рекурсивных функций следующим образом:
>(nil defmethod обращение () this)
(lambda nil this)
>('cons defmethod обращение ()
(this переставь nil))
(lambda nil (this переставь nil))
>(nil defmethod переставь (результат) результат)
(lambda (результат) результат)
>('cons defmethod переставь (результат)
((this rest) переставь
(nil cons ((this first) обращение) результат)))
(lambda (результат) ((this rest) переставь (nil cons ((this first) обращение) результат)))
Функция переставь используется в качестве вспомогательной функции с дополнительными параметрами таким же образом, как и ранее вспомогательная функция перенос использовалась совместно с функцией reverse. В процессе построения обращённого списка она заботится и о том, чтобы возможные подсписки были обращены. Она делает это не сама, а передаёт эту работу специализирующейся на этом функции обращение. Результат получен взаимной рекурсией. Глубина и структура рекурсии зависят от строения списка. Кроме участия во взаимной рекурсии функция переставь рекурсивна и сама по себе.
Соответствующие вложенным циклам процедурного программирования многократные повторения в функциональном программировании осуществляются обычно с помощью двух и более функций, каждая из которых соответствует простому циклу. Вызов такой рекурсивной функции используется в определении другой функции в качестве аргумента её рекурсивного вызова. Естественно, аргументом рекурсивного вызова в определении функции может быть другой рекурсивный вызов. Это уже будет рекурсией более высокого порядка.
Рассмотрим сначала программирование вложенных циклов с помощью двух различных функций, а затем уже с помощью рекурсии более высокого порядка. Вложенный цикл можно выразить и с помощью циклических предложений (for, while и др.) или специализированных повторяющих функций. Такие явные способы мы сейчас использовать не будем.
Мы начнём рассматривать программирование вложенных циклов с сортировки списков. Определим сначала функцию вставь, которая добавляет элемент a в упорядоченный список так, чтобы сохранилась упорядоченность, если порядок любых двух элементов задаётся предикатом <:
>('cons defmethod вставь (a l)
(nil cond
((nil = l)
(nil list a))
((this < a (l first))
(nil cons a l))
(true
(nil cons (l first) (this вставь a (l rest))))))
(lambda (a l) (nil cond ((nil = l) (nil list a)) ((this < a (l first)) (nil cons a l)) (true (nil cons (l first) (this вставь a (l rest))))))
Предикат < проверяет, находится ли элемент a ранее элемента b, в соответствии с расположением определённым порядком следования элементов в списке:
>('cons defmethod < (a b)
(nil cond
((a = (this first)) ; a раньше
true)
((b = (this first)) ; b раньше
false)
(true
((this rest) < a b))))
(lambda (a b) (nil cond ((a = (this first)) true) ((b = (this first)) false) (true ((this rest) < a b))))
>('(a b c d e) < 'b 'e)
true
>('(a b c d e) вставь 'b '(a c d))
(a b c d)
вставь и < образуют двухуровневую вложенную итеративную структуру.
Неупорядоченный список можно отсортировать функцией сортируй, которая рекурсивно ставит первый элемент списка на соответствующее место в предварительно упорядоченном хвосте списка:
>('cons defmethod сортируй (l)
(nil if (nil consp l)
(this вставь (l first)
(this сортируй (l rest)))))
(lambda (l) (nil if (nil consp l) (this вставь (l first) (this сортируй (l rest)))))
>('(a b c d e) сортируй '(b a c))
(a b c)
Теперь рекурсия функций сортируй, вставь и < образует уже трёхуровневую вложенную повторяющуюся структуру.
Приведём ещё функцию +, напоминающую своей структурой функцию сортируй и позволяющую элементы списка новый вставить в упорядоченный список l. Функция + повторяет процедуру вставки для каждого элемента списка новый:
>('cons defmethod + (l новый)
(nil if (nil = новый)
l
(this вставь (новый first)
(this + l (новый rest)))))
(lambda (l новый) (nil if (nil = новый) l (this вставь (новый first) (this + l (новый rest)))))
>('(a b c d e) + '(a b d) '(b c))
(a b b c d)
Эту рекурсивную по аргументам функцию можно записать и в виде функции, рекурсивной по значению:
('cons defmethod + (l новый)
(nil if (nil = новый)
l
(this + (this вставь (новый first) l)
(новый rest))))
Выразительные возможности рекурсии уже видны из приведённых выше содержательных и занимающих мало места определений. Определения функций в-один-уровень и обращение в итеративном варианте не поместились бы на один лист бумаги (попробуйте!). С помощью рекурсии легко работать с динамическими, заранее не определёнными целиком, но достаточно регулярными структурами, такими как списки произвольной длины и глубины вложения.
Используя всё более мощные виды рекурсии, можно записывать относительно лаконичными средствами и более сложные вычисления. Одновременно с этим, поскольку определения довольно абстрактны, растёт сложность программирования и понимания программы.
Рассмотрим теперь программирование вложенных циклов в такой форме, при которой в определении функции рекурсивный вызов является аргументом вызова этой же самой функции. В такой рекурсии можно выделить различные порядки в соответствии с тем, на каком уровне рекурсии находится вызов. Такую форму рекурсии будем называть рекурсией более высокого порядка. Функции, которые мы до сих пор определяли, были функциями с рекурсией нулевого порядка.
В качестве классического примера рекурсии более высокого порядка часто приводится известная из теории рекурсивных функций функция Аккермана, пользующаяся славой "плохой" функции (немного отличается от классики для удобства):
>('number defmethod аккерман (x y)
(nil cond
((y <= 1)
x)
((this <= 0)
(x + y))
((this = 1)
(x * y))
((this = 2)
(x ^ y))
(true
((this - 1) аккерман x (this аккерман x (y - 1))))))
(lambda (x y) (nil cond ((y <= 1) x) ((this <= 0) (x + y)) ((this = 1) (x * y)) ((this = 2) (x ^ y)) (true ((this - 1) аккерман x (this аккерман x (y - 1))))))
>(0 аккерман 3 3)
6
>(1 аккерман 3 3)
9
>(2 аккерман 3 3)
27
>(3 аккерман 3 3)
7625597484987
Функция Аккермана является функцией с рекурсией первого порядка. Её вычисление довольно сложно, и время вычисления растёт лавинообразно уже при малых значениях аргумента.
В качестве другого примера функции с рекурсией первого порядка приведём функцию в-один-уровень, расставляющую элементы списка на одном уровне, которую мы ранее определили, используя параллельную рекурсию:
>(nil defmethod в-один-уровень (результат)
(nil if (nil = this)
результат
(nil cons this результат)))
(lambda (результат) (nil if (nil = this) результат) (nil cons this результат))
>('cons defmethod в-один-уровень (результат)
((this first) в-один-уровень ((this rest) в-один-уровень результат)))
(lambda (результат) ((this first) в-один-уровень ((this rest) в-один-уровень результат)))
В этом определении работа функции непосредственно сведена к базовым функциям и рекурсии первого порядка, где аргументом рекурсивного вызова является один рекурсивный вызов. В более раннем определении дополнительно к базовым функциям и рекурсии нулевого порядка мы использовали функцию +. Применяя рекурсию более высокого порядка вычисления можно представить более абстрактно и с помощью более короткого определения, однако представить себе работу такой функции довольно сложно.
Функция в-один-уровень работает следующим образом. Результат строится в списке результат. Если this - атом, то его можно непосредственно добавить в начало списка результат. Если this - список и его первый элемент является атомом, то всё сводится к предыдущему состоянию на следующем уровне рекурсии, но в такой ситуации, когда список результат содержит уже вытянутый в один уровень оставшийся хвост.
В том случае, когда и голова списка является списком, то его сначала приводят к одному уровню. Это делается с помощью рекурсивных вызовов, погружающихся в головную ветвь до тех пор, пока там не встретится атом, который можно добавить в начало вытянутой к этому моменту в один уровень структуры. Встречающиеся таким образом атомы добавляются по одному к вытянутому хвосту. На каждом уровне при исчерпании списка на предыдущий уровень выдаётся набранный к данному моменту результат.
Следующее определение функции reverse, использующей лишь базовые функции и рекурсию, является примером ещё более глубокого уровня рекурсии:
(nil defmethod reverse ()
this)
('cons defmethod reverse ()
(nil if (nil consp (this rest))
(nil cons
(((this rest) reverse) first)
((nil cons
(this first)
((((this rest) reverse) rest) reverse))
reverse))
this))
В определении использована рекурсия второго порядка. Вычисления, представленные этим определением, понять труднее, чем прежние. Сложная рекурсия усложняет и вычисления. В этом случае невозможно вновь воспользоваться полученными ранее результатами, поэтому одни и те же результаты приходится вычислять снова и снова. Обращение списка из пяти элементов функцией reverse требует 149 вызовов. Десятиэлементный список требует уже 74409 вызовов и заметное время для вычисления! Как правило, многократных вычислений можно избежать, разбив определение на несколько частей и используя подходящие параметры для сохранения и передачи промежуточных результатов.
Обычно в практическом программировании формы рекурсии более высокого порядка не используются, но у них по крайней мере есть своё теоретическое и методологическое значение.