Форумы caduser.ru

 
Поиск  Пользователи  Правила 
Закрыть
Логин:
Пароль:
Забыли свой пароль?
Регистрация
Войти  
   RSS
Уроки создания рекурсивных функций
Решил потихоньку делиться опытом создания рекурсий, к сожалению, сразу сделать большую статью не могу, но, если тема будет интересна, буду потихоньку выкладывать
функции с максимально возможным объяснением. Наверное, это будет выглядеть как уроки, а может и дискуссия, но в любом случае, единственная задача, которую я хочу решить, это научить вас спокойно создавать и использовать такие функции на равнее с другими.
Для начала хотелось бы объяснить термин "рекурсия" это обычная функция (процедура), которая в процессе выполнения вызывает сама себя.
Применительно к Лиспу, некоторое объяснение есть в книге
С.Зуева и Н. Полещука "САПР на базе 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))  
Страницы: Пред. 1 2 3 4 5
Ответы
Мне нужно написать рекурсивную функцию x1x2-y
> евгения (2008-09-12 13:32:17)
Это утверждение или вопрос?
> евгения (2008-09-12 13:32:17)
Пишите, Женя, пишите smile:)
нет мне нужно написать,но я не знаю как это сделать.мне нужна помощь
> евгения (2008-09-13 10:19:15)
Если вам необходима помощь форума, для написания программы - создайте новую тему, в разделе программирования на лиспе и спрашивайте помощи...
Кстати, на этом форуме обсуждается автолисп под автокад.
> [Re:] евгения (2008-09-13 10:19:15)
Во-первых внимательно прочитайте предупреждение администратора написанное выше.
Во-вторых более четко сформулируйте вопрос - лично я ничего не понял...
Страницы: Пред. 1 2 3 4 5
Читают тему (гостей: 3, пользователей: 0, из них скрытых: 0)