В 2006 году, я опубликовал статью: "Уроки создания рекурсивных функций". Прошло несколько лет и я предлагаю вашему вниманию, новую версию.Все коды, прилагающиеся к учебным материалам, имеют подсветку синтаксиса, как в LISP редакторе AutoCAD.
Рекурсии в AutoLISP урок 1
Для начала хотелось бы объяснить термин: "рекурсия" — обычная функция (процедура), которая в процессе выполнения вызывает сама себя.
Применительно к Лиспу дано полное объяснение в книге С. Зуева и Н. Полещука "САПР на базе AutoCAD, Как это делается", стр. 273 — 286. Считаю, что Петр Лоскутов (один из соавторов издания "САПР на базе AutoCAD, Как это делается") очень доступно изложил принципы работы рекурсий и провел исследование целесообразности использования рекурсий. Мое личное мнение заключается в том, что функцию использовать стоит, но не ставлю перед собой задачи убедить вас. Единственная задача, которую я хочу решить: научить свободно использовать такие приемы наравне с другими. Структура рекурсивной функции: (цитата из вышеупомянутой книги)
(defun my-test-function (arg) (if <условие> (my-test-function (<некая тестовая функция> arg)) <действие при невыполненном условии> ) ;_ if ) ;_ defun
Для начала создадим простую рекурсию — аналог mapcar:
(setq lst (list 1 2 3))
Так выглядит реализация увеличения всех элементов на единицу с использованием mapcar:
(mapcar '1+ lst)
А так выглядит рекурсия:
(defun rec_1+ (lst) (if lst (cons (1+ (car lst)) (rec_1+ (cdr lst)) ) ;_ cons ) ;_ if ) ;_ defun
вызывать:
(rec_1+ lst)
Теперь разберем работу рекурсии.
(defun rec_1+ (lst) ;с первой строкой, я думаю, все понятно (if lst ;| со второй, думаю тоже, но на всякий случай поясню — здесь проверяется наличие в переменной lst каких либо данных. Если есть, то выполняем следующую строку. Если нет — возвращаем NIL |; (cons (1+ (car lst)) (rec_1+ (cdr lst))) ;| добавляем увеличенное на единицу значение первого элемента списка к результату, полученному при выполнении программы rec_1+ со списком без первого элемента |; ) ;_ if ) ;_ defun
Для наглядности разверну рекурсию со списком '(1 2 3) заменив программу на ее содержимое:
(if '(1 2 3) (cons (1+ (car '(1 2 3)) ) ;_ 1+ => 2 (if (cdr '(1 2 3)) (cons (1+ (cadr '(1 2 3)) ) ;_ 1+ => 3 (if (cddr '(1 2 3)) (cons (1+ (caddr '(1 2 3)) ) ;_ 1+ => 4 (if (cdddr '(1 2 3)) (cons (1+ (car lst)) (rec_1+ (cdr lst))) ) ;_ if => NIL ) ;_ cons => '(4) ) ;_ if => '(4) ) ;_ cons => '(3 4) ) ;_ if => '(3 4) ) ;_ cons => '(2 3 4) ) ;_ if => '(2 3 4)
теперь сделаем то же самое, но с двумя списками, опять же аналог mapcar:
(setq lst_1 (list 1 2 3) lst_2 (list 4 5 6))
(mapcar '+ lst_1 lst_2) ; => '(5 7 9)
И рекурсия
(defun rec_+ (lst_1 lst_2) (if (and lst_1 lst_2) (cons (+ (car lst_1)(car lst_2)) (rec_+ (cdr lst_1)(cdr lst_2)) ) ;_ cons ) ;_ if ) ;_ defun
Вызывать:
(rec_+ lst_1 lst_2)
Надеюсь, не трудно догадаться, как будет выглядеть функция для трех и более аргументов...
(setq lst_1 '(7 8 9) lst_2 '(4 5 6) lst_3 '(1 2 3))
(mapcar '- lst_1 lst_2 lst_3) ; => '(2 1 0)
и рекурсия
(defun rec_- (lst_1 lst_2 lst_3) (if (and lst_1 lst_2 lst_3) (cons (- (car lst_1)(car lst_2)(car lst_3)) (rec_- (cdr lst_1)(cdr lst_2)(cdr lst_3)) ) ;_ cons ) ;_ if ) ;_ defun
Вызывать:
(rec_- lst_1 lst_2 lst_3)
Аналогию с mapcar можно продолжать и продолжать. Думаю, теперь интересно рассмотреть различия, например, mapcar «умеет» подавать на вход функции только по одному первому элементу из каждого аргумента — списка, а для рекурсии не проблема обращаться к полному аргументу — списку! Возьмем простейший пример:
(setq lst '(1 2 3 4 5 6 7 8 9))
Такой список координат "точек" можно получить после Vla-Intersect-With и других функций, но для более удобного использования их необходимо преобразовать в список точек.
(defun rec_lst_3d (lst) (if lst (cons (list (car lst) (cadr lst) (caddr lst) ) ;_ list (rec_lst_3d (cdddr lst)) ) ;_ cons ) ;_ if ) ;_ defun
Вызывать:
(rec_lst_3d lst)
получаем:
'((1 2 3) (4 5 6) (7 8 9))
Старая версия сайта, доступна здесь.