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

Рекурсия - одна из основ лиспа, в сочетании со списками она хорошо ложится на концепцию функционального программирования. Это очень мощный и элегантный формализм, при помощи рекурсии вы можете легко и кратко описать то, над чем бы бились, используя традиционный итеративный подход.

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

>> (defun new-copy-list (list)
          (if (null list)
              list
            (cons (car list)
                  (new-copy-list (cdr list))))) => NEW-COPY-LIST
>> (new-copy-list '(a b (c d))) => (A B (C D))

Функция, которую мы обозвали new-copy-list, чтобы отличать не переопределять встроенную copy-lisp, создает физическую копию списка. На этом примере видно, что у рекурсивной функции как миминум две ветви, причем одна обязательно ведет к завершению вычислений. В каждой ветви рекурсии функция строит список из головного элемента (car list) и списка, который получается в результате вызова той же функции new-copy-list с аргументом (cdr list) - хвостом исходного списка. Что получается в результате такого "внутреннего" вызова - догадайтесь :-) Так продолжается до тех пор, пока не будет истинным (null list), то есть аргумент вызываемой функции не станет пустым списком. В этом случае вычисления завершаются. Это самый простой пример рекурсии, к тому же он работает со списками и хорошо подходит для описания рекурсии в лиспе. Так же можно было бы привести рекурсивные функции для вычисления факториала, чисел фибоначчи etc, но их вы найдете в любом пособии по теории рекурсии и даже в книжках типа "математика для домохозяек и носорогов".

new-copy-list копирует только верхний уровень списка, подсписки он рассматривает не как списки, а как атомы. Это не позмоляет, например, использовать функции с такой структурой для поиска отдельных атомов, потому что она найдет только (C D), но не C и D. Поэтому определим функцию new-copy-tree, которая рекурсивно копирует список как дерево (дерево - еще одна трактовка структуры лисповых списков).

>>(defun new-copy-tree (tree)
         (cond ((null tree) nil)
               ((atom tree) tree)
               (t (cons (new-copy-tree (car tree))
                        (new-copy-tree (cdr tree)))))) => NEW-COPY-TREE

Здесь происходит рекурсивное копирование не только по cdr, но и по car списка. По сути, вас никто не обязывает выстраивать элементы исходного списка в том же порядке. Надеюсь, вы уже поняли.

заменив (cons (new-copy-tree (car tree)) (new-copy-tree (cdr tree)))
на     (cons (new-copy-tree (cdr tree)) (new-copy-tree (car tree)))

наша функция будет строить список в обратном порядке. Мы получили функцию new-reverse, аналог встроенной reverse. Так вы можете производить различные махинации со списками, например, выстраивать все атомы в списке в один ряд, то есть "убрать скобочки", делать разного рода сортировки. Как всегда, здесь все ограничено вашей фантазией.

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

>> (defun new-append (list1 list2)
          (if (null list1)
              list2
            (cons (car list1)
                  (new-append (cdr list1) list2)))) => NEW-APPEND

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

>> (defun template (arg1 &optional arg2 (func #'cons)) ; #' - говорим интерпретатору, что следующий за ним аргумент - функционал (функция с заранее                                                 ; неизвестными аргументами. Интерпретатор не вычисляет значение функционала, "посаженного за решетку",                                               ; а применяет к нему нужные аргументы (funcall) по нашей просьбе
          (if (null arg1)
              arg2
            (funcall func (car arg1) ;funcall - применение функции func к ее аргументам
                     (template (cdr arg1) arg2 func)))) => TEMPLATE

вызов 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++ именно из лиспа :-) Такой подход позволяет значительно улучшить программу, сделать ее модульной и расширяемой, это один из примеров восходящего программирования