Введение в программирование на Лиспе



             

Рекурсивные функции: определение и исполнение


  1. Определения могут быть рекурсивны.

Как правило рекурсивное применение функций должно быть определено в комплекте с нерекурсивными ветвями процесса. Основное предназначение условных выражений - рекурсивные определения функций.

Для примера рассмотрим функцию, выбирающую в списке самый левый атом:

Алг Левейший ( список x) арг x нач если Atom (x) то знач := x иначе знач := Левейший (Car (x)) кон

Пример 4.10. запись на алгоритмической нотации (html, txt)

Новая функция "Левейший" выбирает первый атом из любого данного.

(DEFUN Левейший (x) (COND ((ATOM x) x) (T (Левейший (CAR x))) ))

Пример 4.11. эквивалентная Лисп-программа (html, txt)

Если x является атомом, то он и является результатом, иначе функцию "Левейший" следует применить к первому элементу значения x, которое получается в результате вычисления формулы (CAR x). На составных x будет выполняться вторая ветвь специальной функции COND, выбираемая по тождественно истинному значению встроенной константы T.

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

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

Рассмотрим вычисление формы:

(APPLY (DEFUN Левейший (x) (COND ((ATOM x) x) (T (Левейший (CAR x))) ))) (QUOTE ((A . B) . C) ) )

Функция "APPLY" применяет функцию "Левейший", полученную как результат "DEFUN", к ее аргументам – константе "((A . B) . C)".

DEFUN дает имена обычным функциям, поэтому фактический параметр функции "Левейший" будет вычислен до того как начнет работать ее определение и переменная "x" получит значение "((A .


Содержание  Назад  Вперед