РЕКУРСИЯ И ЦИКЛ В ПРОГРАММАХ НА ЛИСПЕ

В «чистом» функциональном программировании организация повторяющихся вычислений должна происходить лишь с помощью условных предложений и определения рекурсивных, вызывающих самих себя, функций. Рассмотрим в качестве примера функцию, просто определяемую через рекурсию, - факториал n!=1*2 * 3 *...* (n-1) * n = (n-1)! ^т n (0! = 1 по определению):

(defun ! (n) (if(= п 0) 1 (* п (! (. п 1))))) .

Имя функции - "!",ее аргументом является переменная n. Лямбда-выражение, определяющее функцию, представляет собой условную if-форму, которая в случае n=0 возвращает 1, а в противном случае вычисляет произведение n и результата вызова этой же функции ! для аргумента n-1.

Пример вызова этой функции:

(!5)

Результат: 120.

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

(DO ((nepi знач! шаг1) (пер2 знач2 шаг 2) ...)
(условие-окончания форма11 форма12 ...)

форма21 форма22 ...)

Вычисление предложения DO начинается с присваивания переменным пep1, пер2, ... начальных значений знач1, знач2, . . . соответственно; потом вычисляется условие окончания и, если оно истинно, последовательно вычисляются формы форма1i, и значение последней возвращается как результат DO-предложения. В противном случае вычисляются формы форма2i из тела предложения DO, затем значения переменных пep1, пер2, . . . изменяются на величину шага шаг1, шаг2, ... и все повторяется.

Для примера с помощью предложения DO определим функцию expt, вычисляющую n-ю степень числа х (n - целое положительное):

(defun expt (х n)

(do ((результат 1)) ; начальное значение

((= n 0 ) результат ) ; условие окончания

(setq результат (* результат х))

(setqn(^nl))))

Результат задания функции: EXPT.

Пример вызова:

(expt 2 3)

Результат: 8.

Итеративные (циклические) и рекурсивные программы теоретически одинаковы по своим вычислительным возможностям, однако свойства итеративных и рекурсивных вариантов программ могут существенно различаться. Рекурсивные программы более короткие и содержательные. Особенно полезно использовать рекурсию в тех случаях, когда решаемая задача и обрабатываемые данные по своей сути рекурсивны, например, при обработке списков, так как списки могут рекурсивно содержать подсписки, при работе с другими динамическими структурами, которые заранее не полностью известны. Рекурсивные процедуры играют важнейшую роль почти во всех программах, связанных с искусственным интеллектом.