На этом шаге мы введем понятие параллельной рекурсии и проиллюстрируем ее использование.
Рекурсию называют параллельной, если она встречается одновременно в нескольких аргументах функции.
"Вот два правила, которыми можно руководствоваться, решая вопрос о целесообразности применения рекурсии:
- Если задачу можно решить итеративно, то пользуйтесь итерацией.
- Если рекурсивный вариант процедуры содержит два обращения к собственному наименованию, то он может оказаться полезным." [1, с.29].
Пример 1. Функция, вычисляющая количество атомов в заданном списке LST на всех уровнях:
(DEFUN COUNT (LAMBDA (LST)
(COND ( (NULL LST) 0 )
( (ATOM LST) 1 )
( T (+ (COUNT (CAR LST))
(COUNT (CDR LST))) )
)
))
Отметим, что если применять эту функцию к списку списков, то элементы NIL, которые заключают каждый список, будут также учитываться!
Пример 2. Определение количества отличных от NIL атомов в заданном многоуровневом списке LST.
(DEFUN COUNTATOMS (LAMBDA (LST)
(COND ( (NULL LST) 0 )
( (ATOM LST) 1 )
( T (+ (COUNTATOMS (CAR LST))
(COUNTATOMS (CDR LST))) )
)
))
Пример 3. Функция, вычисляющая "глубину" списка. Фраза "глубина" списка является специальным случаем понятия уровня скобок. Чтобы найти глубину списка для некоторого атома, мы подсчитываем число левых и число правых скобок до этого атома и из первого вычитаем второе. Так, в ((1 6) 7 ((8 4) 3)) глубина списка для атома 8 равна трем.
(DEFUN DEPTH (LAMBDA (X)
(COND ( (ATOM X) 1 )
( T (MAX (+ 1 (DEPTH (CAR X)))
(DEPTH (CDR X))) )
)
))
; --------------------
(DEFUN MAX (LAMBDA (X Y)
(COND ( (> X Y) X )
( T Y )
)
))
Пример 4. Функция COPY возвращает копию своего аргумента.
(DEFUN COPY (LAMBDA (EXPN)
(COND ( (ATOM EXPN) EXPN )
( T (CONS (COPY (CAR EXPN))
(COPY (CDR EXPN))) )
)
))
Пример 5. Найти сумму элементов многоуровневого числового списка.
(DEFUN ADD (LAMBDA (L)
(COND ( (NULL L) 0 )
( (ATOM (CAR L)) (+ (CAR L) (ADD (CDR L))))
( T (+ (ADD (CAR L))
(ADD (CDR L))) )
)
))
Пример 6. Предикат MEMBER3 устанавливает вхождение элемента X в многоуровневый список LST (в случае успеха возвращает остаток списка).
(DEFUN MEMBER3 (LAMBDA (X LST)
(COND ( (NULL LST) NIL)
( (COND ( (ATOM (CAR LST))
(COND ( (EQ X (CAR LST)) LST )
( T (MEMBER3 X (CDR LST)) )) )
( T (MEMBER3 X (CAR LST)) )
)
)
( T (MEMBER3 X (CDR LST)) )
)
))
Пример 7. Рассмотрим функцию, которая предназначена для обращения порядка следования элементов списка L и его подсписков независимо от их места и глубины вложенности.
Функция SUPERREVERSE обращает голову списка, формирует из него список и присоединяет к нему спереди обращенный хвост.
(DEFUN SUPERREVERSE (LAMBDA (L)
( (ATOM L) L )
( (NULL (CDR L)) (CONS (SUPERREVERSE (CAR L)) NIL) )
( APPEND (SUPERREVERSE (CDR L))
(SUPERREVERSE (CONS (CAR L) NIL)) )
))
; -----------------------
(DEFUN APPEND (LAMBDA (X Y)
; Функция APPEND возвращает список, состоящий из
; элементов списка X, добавленных к списку Y
(COND ( (NULL X) Y )
( T (CONS (CAR X) (APPEND (CDR X) Y)) )
)
))
Пример 8. Списочную структуру "ужать" в одноуровневый список, т.е. удалить все вложенные скобки.
(DEFUN ONE-RANGE (LAMBDA (LST)
( (NULL LST) NIL )
( (ATOM LST) (CONS (CAR LST) NIL) )
( APPEND (ONE-RANGE (CAR LST)) (ONE-RANGE (CDR LST)) )
))
; -----------------------
(DEFUN APPEND (LAMBDA (X Y)
; Функция APPEND возвращает список, состоящий из
; элементов списка X, добавленных к списку Y
(COND ( (NULL X) Y )
( T (CONS (CAR X) (APPEND (CDR X) Y)) )
)
))
Функция ONE-RANGE объединяет (функцией APPEND) "ужатую" в один уровень голову списка и "ужатый" хвост. Если голова списка является атомом, то из него формируется список, поскольку аргументы функции APPEND должны быть списками.
Пример 9. Моделирование предиката EQUAL с помощью предиката EQ.
(DEFUN EQUAL1 (LAMBDA (L M)
(COND ( (NULL L) (NULL M) )
( (ATOM L) (AND (ATOM M) (EQ L M)) )
( (ATOM M) NIL )
( T (AND (EQUAL1 (CAR L) (CAR M))
(EQUAL1 (CDR L) (CDR M))) )
)
))
Пример 10. Построение предиката LISTP, который возвращает значение NIL, если заданное выражение является атомом, отличным от NIL, или выражением, которое может быть записано только в точечных обозначениях. В противном случае заданное выражение является списком, который можно записать, не прибегая к точечным обозначениям ни на одном из уровней, и предикат возвращает значение T.
(DEFUN LISTP (LAMBDA (X)
(COND ( (NULL X) T )
( (ATOM X) NIL )
( (OR (ATOM (CAR X)) (LISTP (CAR X)))
(LISTP (CDR X)) )
( T NIL )
)
))
Тестовые примеры:
$ (LISTP '((A B) (B . C) C))
NIL
$ (LISTP '((A . (B C)) (B . (C A))))
T
Пример 11. Лучше всего рекурсивные методы оправданы в задачах, в которых встречается формальная и прежде всего естественная рекурсия в структурах и процессах.
Реализуем классическую восточную игру "Ханойские башни". Игра состоит в следующем. Используются три вертикальные стержня А, В и С и совокупность N круглых дисков разной величины с отверстием. В начальном состоянии диски нанизаны по порядку в соответствии со своими размерами на стержень А.
Целью является перенесение всех дисков на стержень В. Однако, диски переносятся не в произвольном порядке, при переносе нужно выполнять следующие правила:
- За один раз можно перенести только один диск.
- Больший по размеру диск нельзя положить на меньший.
Третий стержень можно использовать как вспомогательный (промежуточный). Если он свободен или там лежит больший диск, то на него можно переложить очередной диск на то время, пока переносится ниже лежащий диск. В этой идее и содержится решение игры.
Алгоритм задачи "Ханойские башни":
(DEFUN HANOI (LAMBDA (VYSOTA)
(PERENOS A B C VYSOTA) (QUOTE Готово!)
))
; -------------------------------------
(DEFUN PERENOS (LAMBDA (IZ W VSPOMOGAT N)
( (EQ N 1) (PRIN1 IZ) (PRIN1 " --> ") (PRINT W) )
( (PERENOS IZ VSPOMOGAT W (- N 1))
(PRIN1 IZ) (PRIN1 " --> ") (PRINT W)
(PERENOS VSPOMOGAT W IZ (- N 1))
)
))
Тестовый пример:
$ (HANOI 3)
А --> В
А --> С
В --> С
А --> В
С --> А
С --> В
А --> В
Готово!
Задачи для башен, состоящих из одного или двух дисков, решаются просто. Задача для трех дисков требует уже больше переносов.
Можно ли указать нерекурсивное решение задачи о Ханойской башне? Ответ положителен. Хотя его обоснование значительно сложнее, чем рекурсивное решение.
Прямое решение нашли П.Бьюнеман и Л.Леви. Алгоритм последовательно выполняет следующие действия [2, с.64-65].
- Перенести наименьший диск с того стержня, на котором он находится в данный момент, на стержень, следующий в порядке движения часовой стрелки.
- Перенести любой диск, кроме наименьшего.
(1)Фостер Дж. Обработка списков. - М.: Мир, 1974. - 72 с.
(2)Анисимов А.В. Информатика. Творчество. Рекурсия. - Киев: Наук.думка, 1988. - 224 с.
На следующем шаге мы рассмотрим взаимную рекурсию.
