Форумы 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 След.
Ответы
С чем бы сравнить (* 2.5 4.36)?
Код

(BENCHMARK
  '(
    (* 2.5 4.36)
    (* 4.36 2.5)
    (* 25 0.436)
    (* 0.436 25)
    (* 0.025 436)
    (* 436 0.025)
    (* (* 436 25) 0.001)
    (* 0.001 (* 436 25))
    (/ (* 436 25) 1000.)
    (/ 1000. (* 436 25))
   )
) ;_  BENCHMARK
Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):
    (* 25 0.436)..............1515 / 1.16 <fastest>
    (* 2.5 4.36)..............1547 / 1.13
    (* 4.36 2.5)..............1547 / 1.13
    (* 0.436 25)..............1563 / 1.12
    (* 0.025 436).............1578 / 1.11
    (* 436 0.025).............1594 / 1.1
    (/ (* 436 25) 1000.0).....1703 / 1.03
    (* 0.001 (* 436 25))......1735 / 1.01
    (* (* 436 25) 0.001)......1750 / 1
    (/ 1000.0 (* 436 25)).....1750 / 1 <slowest>
Акелла промахнулся! smile:-D
Это я о себе:
(/ (* 436 25) 1000.)
(/ 1000. (* 436 25))
слишком увлекся...
Вот исправленные данные:
Код

(BENCHMARK
  '(
    (* 2.5 4.36)
    (* 4.36 2.5)
    (* 25 0.436)
    (* 0.436 25)
    (* 0.025 436)
    (* 436 0.025)
    (* (* 436 25) 0.001)
    (* 0.001 (* 436 25))
    (/ (* 436 25) 1000.)
    (/ (* 25 436) 1000.)
   )
) ;_  BENCHMARK
Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):
    (* 4.36 2.5)..............1547 / 1.14 <fastest>
    (* 25 0.436)..............1562 / 1.13
    (* 0.025 436).............1562 / 1.13
    (* 2.5 4.36)..............1563 / 1.13
    (* 436 0.025).............1593 / 1.11
    (* 0.436 25)..............1594 / 1.11
    (* (* 436 25) 0.001)......1734 / 1.02
    (* 0.001 (* 436 25))......1735 / 1.02
    (/ (* 436 25) 1000.0).....1750 / 1.01
    (/ (* 25 436) 1000.0).....1766 / 1 <slowest>
