На этом шаге мы введем понятие взаимной рекурсии и проиллюстрируем ее использование.
Если две или более функций вызывают друг друга, то рекурсия называется взаимной. К сожалению, нам удалось подобрать лишь один содержательный пример взаимной рекурсии!
Пример. Функция, позволяющая установить, нечетно ли число минусов в заданном списке LST, содержащем только атомы + и -. В [1, с.149] утверждается, что в данном примере нельзя исключить одну из функций путем подстановки.
(DEFUN ISPOS (LAMBDA (LST)
(COND ( (NULL LST) NIL )
( (AND (NULL (CDR LST)) (EQ (CAR LST) -)) T )
( (EQ (CAR LST) -) (ISNEG (CDR LST)) )
( (EQ (CAR LST) +) (ISPOS (CDR LST)) )
)
))
;------------------------
(DEFUN ISNEG (LAMBDA (LST)
(COND ( (NULL LST) NIL )
( (AND (NULL (CDR LST)) (EQ (CAR LST) +)) T )
( (EQ (CAR LST) -) (ISPOS (CDR LST)) )
( (EQ (CAR LST) +) (ISNEG (CDR LST)) )
)
))
Замечание. О программировании вложенных циклов. Соответствующие вложенным циклам императивного программирования многократные повторения в функциональном программировании осуществляются обычно с помощью двух или более функций, каждая из которых соответствует простому циклу. Вызов такой рекурсивной функции используется в определении другой функции в качестве аргумента ее рекурсивного вызова.
(1)Бауэр Ф.Л., Гооз Г. Информатика. Вводный курс: В 2-х ч. Ч.1. пер. с нем. - М.: Мир, 1990. - 336 с.; Ч.2. пер. с нем. - М.: Мир, 1990. - 423 с.
На следующем шаге мы поговорим о рекурсии высших порядков.
