2.2.19 Рекурсивные функции
Если в теле функции содержится хотя бы одно прямое или косвенное обращение к самой себе, то такая функция называется рекурсивной. Такое обращение может быть неявным, т.е. обращение происходит к другой функции, которая содержит обращение к первой. Большинство встроенных функций используют рекурсию. ЛИСП допускает использование рекурсивных функций без всяких ограничений, в чем и заключается сила языка.
Принцип построения таких функций обычно сводится к следующему:
Обрабатывается 1-й элемент списка.
Рекурсивный вызов определяемой функции, которой в качестве аргумента передается “хвост” списка.
Проверяется условие, не стал ли “хвост” списка пустым списком, если это произошло, то происходит передача значений по цепочке рекурсивных вызовов.
Определим функцию, которая будет определять принадлежность атома некоторому списку
(MEMB X Y),
где X- атом,
Y- список.
Текст программы:
(DEFUN MEMB(X Y)
(COND
((EQ Y NIL) NIL)
((EQ X (CAR Y)) T)
(T (MEMB X (CDR Y)))
)
)
Здесь вначале выполняется проверка: является ли список Y пустым. Если да, то результат NIL. Это условие является также условием выхода из цикла, когда перебрали все элементы списка и не нашли в нем атома. Далее, если X является первым элементом списка Y, то результат Т. Если ни одно из условий не выполнилось, то отбросив из списка Y первый (проверенный) элемент, опять обращаемся к функции MEMB с целью выяснения, а не содержится ли искомый атом в хвосте списка.
Пример использования функции MEMB
(MEMB ‘A ‘(B C A D))
-
о
бращение
к функции MEMB
A T
(B
C
A
D) 
A T - диаграмма работы функции MEMB
(C A D)
A T
(A D)
Т.о. анализируются простейшие частные условия, и если ни один из них не дает ответа, то следует прямое или косвенное обращение к той же функции для дальнейшего анализа. Но структура этих аргументов при повторном обращении становится чуточку проще. Так мы добираемся до простой ситуации, предусмотренной начальными проверками.
Эта функция работает, если внутри списка Y нет подсписков. Если необходимо, чтобы такая функция находила один список внутри другого, то следует ее переопределить. Для этого определим сначала функцию EQUAL, которая могла бы сравнивать списки. Отметим, что такая функция является встроенной для многих реализаций языка ЛИСП. Здесь мы это деляем в учебных целях.
(DEFUN EQUAL (X Y)
(COND
((ATOM X)(EQ X Y))
((ATOM Y) NIL)
((EQUAL(CAR X)(CAR Y))(EQUAL(CDR X)(CDR Y)))
(T NIL)
)
)
Программа выполняет следующие действия:
1.Если X- атом, то требуемое сравнение можно выполнить с помощью EQ;
2.Если Y- атом, (а X- уже не атом) то результат NIL.
3.Сравниваются головы списков, если они равны, то сравниваются их хвосты и если они равны, то результат Т.
4.Иначе ответ NIL.
Теперь с помощью EQUAL определим необходимую функцию MEMBER, работающую аналогично МЕМВ, но позволяющую обнаруживать наличие в списке элементов любого вида:
(DEFUN MEMBER (X Y)
(COND
((NULL Y) NIL)
((EQUAL X (CAR Y)) T)
(T (MEMBER X (CDR Y)))
)
)
Функции EQUAL и MEMBER весьма употребительны и, поэтому, существуют как встроенные во многих реализациях ЛИСПа.