На этом шаге мы рассмотрим примеры использования рекурсии по значению и по аргументам.

В этом разделе мы рассмотрим лишь несколько примеров.

Пример 1. Функция REMOVE возвращает список, в котором удалены все вхождения ATM в список LST.

   (DEFUN REMOVE (LAMBDA (ATM LST)
      (COND ( (NULL LST) NIL)
            ( (EQ ATM (CAR LST))
                  ; Рекурсия по значению  
                  (REMOVE ATM (CDR LST)) )
            (  T  ; Рекурсия по аргументу 
                  (CONS (CAR LST)
                        (REMOVE ATM (CDR LST))) )
      )
   ))

Текст этой функции можно взять здесь.

Список LST сокращается путем удаления всех идентичных ATM в смысле EQ элементов (вторая ветвь) и копирования в результирующий список (CONS) остальных элементов (третья ветвь) до тех пор, пока условие окончания (первая ветвь) не станет истинным. Результат формируется в процессе возврата.

Замечание. Функцию REMOVE можно определить с использованием предиката EQUAL вместо EQ. С помощью такой функции можно удалять элементы, являющиеся списками!

Пример 2. Предикат MEMBERN позволяет определить вхождение списка X в список LST на любом уровне.

   (DEFUN MEMBERN (LAMBDA (X LST)
      (COND ( (NULL LST) NIL)
            (  T  (OR (COND ( (ATOM (CAR LST))
                                        (MEMBERN X (CDR LST)) )
                            (  T  (OR (EQUAL X (CAR LST))
                                      (MEMBERN X (CAR LST))) )
                      )
                      (MEMBERN X (CDR LST))
                  )
            )
      )
   ))

Текст этой функции можно взять здесь.

Пример 3. Приведенные в примере ниже функции FOOT и HEAD аналогичны стандартным лисповским функциям CAR и CDR, но предназначены для прохода по списку от конца к началу.

   (DEFUN SUMMA (LAMBDA (X LST)
   ; Подсчитать сумму мест, на которых в списке LST 
   ;           встречается элемент X                
      (COND
         ( (NULL LST) 0  )
         ( (EQ X (FOOT LST))
                  (+ (SUMMA X (HEAD LST)) (LENGTH LST)) )
         (    T   (SUMMA X (HEAD LST))                     )
      )
   ))
   ; --------------------- 
   (DEFUN FOOT (LAMBDA (LST)
      (CAR (REVERSE LST))
   ))
   ; --------------------- 
   (DEFUN HEAD (LAMBDA (LST)
      (REVERSE (CDR (REVERSE LST)))
   ))

Текст этой функции можно взять здесь.

Пример 4.

   (DEFUN REVERSE1 (LAMBDA (LST)
   ; "Обращение" списка LST на первом уровне 
      ( (NULL LST) NIL)
      ( APPEND1 (REVERSE1 (CDR LST)) (CAR LST) )
   ))
   ; -------------------------- 
   (DEFUN APPEND1 (LAMBDA (LST X)
      ( (NULL LST)
             (CONS X NIL) )  ; Создание одноэлементного списка 
      ( CONS (CAR LST) (APPEND1 (CDR LST) X) )
   ))

Текст этой функции можно взять здесь.

На следующем шаге мы рассмотрим параллельную рекурсию.

Предыдущий шаг Содержание Следующий шаг