Рекурсивные функции: определение и исполнение
8) Определения могут быть рекурсивными.
На практике такие определения обычно имеют глобальные имена, задаваемы с помощью функции DEFUN, о которой еще будет речь в конце этой лекции. Сейчас теоретически можно ограничиться конструктором локальных функций LABEL, которую мы вводим здесь для учебных целей (в системе GNU Clisp его нет, но для него проще определение интерпретатора, которое будем строить в следующей лекции).
Как правило, рекурсивные вызовы функций должны быть заданы в комплекте с нерекурсивными ветвями процесса. Основное применение условных выражений — рекурсивные определения функций.
(LABEL премьер ; имя локальной функции (LAMBDA (x) ; определение функции (COND ((ATOM x) x) (T (премьер (CAR x))) ) ) )
Пример 2.3.
Новая функция "премьер" выбирает первый атом из любого данного. Если x является атомом, то он является результатом, иначе функцию "премьер" следует применить к первому элементу значения x, которое получается в результате вычисления формулы (CAR x). На составных x будет выполняться вторая ветвь, выбираемая по тождественно истинному значению встроенной константы T.
Определение функции "премьер" рекурсивно. Эта функция действительно работает в терминах самой себя. Важно, что для любого S-выражения существует некоторое число применений функции CAR, после которого из этого S-выражения выделится какой-нибудь атом, следовательно, процесс вычисления функции всегда определен, детерминирован и завершится за конечное число шагов. Можно сказать, что для определенности рекурсивной функции следует формулировать условие ее завершения.
Введенные обозначения достаточны, чтобы проследить за формированием значений и преобразованием форм в процессе исполнения функциональных программ. Рассмотрим вычисление формы:
((LABEL премьер (LAMBDA (x) (COND ((ATOM x) x) (T (премьер (CAR x))) ) ) ) ; объявлена локальная функция "премьер" (QUOTE ((A . B) . C) ) ; дан аргумент локальной функции ) ; завершено выражение с локальной функцией