Как бы заменить (* 2.5 4.36) на (+ ...)?
> [url=http://www.caduser.ru/forum/index.php?PAGE_NAME=read&FID=&TID=]ВСЕМ!
Считаю, что начальные сведения, для самостоятельного написания программ с использованием рекурсий, я дал за эти десять уроков! Любой, разобравшийся во всем описанном здесь коде, сможет самостоятельно написать свою рекурсию.
Хотелось бы, у вас, спросить... Нужно ли продолжать уроки в этой ветке и если нужно, то какие вопросы о рекурсиях, вы хотели бы раскрыть?
PS.
>VH (2006-05-12 16:46:50)[/url]
Хотел пообщаться с вами по почте, но письма вернулись...
Почтовый ящик корпоративный, постоянно действующий. Наверное, наши администраторы не пропускают письма, в которых не присутствует тема.
Видимо всем уже надоели эти уроки...
Пожалуй для затравки покажу вариант рекурсии без defun.
На примере уже известной вам функции.
Код

(setq lst '(1 2 3 4 5 6 7 8 9 10 11 12))
;Вариант через defun
(defun lst-3d-pt (lst)
  (if lst
    (cons (list (car lst) (cadr lst) (caddr lst)) (lst-3d-pt (cdddr lst)))
  ) ;_  if
) ;_  defun
(setq 3d-lst (lst-3d-pt lst))
;Вариант через lambda
(setq f      (lambda (x)
               (if x
                 (cons (list (car x) (cadr x) (caddr x)) (f (cdddr x)))
               ) ;_  if
             ) ;_  lambda
      3d-lst (f lst)
) ;_  setq
Прошу не счесть этот вопрос наглым после приведенной выше функции для сравнения скоростей, просто времени на эксперименты не всегда есть: будет ли быстрее функция, использующая внутри себя подфункции (defun...), если их заменить на (lambda...)?
> Kosarev (2006-05-19 09:31:03)
Если без компиляции:
Код
Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):
    (LST-3D-PT LST).....1328 / 1 <fastest>
    (F LST).............1329 / 1 <slowest>
Прошла неделя...
Повторю свой вопрос, недельной давности!
Я вижу, что эта тема очень просматриваемая (третья по количеству просмотров за всю историю раздела Программирование :: LISP).
Делаю вывод, что тема, кому то интересна. Хотелось бы услышать совет о дальнейшем развитии темы или другие предложения!
Если пожеланий не будет, значит тема достаточно раскрыта и такое количество просмотров, обусловленно пользованием этой ветки как справочным пособием, в котором более чем достаточно информации...
PS. Хотелось бы услышать любое мнение по этому вопросу - если тему можно закрывать, то я займусь приведением всех уроков к единому стилю и выложу их в готовые программы...
Евгений!
Честно говоря не знаю в каком направлении в дальнейшем нужно развивать тему, т.к. трудно давать советы по вопросу, который тут же и изучаешь, но по моему мнению тему закрывать не надо. Как классно все начиналось - вопросы, ответы, дискуссии и тишина...
Ау!!! Где же вы - мастера LISP'а??? Или современное программирование сводится только к VL-,VLA-,VLR- и VLAX-? (хотя такую тему тоже хотелось бы увидеть на форуме).
Неужели все вопросы по данной теме исчерпаны?
Ведь наверное только вы сможете помочь своими советами и знаниями изучающим LISP, и в частности - рекурсии. Не дайте потухнуть теме!!!
Особые слова благодарности автору - вы НАСТОЯЩИЙ УЧИТЕЛЬ!!!
Выложить в Готовые Программы не помешает, а относительно продолжения Вы, Евгений, должны решить сами, т.к. те кто УЧИТСЯ, просматривая тему, просто не могут определить той границы, когда она будет более-менее исчерпана, а те кто соревнуется в мастерстве - пожалуй и далее заинтересованы в возможности сравнения своих творений и Ваших. Мне кажется, что продолжение темы должно быть в виде предложения, рассмотрения и анализа оригинальных или необычных примеров использования рекурсий...
Уважаемый Евгений.
Отвечаю Вам тут, по-поводу
этого: http://thespoke.net/blogs/semka/archi...x#comments
Тут, потому что Споук дико тормозной.
Вы вообще мой пост читали?
Фраза "Может, начнешь использовать и рекурсии".
Меня повеселила изрядно, если честно.
Я-то воспринимаю Автолисп как функциональный язык, и если вы внимательно прочитаете пост целиком, вы встретите фрагмент свежего (относительно уже) кода:
Код

(defun del (x n)
   (cond
          ((null x) nil)
          ((= n 0)
                (del (cdr x)
                        (- n 1)))
          (t (append (list (car x))
                (del (cdr x) (- n 1))))))

В общем энивэй спасибо за отклик, если интересно, мы с Вадиком делаем проект http://defun.ru посвящённый функциональному программировани. Автолиспу там будет уделено немало времени.
p.s. На самом деле функциональность на рекурсиях не заканчивается (-:
> semka (2006-10-23 13:23:21)
Я, конечно, дико извиняюсь, но код бы продокументировать хоть чуть-чуть не помешало бы, я думаю - формат передаваемых данных, имена поинформативнее, примеры применения и т.п.. Для примеру сравните 2 кода:
Код
(defun conv2d (lst / res)
  (cond
    ((not lst)
     nil
     )
    (t
     (setq res (cons (list (car lst)
            (if (cadr lst)
              (cadr lst)
              0.
              ) ;_ end of if
            ) ;_ end of list
           (conv2d  (cddr lst))
           ) ;_ end of cons
      ) ;_ end of setq
     )
    ) ;_ end of cond
  res
  ) ;_ end of defun
и
Код
;|==================================================­===========================
*    Функция конвертации списка чисел в список 2-мерных точек.
*    Параметры вызова:
*   lst   список чисел
*    Примеры вызова:
(_kpblc-conv-list-to-2dpoints '(1 2 3 4 5 6)) ;-> ((1 2) (3 4) (5 6))
(_kpblc-conv-list-to-2dpoints '(1 2 3 4 5))   ;-> ((1 2) (3 4) (5 0.))
==================================================­===========================|;
(defun _kpblc-conv-list-to-2dpoints (lst / res)
  (cond
    ((not lst)
     nil
     )
    (t
     (setq res (cons (list (car lst)
            (if (cadr lst)
              (cadr lst)
              0.
              ) ;_ end of if
            ) ;_ end of list
           (_kpblc-conv-list-to-2dpoints (cddr lst))
           ) ;_ end of cons
      ) ;_ end of setq
     )
    ) ;_ end of cond
  res
  ) ;_ end of defun

Разница ощутима? А действия выполняются одни и те же...
>semka
Красота,
однако можно вместо (append (list (car список)) ...) применить (cons (car список) ...)
(или нельзя?)
Код
(defun DEL (список индекс)
(cond
  ((null список) nil)
  ((= индекс 0) (DEL (cdr список) (- индекс 1)))
  (T (cons (car список) (DEL (cdr список) (- индекс 1))))))
> VH (2006-10-23 14:11:50)
Тогда уж, нет смысла проходить весь список до конца, иначе теряется смысл в использовании рекурсии...
Например:
Код

(defun del (lst i)
  ; функция удаления элемента списка по порядковому номеру
  ; Первый аргумент список из которого нужно удалить элемент
  ; Второй пргумент порядковый номер удаляемого элемента
  ; Пример вызова:
  ; (del '(1 2 3 4 5 6 7 8 9) 5)
  (if lst
    (if (zerop i)
      (cdr lst)
      (cons (car lst) (del (cdr lst) (1- i)))
    ) ;_  if
  ) ;_  if
) ;_  defun
Ладно, ребят, чего вы накинулись, это же в своём роде сэмпловый исходник.
А по-поводу оформления кода, советую почитать вот это: http://www.norvig.com/luv-slides.ps
Таки образом оформленные скобки очень тяжело читать. Есть же стандарты оформления текста в Common Lisp.
Код

  (if lst
    (if (zerop i)
      (cdr lst)
      (cons (car lst) (del (cdr lst) (1- i)))
    ) ;_  if
  ) ;_  if
) ;_  defun

Такой код довольно трудно читать в больших проектах, которые написаны с учётом функциональности лиспа. В конце-концов не надо считать идиотами тех, кто читает ваш исходник. Они найдут, где что закрывается.
Оверкомментинг тоже зло.
>Евгений Елпанов
Это-то понятно (обеденный перерыв кончился - вот мысль и не материализовалась).
> semka (2006-10-23 15:32:12)
Я уже много раз спорил по поводу необходимости таких коментариев, теперь не спорю, а просто говорю свое мнение...
Если вам удобно читать код без коментариев - удалите их и читайте без них!
Мне очень сложно без них.
Представьте себе програмку на 10000 - 30000 строк, в которой огромное количество скобок закрываются через многие сотни строк, а некоторые, через тысячи. Такой подход, тоже имеет место быть и я им пользуюсь!
Короче, если из моих больших проектов удалить коментарии и сцепить закрывающиеся скобки, довольно часто, будет получаться, что блок закрывающих скобок займет несколько строк и посчитать их будет проблематично.
Ну. Я же не имел в виду совсем без комментариев (:
И правила закрытия скобок должны быть, но не "скобка в строке". А то лёгким движением автоформатера код на 500 строк превращается в код на 1000 (:
Вот пример кода, правда это Common Lisp, а не AL,VL.
http://semka.undesigned.ru/src/lisp/passgen.html
Скажите, там что-то сильно непонятно? (-;
> semka (2006-10-23 16:20:25)
Там все отлично понятно!
Но там очень короткий и простой код...
Посмотри мой вариант примера и поделись своими впечатлениями, насколько легко он читается.
Форматировал, специально для тебя!
Код
(defun multi-subst-fun (lst-i)
  (eval
    (list
      (function defun)
      (function multi-subst)
      '(lst)
      (list
        (function mapcar)
        (list
          (function function)
            (list
              (function lambda)
              '(a)
              (cons
                (function cond)
                (reverse
                  (cons
                    '(t a)
                    (mapcar
                      (function
                        (lambda (a)
                          (list
                            (list
                              (function equal)
                              (car a)
                              'a)
                            (cadr a))))
                      lst-i))))))
        'lst))))
;;Проверка:
(multi-subst-fun '((1 "Первый") (3 "Третий")))
(multi-subst '(1 2 3 4 5)); => ("Первый" 2 "Третий" 4 5)
(multi-subst '(1 6 4 3 7)); => ("Первый" 6 4 "Третий" 7)
Код
(defun multi-subst-fun (lst-i)
  (eval (list (function defun)
      (function multi-subst) '(lst)
        (list (function mapcar)
           (list (function function)
             (list (function lambda) '(a)
                 (cons (function cond)
        (reverse (cons '(t a) (mapcar (function (lambda (a)
          (list (list (function equal) (car a) 'a)
          (cadr a))))
          lst-i))))))
        'lst))))
   
;;Проверка:
(multi-subst-fun '((1 "Первый") (3 "Третий")))
(multi-subst '(1 2 3 4 5)); => ("Первый" 2 "Третий" 4 5)
(multi-subst '(1 6 4 3 7)); => ("Первый" 6 4 "Третий" 7)

Ня? ^__^
В общем я думаю это отдельная тема для беседы.
На самом деле правда скачайте файлик, который я рекомендовал к прочтению. Там хорошие примеры, правда.
Но я таки чертовски рад, что кто-то кроме двух сумасшедших студентов пишет на автолиспе функционально (-:
Всё-равно форматирование сбилось ):
Гадкий html.
> semka (2006-10-23 17:00:34)
Цитата
Но я таки чертовски рад, что кто-то кроме двух сумасшедших студентов пишет на автолиспе функционально (-:

Если вы начнете посещать англоязычные и не только сайты и форумы по автолиспу, вы найдете очень много интересных примеров...
> semka (2006-10-23 13:23:21)
Знаешь почему мало где увидишь в книгах рекурсии? Потому, что на их создание и чтение нужно напрягать мозги. Вот эта ветка, после её создания Евгением - стала для многих, в том числе и для меня, отличным пособием в изучении рекурсивных функций, за что ему моё искреннее СПАСИБО.
Насчёт комментариев с тобой в корне не согласен. Сразу видно ты больших проектов под заказчика не писал.
Предположим, что заказчик попросил тебя доработать код полугодовой давности. Что будешь делать? Вникать заново?
Я вообще при написании программ делаю и такие комментарии.
Пример:
; Получим из списка (list ...)
; список (list ....)
И всё сразу везде понятно.
Страницы: Пред. 1 2 3 4 5 След.
Читают тему (гостей: 2, пользователей: 0, из них скрытых: 0)