elpanov.com » Обучение » Рекурсии урок 1



В 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))

Старая версия сайта, доступна здесь.