Рекурсия

(defun member(lst a)
(if null(lst)
NIL
(or (equal (car lst a)) (member (cdr lst) a))
)
)

(defun длина (список)
  (if (null список) 0 (+ 1 (длина (cdr список)))))
 
==> ДЛИНА
(trace длина)
 
==> ДЛИНА
(длина '(q w e r t y))
Вход в функцию длина Аргументы: (Q W E R T Y)
  Вход в функцию длина Аргументы: (W E R T Y)
    Вход в функцию длина Аргументы: (E R T Y)
      Вход в функцию длина Аргументы: (R T Y)
        Вход в функцию длина Аргументы: (T Y)
          Вход в функцию длина Аргументы: (Y)
            Вход в функцию длина Аргументы: NIL
            Возврат из функции длина Результат: 0
          Возврат из функции длина Результат: 1
        Возврат из функции длина Результат: 2
      Возврат из функции длина Результат: 3
    Возврат из функции длина Результат: 4
  Возврат из функции длина Результат: 5
Возврат из функции длина Результат: 6
 
==> 6

Рекурсия
Рекурсия является одним из основных способов организации вычислений, связанных с обработкой списков. С учетом того, что «Lisp» – это «list processor», можно считать, что рекурсия один из важнейших способов организации вычислений в Common Lisp (и наиважнейший чистых функциональных языках).
Существуют разные способы классификации организации рекурсии, которые, надо признать, являются достаточно условными, но позволяют лучше понять природу рекурсивных вычислений и освоить технологию создания рекурсивных функций.
Можно выделить следующие признаки классификации:
 по количеству рекурсивных вызовов и их характеру;
 по способу организации рекурсивных вычислений;
 по характеру вычислительного процесса.
По количеству рекурсивных вызовов и их характеру выделяют следующие виды рекурсии.
1. Простая рекурсия. Тело рекурсивной функции f содержит один рекурсивный вызов функции f.
(defun f(…)( … (f …) … ).
2. Параллельная рекурсия. При параллельной рекурсии тело определения функции f содержит вызов некоторой функции g, несколько аргументов, которой является рекурсивными вызовами функции f.
(defun f(…)( … (g … (f …) (f …) … ) … )).
3. Взаимная (косвенная) рекурсия. При взаимной рекурсии тело определения функции f содержит вызов некоторой другой функции g, которая в свою очередь содержит вызов функции f.
(defun f(…)( … (f …) … ),
(defun f(…)( … (f …) … ).
4. Рекурсия высокого порядка. Рекурсия более высокого порядка возникает тогда, когда тело определения функции f содержит рекурсивный вызов функции f, аргументом которого является рекурсивный вызов f:
(defun f(…) … (f … (f …) … ) … ).
По способу организации рекурсивных вычислений можно выделить следующие виды рекурсии.
1. С одной (несколькими) терминальными ветвями и одним рекурсивным вызовом. Две (и более) терминальные ветви необходимы тогда, когда, например, возможны два (и более) принципиально отличающихся варианта решения. Если же заранее известна однозначность решения, можно обойтись и одной терминальной ветвью. Шаблон такой обобщенной рекурсивной функции приведен ниже.
(defun function(x)
   (cond (end-test-1 end-value-1)
          …
         (end-test-n end-value-n)
         (T (function reduced-x))
   )
)
Ниже приведены примеры рекурсивных функций с одной и двумя терминальными ветвями соответственно.
Пример 18. Рекурсивная функция find-first-atom осуществляет поиск первого атомарного элемента. Если считать, что атом будет всегда найден, то можно обойтись одной терминальной ветвью.
(defun find-first-atom(x)
   (cond ((atom (car x)) (car x))
         (t (find-first-atom (cdr x)))
   )
)
Пример 19. Рекурсивная функция anyoddp осуществляет поиск первого нечетного числа. Так как возможны два результата поиска, то необходимы две терминальные ветви.
(defun anyoddp(x)
   (cond ((null x) nil)
         ((oddp (сar x)) t)
         (t (anyoddp (cdr x)))
   )
)
2. Пополняющая рекурсия или рекурсия с отложенными вычислениями. Если предыдущий способ организации рекурсии позволяет просто последовательно обрабатывать некоторые данные, постепенно сокращая их объем, то в ряде случаев необходимо получить результат как объединение текущих действий и результата работы рекурсии над «уменьшенными» данными. Для случая одной терминальной ветви, хотя их может быть и больше, шаблон рекурсивной функции может выглядеть так:
(defun function (X)
   (cond (end-test end-value)
         (T (aug-fun   aug-val
                       (function reduced-x)
             )
         )
   )
)
Пример 20. Пример функции с отложенными вычислениями, высчитывающей сумму арифметического ряда от 1 до заданного n:
(defun sum(n)
   (cond ((= n 1) 1)
         (t (+ n (sum (- n 1))))
   )
)
При обработке списков очень часто в качестве накапливающей функции используется функция cons, конструирующая списки.
Пример 21. Функция – «генератор смеха»:
(defun laugh(n)
   (cond ((zerop n) nil)
         (t (cons “ha” (laugh (- n 1))))
   )
)
Очевидно, что рекурсивная функция может иметь не один, а несколько аргументов. Другим обобщением рассматриваемого вида рекурсии является рекурсия, в которой накопление происходит по условию. Шаблон такой функции может быть следующим:
(defun function (x)
   (cond (end-test end-value)
         (aug-test (aug-fun aug-val
                           (function reduced-x)
         )
         (T (function reduced-x))
   )
)
Как видно из листинга, такая рекурсия является комбинацией «простой» рекурсии с одной терминальной ветвью и накопительной рекурсии.
Пример 22. Функция, вычленяющая из списка символы:
(defun extract-symbols(x)
   (cond ((null x) nil)
         ((symbolp (car x))
             (cons (car x)
                   (extract-symbols (cdr x))
             )
         )
         (t (extract-symbols (cdr x)))
   )
)
Использование рекурсии с накоплением имеет один существенный недостаток – выполняющая среда должна поддерживать необходимую вложенность вызовов и хранить стеки. В тоже время, если рекурсивный вызов функции является «последним действием», и конечный результат работы всей функции определяется только им, то можно не сохранять стеки предыдущих рекурсивных вызовов. Такую рекурсию принято называть хвостовой рекурсией. Таким образом, выполняющая среда может оптимизировать вычисления хвостовой рекурсии и преобразовать ее в циклические вычисления, которые, как правило, гораздо эффективнее выполняются на современных аппаратных платформах. В Common Lisp задачу построения хвостовой рекурсии можно решать с помощью введения в набор аргументов функции дополнительных аргументов, которые и будут накапливать результат. Но при этом следует помнить, что реализации функции будет усложняться, а сама функция становиться семантически менее доступной (можно сравнить реализации функций в примерах 22 и 23).
Пример 23. Функция, решающая ту же задачу, что и в примере 22, но для организации внутренней функции, которая имеет дополнительный параметр, используется специальный оператор labels. Таким образом удается с одной стороны реализовать хвостовую рекурсию, а с другой – оставить количество аргументов целевой функции соответствующим ее назначению.
(defun extract-symbols(x) (labels 
  ((inner(out in) (cond 
     ((null in) out) 
     ((symbolp (car in)) 
      (inner (append out (list (car in))) (cdr in)))
     (t (inner out (cdr in)))  
   )))
   (inner nil x)
   )
)
3. CAR/CDR рекурсия. При обработке многоуровневых списков часто возникает задача полного обхода списка на всех уровнях. В этом случае на помощь приходит так называемая CAR/CDR рекурсия или рекурсия по дереву. Ее принцип легко понять, если принять во внимание тот факт, внутренняя реализация списков основана на списочных ячейках и, фактически, многоуровневые списки являются бинарными деревьями. Термин «CAR/CDR рекурсия» считается традиционным именно в контексте программирования на языке Lisp и его диалектах. По сути, такая рекурсия является комбинацией параллельной рекурсии и рекурсии с накоплением
(defun func (X)
   (cond (end-test-1 end-value-1)
         (end-test-2 end-value-2)
         (T (combiner (func (CAR X))
                      (func (CDR X))
            )
         )
   )
)
Пример 22. Функция, осуществляющая поиск числа в  многоуровневом списке:
(defun find-number (x)
   (cond ((numberp x) x)
         ((atom x) nil)
         (t (or (find-number (car x))
                (find-number (cdr x)))
         )
   )
)
Другим примером функции, использующей CAR/CDR рекурсию, является функция, представленная в примере 23.
Пример 23. Функция, вычленяющая символы из многоуровневого списка:
(defun extract-symbols (x)
   (cond ((null x) nil)
         ((symbolp (car x)) (cons (car x)
                            (extract-symbols (cdr x))
             )
         )
         ((listp (car x))
             (cons (extract-symbols (car x))
                   (extract-symbols (cdr x))
             )
         )
         (t (extract-symbols (cdr x)))
   )
)
В заключение разговора о рекурсии можно привести пример рекурсивных функций, первая из которых осуществляет переворот списка (пример 24), а вторая – вспомогательная – реализует добавление элемента в конец списка (пример 25).
Пример 24.
(defun rev(ls) (cond ((null (cdr ls)) ls) 
            (t  (add (rev (cdr ls)) (car ls)))
    )
)
Пример 25.
(defun add(a b)(cond ((null a) (cons b nil))
                     (t (cons (car a) (add (cdr a) b)))
     )
)
По характеру вычислительного процесса, рекурсивные вычисления могут быть итерационными (обычная хвостовая рекурсия, простая рекурсия), рекурсивными (параллельная рекурсия), каскадными (рекурсия высокого порядка).
Функции высокого порядка
Рассмотренные способы построения рекурсивных функций позволяют строить достаточно сложные функции, обладающие необходимой функциональностью. С другой стороны, оказывается, что эти функции достаточно типичны и по своей структуре соответствуют некоторым шаблонам. Рассмотрим реализацию двух функций: первая формирует список из первых элементов подсписков, являющихся элементами полученного в качестве аргумента двухуровневого списка (пример 26), вторая – инкрементирует значения всех элементов (чисел) одноуровневого списка (пример 27).
Пример 26.
(defun 1st(x)
   (cond (x (cons (car (car x))(1st (cdr x)))))
)
Пример 27.
(defun inc(x)
   (cond (x (cons (1+  (car x)) (inc (cdr x)))))
)
Очевидно, что эти функции отличаются только способом накопления результатов, поэтому потенциально можно объединить реализацию этих функций в одну, которая в качестве аргументов будет получать список и функциональный объект – функцию или лексическое замыкание. Функцию, которая в качестве аргумента получает функциональный объект, называют функционалом. Функцию, которая возвращает функциональный объект и/или получает функциональный объект в качестве аргумента называют функцией высокого порядка [6].
Специальный оператор function блокирует вычисления, образуя так называемое лексическое замыкание. Лексическое замыкание – это определение функции (лямбда-выражение) и контекст определения функции. Если блокируемая функция не содержит свободных переменных, то функциональная блокировка не отличается от обычной, выполняемой с помощью функции quote. Для выполнения функциональной блокировки можно использовать синоним #’. Вызвать функциональный объект (заблокированную функцию или замыкание) можно с помощью, так называемых, применяющих функционалов funcall и apply (приложение А).
Пример 28.
(funcall #’exp 0) => 1.0  ; попытки вызвать
; (eval exp 0) или (eval #’exp 0) ошибочны
(apply #’(lambda(x)(* x 2)) 2) => 4
Пример 29. Функция x+1 строит функцию-генератор последовательности целых чисел.
(defun x+1()(let ((x 1))
      #’(lambda()(setq x (+ x 1))))) => X+1
(setq x (x+1)) => ;связывание с x замыкания X+1
#<interpreted closure (LAMBDA NIL (SETQ X (+ X 1)))>
(setq y (x+1)) => ;связывание с y замыкания X+1
#<interpreted closure (LAMBDA NIL (SETQ X (+ X 1)))>
(funcall x) => 2 ;вызов функции
(funcall x) => 3 ;еще один вызов функции
(funcall y) => 2 ;а связи этой функции – другие!
Из примера 29 следует, что в замыкании сохраняются связи с локальным контекстом и, фактически, экземпляры замыканий можно рассматривать как объекты в терминах объектно-ориентированного подхода.
С учетом рассмотренных возможностей языка Common Lisp можно вернуться к примерам 27 и 28. Предложенное ранее обобщение этих функций и его применение показаны в примере 30.
Пример 30. Простой отображающий функционал.
(defun map-el(x f)
  (cond (x (cons (funcall f (car x))
                 (map-el (cdr x) f)))
  )
) => map-el
(map-el ‘(1 2 3) #’1+) => (2 3 4)
(map-el ‘(-1 -3 4 -5) #’abs) => (1 3 4 5)
Как следует из последнего примера, при построении функции map-el использовались: композиция функций, рекурсия и возможность использовать функции как объекты первого класса, т. е. ключевые возможности функционального подхода. Среди стандартных функций Common Lisp существует большое количество функционалов: группа отображающих функционалов (map, mapcar, maplist и др.), функционалы, которые получают в качестве параметра функцию-предикат (sort, remove, remove-if, subst, subst-if и др.), но это не лишает разработчика определять свои собственные функционалы.
Построенный функционал является примером функций высших порядков – функций, которые получают в качестве аргумента функцию и/или возвращают новую функцию. Можно показать, что не только передача аргументов-функций, но и возвращение функции как результата может играть большую роль в построении программ. Эффективность и элегантность функционального подхода можно показать на примере задачи построения распознавателя простого контекстно-свободного языка (этот пример рассматривается в [2, 5], однако в [5] он не снабжен примерами реализации на Common Lisp, а в [2] допущено много опечаток). Контекстно-свободным является язык, синтаксис которого может быть описан множеством правил, обычно называемых продукциями. В данном случае пусть язык задан следующими правилами:
S ::= BA | AB | BAB,  A ::= a | aA, B ::= b | bB.
В данной грамматике терминальными символами являются a и b. Таким образом, следующие цепочки символов будут принадлежать грамматике языка:
ba, ab, bab, bbba, bbaabb, baaabbb,
а приведенные ниже – нет:
aa, bb, aaa, bbb, abbaabb, baaabbba.
Можно считать, что распознаваемые строки представляются списками элементов a и b. Пусть определены функции одного аргумента is-a и is-b, которые возвращают значение T тогда, когда переданный им аргумент является списком и содержит один допустимый символ:
(defun is-a(x) (if (eq (car x) 'a) (null (cdr x))))
(defun is-b(x) (if (eq (car x) 'b) (null (cdr x))))
Для решения задачи выбранным способом потребуется определить несколько вспомогательных функций. Первой из таких функций будет функция, результатом работы которой является предикат, возвращающий значение T, если хотя бы один аргументов p или q имеют такое значение.
(defun is-alt(p q)
  #'(lambda (x) (or (funcall p x) (funcall q x)))
)
Следующая функция более сложная, она должна генерировать предикат, способный определять, можно ли разделить список x на две части так, чтобы первая удовлетворяла p, а вторая – q.
(defun is-chain(p q)
  #'(lambda (x)
    (cond 
    ((null x) (and (funcall p nil) (funcall q nil)))
    ((and (funcall p nil) (funcall q x)) t)
    (t (funcall (is-chain
                   #'(lambda(y)
                      (funcall p (cons (car x) y)))q
                 )     
                 (cdr x)
               )
            )
        )
    )
)
Используя эту функцию можно строить гораздо более мощные предикаты: ниже приведены два предиката, построенные на основе is-chain и способные распознавать цепочки одинаковых символов a и b соответственно.
(defun is-a-gr(x)
  (funcall (is-alt #'is-a 
                  (is-chain #'is-a #'is-a-gr)) x)
)
(defun is-b-gr(x)
  (funcall (is-alt #'is-b 
                  (is-chain #'is-b #'is-b-gr)) x)
)
Эти рекурсивные функции позволяют определять функции-распознаватели слов, в соответствии с их грамматикой. Причем определение функции при этом становится очень близко по форме правилам, задающим грамматику языка. Например, функция, распознающая цепочку из двух символов a и b, может быть реализована так
(defun is-ab(x)(funcall (is-chain #'is-a #'is-b) x))
Реализация функции, распознающей цепочки, принадлежащие языку с описанной ранее грамматикой, будет более сложной, но, тем не менее, остается достаточно прозрачной
(defun is-syllable(x)
  (funcall 
     (is-alt 
        (is-chain #'is-b-gr #'is-a-gr)
        (is-alt 
            (is-chain #'is-a-gr #'is-b-gr)
            (is-chain #'is-b-gr 
                      (is-chain #'is-a-gr #'is-b-gr)
            )
         )
      )
     x 
  )
)
Функция, распознающая цепочки вида (b a) и (b b).
(defun is-simple(x) 
  (funcall 
     (is-chain #'is-b-gr (is-alt #'is-b-gr #'is-a-gr)) 
     x
  )
)