Тема: Уроки создания рекурсивных функций
Решил потихоньку делиться опытом создания рекурсий, к сожалению, сразу сделать большую статью не могу, но, если тема будет интересна, буду потихоньку выкладывать
функции с максимально возможным объяснением. Наверное, это будет выглядеть как уроки, а может и дискуссия, но в любом случае, единственная задача, которую я хочу решить, это научить вас спокойно создавать и использовать такие функции на равнее с другими.
Для начала хотелось бы объяснить термин "рекурсия" это обычная функция (процедура), которая в процессе выполнения вызывает сама себя.
Применительно к Лиспу, некоторое объяснение есть в книге
С.Зуева и Н. Полещука "САПР на базе AutoCAD. Как это делается"
на страницах 273 - 286
Петр Лоскутов очень доступно изложил принципы работы рекурсий и сделал некоторое расследование - стоит ли их использовать и зачем. Мое личное мнение - СТОИТ, но убеждать не буду.
Структура рекурсивной функции:
(скопировано из вышеупомянутой книги)
(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-IntersectWith и других функций, но для Лиспа их нужно преобразовать в список точек.
(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))