Лисп/Рекурсия

Рассмотрим простейший пример рекурсивного копирования списка:

(defun my-copy-list (A)
"Выдаёт копию данного линейного списка. (Аналог встроенной copy-list.)"
  (if (null A)
      A
      (cons (car A) (my-copy-list (cdr A)))))
;; >> (my-copy-list '(a b (c d))) => (A B (C D))

У рекурсивной функции две или более вычислительных «ветви», причём одна обязательно ведёт к завершению вычислений. В другой — рекурсивной — ветви (каковая в данном случае единственна) функция строит список из головного элемента (car A) и списка, который получается в результате вызова той же функции my-copy-list с аргументом (cdr A) — обезглавленным исходным списком. Так повторяется до тех пор, пока не будет истинным (null A), то есть аргумент вызываемой функции не станет пустым списком; в этом случае вычисления завершаются.

Наша my-copy-list копирует только верхний уровень списка (дерева), ведь очередной головной элемент (car A) вполне может сам быть списком, — но функция копирует его целиком, не глядя. Это не позволяет, например, использовать функции с такой структурой для поиска отдельных атомов, потому что она найдет только (C D), но не C и D по отдельности. Определим функцию my-copy-tree, копирующую список, — потенциальное дерево — рекурсивно:

(defun my-copy-tree (D)
  (cond ((null D) nil)
        ((atom D) D)
        (t (cons (my-copy-tree (car D))
                 (my-copy-tree (cdr D))))))

Здесь рекурсивный вызов проходится не только по cdr, но и по car текущего списка. По сути, вас никто не обязывает выстраивать элементы исходного списка в том же порядке: заменив (cons (new-copy-tree (car tree)) (new-copy-tree (cdr tree))) на (cons (new-copy-tree (cdr tree)) (new-copy-tree (car tree))), наша функция будет строить список в обратном порядке. Так можно было бы определить аналог встроенной reverse.

Скелеты приведенных выше функций - довольно распространенные лисповские идиомы. Например, вы можете определить функцию my-append — аналог append, объединяющую списки:

(defun new-append (list1 list2)
  (if (null list1)
      list2
      (cons (car list1)
            (new-append (cdr list1) list2))))

Ее конструкция очень напоминает new-copy-list. Таких функций можно придумать довольно много. Если вы захотите использовать их в своей программе, то можете написать функцию

>> (defun template (arg1 &optional arg2 (func #'cons))
          (if (null arg1)
              arg2
            (funcall func (car arg1) ;funcall - применение функции func к ее аргументам
                     (template (cdr arg1) arg2 func)))) => TEMPLATE

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

вызов template с нужными аргументами позволяет превратить ее в new-copy-list, append или что-то еще (например, такой же вид будет иметь функция для замены, вставки, удаления атомов в списке)

>> (template '(a b (c d))) ; вызов с одним аргументом - копия списка
<< (A B (C D))
>> (template '(a b) '(c d)) ; два аргумента - объединение списков
<< (A B C D)
;; etc

Это напоминает шаблоны в C++ (ой, что я сказал?! ведь концепция шаблонов вместе с ООП пришла в C++ именно из лиспа :-) Такой подход позволяет значительно улучшить программу, сделать ее модульной и расширяемой, это один из примеров восходящего программирования