Функция является рекурсивной, если в её определении содержится вызов самой этой функции. Мы будем говорить о рекурсии по значению, когда вызов является выражением, определяющим результат функции. Если же в качестве результата функции возвращается значение некоторой другой функции и рекурсивный вызов участвует в вычислении аргументов этой функции, то будем говорить о рекурсии по аргументам. Аргументом рекурсивного вызова может быть вновь рекурсивный вызов, и таких вызовов может быть много.
Рассмотрим сначала случай простой рекурсии. Мы будем говорить, что рекурсия простая, если вызов функции встречается в некоторой ветви лишь один раз. Простой рекурсии в процедурном программировании соответствует обыкновенный цикл.
Определим методы copy, которая строит копию списка. Копия списка логически идентична первоначальному списку:
>(nil defmethod copy () this) ; достижение конца списка
(lambda nil this)
>('cons defmethod copy ()
(nil cons (this first) ((this rest) copy))) ; рекурсия
(lambda nil (nil cons (this first) ((this rest) copy)))
>('l set '(a b c))
(a b c)
>(l copy)
(a b c) ; логическая копия
>(nil eq l (l copy))
false ; физически различные списки
Этот метод является рекурсивным по аргументу, поскольку рекурсивный вызов стоит на месте аргумента функции cons. Метод проходит список, копируя и укорачивая в процессе этого список по направлении rest. Ветвь с окончанием рекурсии достигается тем, что метод copy виртуальный и при достижении конца списка возвращает nil. После этого рекурсивные вызовы будут по очереди заканчиваться и возвращаться на предыдущие уровни, и с помощью функции cons в рекурсивной ветке определения начнёт формироваться от конца к началу новый список. На каждом уровне к возвращаемому с предыдущего уровня хвосту (this rest) добавляется головная часть с текущего уровня (this first).
Обратите внимание, что функция копирует не элементы списка (т.е. в направлении first, или в глубину), а лишь составляющие список ячейки верхнего уровня (т.е. список копируется в направлении rest, или в ширину). Чтобы копировать список на любую глубину нужно добавить лишь ещё один рекурсивный вызов.
Копирование списков представляет собой одно из основных действий над списками, и поэтому соответствующая функция входит в число встроенных методов.
Рекурсию можно использовать для определения как предикатов, так и функций. В качестве второго применения простой рекурсии возьмём встроенный предикат Лиспа contain. С его помощью можно проверить, принадлежит ли некоторый элемент данному списку или нет.
>(nil defmethod contain (a) false) ; список пуст ?
(lambda (a) false)
>('cons defmethod contain (a)
(nil if ((this first) = a)
this ; a найден ?
((this rest) contain a))) ; a - в хвосте ?
(lambda (a) (nil if ((this first) = a) this ((this rest) contain a)))
>('(a b c d) contain 'b)
(b c d)
>('(a b c d) contain 'e)
false
В процессе вычислений возникает три ситуации:
Если список пуст либо a в него не входит, то функция возвращает значение false. В противном случае она возвращает в качестве своего значения ту часть списка, в которой искомое a является первым элементом. Это отличное от false и nil выражение соответствует логическому значению "истина".
В определении предиката contain первоначальная задача разбита на две подзадачи. Первая сводится к простым условиям окончания. Вторая решает такую же задачу, но на шаг более короткую. Её решение можно рекурсивно свести к функции, решающей первоначальную задачу.
Вычисление предиката contain выглядит так:
>('(a b c d) contain 'c)
| this | a | результат | |
| (a b c d) | c | вызов уровня 1 | |
| (b c d) | c | вызов уровня 2 | |
| (c d) | c | вызов уровня 3 | |
| (c d) | c | (c d) | значение уровня 3 |
| (b c d) | c | (c d) | значение уровня 2 |
| (a b c d) | c | (c d) | значение уровня 1 |
На первых двух уровнях рекурсии вычисления осуществляются по второй, рекурсивной ветви. В рекурсивном вызове аргументом является c, так как искомый элемент на каждом шаге один и тот же. Объектом берётся хвост списка текущего уровня (this rest).
На третьем уровне значением предиката ((this first) = a) становится c, поэтому на этом уровне значением всего вызова станет значение соответствующего выражения дающего результат this=(c d). Это значение возвращается на предыдущий уровень, где оно будет значением вызова contain в рекурсивной ветви и, таким образом, станет значением всего вызова на втором уровне. Далее это значение возвращается далее на уровень и, в конце концов, выводится пользователю.
В процессе спуска по ходу рекурсии на более низкие уровни значение параметра a не меняется, в то время как значение this меняется при переходе на следующий уровень. Значения предыдущего уровня сохраняются, поскольку связи переменных ассоциируются с уровнем. Значения предыдущих уровней скрыты до тех пор, пока на них не вернётся управление, после этого старые связи вновь становятся активными. В приведённом примере после возврата на предыдущие уровни эти связи не используются. Обратите внимание, что связи параметра a на различных уровнях физически различны, хотя значение остаётся тем же самым.
Отсутствие проверки, ошибочное условие или неверный их порядок могут привести к бесконечной рекурсии. Это произошло бы, например, если в предикате contain значение объекта не укорачивалось на каждом шагу рекурсии формой (this rest). То же самое случилось бы, если рекурсивная ветвь находилась в условном предложении перед условием окончания. Поэтому существенно, чтобы каждый шаг рекурсии приближал вычисления к условию окончания.
На практике рекурсивные вычисления не могут оказаться бесконечными, поскольку каждый рекурсивный вызов требует некоторого количества памяти, а общий объём памяти ограничен. При простой рекурсии память заполняется быстро, но в более сложных случаях вычисления могут оказаться практически бесконечными, другими словами, до исчерпания памяти будет бесполезно потрачено много машинного времени.
Рассмотрим встроенную функцию +, объединяющую два списка в один новый список. Функция +, подобно функции copy, строит новый список из значений, сохраняемых на различных уровнях рекурсии:
>(nil defmethod + (x) x)
(lambda (x) x)
>('cons defmethod + (x)
(nil cons (this first) ((this rest) + x)))
(lambda (x) (nil cons (this first) ((this rest) + x)))
Приведём пример:
>('(с л и) + '(я н и е))
(с л и я н и е)
>('(a b) + nil)
(a b)
>('(a b nil) + '(nil))
(a b nil nil)
Идея работы функции состоит в том, что рекурсивно откладываются вызовы функции cons с элементами списка до тех пор, пока он не исчерпается, после чего в качестве результата возвращается указатель на список x и отложенные вызовы, завершая свою работу, формируют результат:
>('(a b) + '(c d))
| this | x | результат |
| (a b) | (c d) | |
| (b) | (c d) | |
| nil | (c d) | (c d) |
| (b) | (c d) | (b c d) |
| (a b) | (c d) | (a b c d) |
Обратите внимание, что список строится от конца первого списка к началу, поскольку вычислявшиеся в процессе рекурсии вызовы функции cons начинают вычисляться из глубины наружу по мере того, как осуществляется процесс возврата из рекурсии.
Как видно из данного определения, + копирует список, являющийся объектом. Эту функцию можно использовать в виде (список + nil), когда необходимо сделать копию верхнего уровня списка. Но всё-таки лучше использовать форму (список copy).
Все предыдущие определения функций содержали лишь один рекурсивный вызов. Рассмотрим в качестве следующего примера содержащую две рекурсивные ветви встроенную функцию remove, которая удаляет из списка все совпадающие с данным атомом (используя метод =) элементы и возвращает в качестве значения список из всех оставшихся элементов. Remove можно определить через базисные функции и её саму следующим образом:
>(nil defmethod remove)
(lambda)
>('cons defmethod remove (x)
(nil if (x = (this first))
((this rest) remove x) ; убрали элемент
(nil cons (this first) ; создание нового списка
((this rest) remove x))))
(lambda (x) (nil if (x = (this first)) ((this rest) remove x) (nil cons (this first) ((this rest) remove x))))
>('(с л о н) remove 'л)
(с о н)
>('(a (b c)) remove 'b) ; элементы проверяются лишь в направлении rest
(a (b c))
>('((a b) (c d)) remove '(a b))
((c d)) ; сравнение =
Список сокращается путём удаления всех идентичных x в смысле = элементов и копирования в список остальных элементов до тех пор, пока не достигнется конец списка. Результат формируется в процессе возврата аналогично функции +.
Функция substitute, заменяющая все вхождения данного элемента старый в списке на элемент новый, работает подобно функции remove.
>(nil defmethod substitute)
(lambda)
>('cons defmethod substitute (старый новый)
(nil cons
(nil if ((this first) = старый)
новый ; замена головы
(this first)) ; голова не меняется
((this rest) substitute старый новый))) ; обработка хвоста
(lambda (старый новый) (nil cons (nil if ((this first) = старый) новый (this first)) ((this rest) substitute старый новый)))
>('(a x x a) substitute 'x 'b)
(a b b a)
Обратите внимание, что и здесь замена производится лишь на самом верхнем уровне списка, т.е. рекурсия осуществляется только по хвостовой части списка (в направлении rest). Как и при копировании списка процедуру замены элемента можно обобщить так, чтобы список обрабатывался и в глубину, для этого в случае, когда голова списка является списком, нужно осуществить рекурсию и по головной части.
В приведённых примерах мы просматривали список в соответствии с направлением указателей в списочных ячейках слева направо. Но что делать, если нужно обрабатывать список справа налево, т.е. от конца к началу?
Рассмотрим для примера функцию reverse, которая также является встроенной функцией. Reverse изменяет порядок элементов в списке (на верхнем уровне) на обратный.
Для переворачивания списка мы должны добраться до его последнего элемента и поставить его первым элементом обращённого списка. Хотя нам непосредственно конец списка не доступен, можно, используя +, описать необходимые действия. Идея определения состоит в следующем: берём первый элемент списка (this first), делаем из него с помощью вызова (nil list (this first)) одноэлементный список и объединяем его функцией + с перевёрнутым хвостом. Хвост списка сначала обращается рекурсивным вызовом ((this rest) reverse).
>(nil defmethod reverse)
(lambda)
>('cons defmethod reverse ()
(((this rest) reverse) + (nil list (this first))))
(lambda nil (((this rest) reverse) + (nil list (this first))))
>('(a b c) reverse)
(c b a)
>('((a b) (c d)) reverse)
((c d) (a b)) ; переворачивает лишь первый уровень
Добраться до последнего элемента списка можно, лишь пройдя всю образующую список цепочку слева направо. В функции reverse список будет проходить до конца и по пути подходящие элементы списка откладываются в аргументы незавершённых вызовов. Построение обращённого списка в порядке, противоположном следованию элементов исходного списка может начатся лишь после завершения рекурсии. Результат будет сформирован, когда исчерпается стек рекурсивных вызовов.
Список является несимметричной структурой данных, которая просто будет проходить слева направо. Во многих случаях для решения задачи более естественны вычисления, производимые справа налево. Например, то же переворачивание списка было бы гораздо проще осуществить, если бы был возможен непосредственный доступ к последнему элементу списка. Такое противоречие между структурой данных и процессом решения задачи приводит к трудностям программирования и может служить причиной неэффективности.
В процедурных языках программирования существует возможность использования вспомогательных переменных, в которых можно сохранять промежуточные результаты. Например, обращение списка можно осуществить простым переносом элементов списка друг за другом в список, используя функцию cons:
>(nil defmethod reverse)
(lambda)
>('cons defmethod reverse ()
(nil let ((остаток this)
результат)
(nil do-while
('результат set (nil cons (остаток first) результат))
('остаток set (остаток rest)))
результат))
(lambda nil (nil let ((остаток this) результат) (nil do-while ('результат set (nil cons (остаток first) результат)) ('остаток set (остаток rest))) результат))
В функциональном программировании переменные таким образом не используются. Но соответствующий механизм можно легко осуществить, используя вспомогательную функцию, у которой нужные вспомогательные переменные являются параметрами. Тогда для функции reverse мы получим такое определение:
>(nil defmethod reverse)
(lambda)
>('cons defmethod reverse ()
(this перенос nil))
(lambda nil (this перенос nil))
>(nil defmethod перенос (результат)
результат)
(lambda (результат) результат)
>('cons defmethod перенос (результат)
((this rest) перенос (nil cons (this first) результат)))
(lambda (результат) ((this rest) перенос (nil cons (this first) результат)))
Вспомогательная функция перенос рекурсивна по значению, так как результирующим выражением её тела является непосредственно рекурсивный вызов. С помощью этой функции элементы переносятся таким образом, что на каждом шаге рекурсии очередной элемент переходит из объекта this в аргумент результат. Обращённый список строится элемент за элементом функцией cons в аргументе результат так же, как и в итеративном варианте. Вычисления производятся по списку слева направо и соответствуют итеративным вычислениям.