Форумы 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 След.
Ответы
Ребят, вы вообще мои сообщения читаете?
Я где-то писал, что не надо ставить комментарии?
У вас экстрасенсорные способности хромают, по поводу проектов под заказчика, кстати.
Я писал только то, что оформление скобочек, которое принято автокад-автоформаттером это изврат в высшей степени.
Комментарии писать надо, они хорошие очень.
> semka (2006-10-25 09:26:51)
Я еще раз повторю, если между открывающей и закрывающей скобкой несколько тысяч строк, то быстро просмотреть такой код не получится, но очень помогает стандартное форматирование с пояснением (имеется в виду стандартное пояснение от автоформата), какое действие заканчивается на этой скобке!
Короче! Если открывающая и закрывающая скобки умещаются на экране, то можно форматировать как угодно. Если при стандартном форматировании обе скобки не умещаются на экране, а при вашем варианте умещаются, думаю, ваше форматирование лучше. Если между открывающими и закрывающими скобками умещается несколько экранов, то стандартное форматирование очень помогает, не смотря на увеличение количества строк!
PS. Если хочешь, могу выслать скриншот с экрана, у меня экран 1200х1600 (портретный режим) и уверен, что все сразу станет понятно...
Например, представь себе цикл FOREACH внутри которого еще несколько таких циклов по несколько сотен строк и куча мелких циклов - пойди разберись, где что заканчивается. Может помочь только выделение всего диапазона программы, ограниченного скобками, но этого не достаточно, если нужно не просто посмотреть, но и внести правки или отредактировать.
> semka (2006-10-25 09:26:51)
И с этим не согласен. Опять же, предположим необходимо дописать в функцию что либо между определёнными скобками. Намного легче это сделать, имея пояснения на каждую закрытую скобку. Тем более от этого ничего не старадет, Lisp-интерпретатор всё равно это отбрасывает при компилировании.
Я раньше извращался примерно таким образом. в 14 версии можно было присвоить допустим (setq s setq) и дальше вместо setq использовать s. Вместо polar p. Писалось намного быстрее. Но потом ничего не понятно.
> PahRam (2006-10-25 10:20:34)
Цитата
(setq s setq) и дальше вместо setq использовать s. Вместо polar p.

Это и сейчас можно, только про оптимизацию при компиляции можно забыть, а работать это будет медленнее...
> Евгений Елпанов (2006-10-25 10:24:01)
Не. Сейчас нельзя.
Command: (setq s setq)
#<SUBR @085a29ec SETQ>
Command: (s d 1)
Command: cannot apply special form: SETQ
(: Ну так-то все по-своему правы.
Давайте создадим отдельный тред посвящённый форматированию? Тут это оффтопик, вроде бы.
Вообще очень клёвая тема, немножко странно, конечно, что программистам на лиспе приходится "учиться делать рекурсивные функции", но раз такая необходимость есть не могу не заметить, что Вы, Евгений, проделали хорошую работу. Спасибо вам, хоть лично для себя я от треда ни чего не вынес (:
По поводу функций, которые не умещаются на экран.
Лисп -- функциональный язык программирования, что мешает разбить одну неуклюжую функцию на несколько простых и понятных для понимания?
А для освоения "good lisp programming style" лучше всего подходит изучение исходников серьёзных лисповых проектов. Не Автолисповых, увы.
Например Lisp Jpeg Library. Или банальнейшие lisp-cgi-utils.
Problems have solutions (-:
А от скриншота не откажусь, тем не менее.
> semka (2006-10-25 11:35:32)
Далеко не всё решается рекурсиями. А разбивать функции
Цитата
на несколько простых и понятных

не всегда возможно. Особенно если речь идёт о скорости исполнения кода. И далеко не всегда рекурсия является наиболее выигрышным решением.
А foreach - функция. И чем же она не нравится?
Коллеги, не разменивайтесь на бесплодные споры по поводу форматирования. По каждому языку программирования такие ведутся. В основном, между "доценты с кандидатами". Каждый изматывает своих учеников собственным подходом. Не разрабтав при этом ни одной рабочей программы.
Смотрите в суть.
А по сути - Евгений провел блестящее, убедительное "расследование" по неоднозначному вопросу. Большое ему СПАСИБО. Весьма убедительно. Спорить по сути можно, но лично мне - не хочется. Принимаю к сведению.
И незачем доказывать друг другу преимущества функционального языка. Кто "службу понял", тому все ясно (независимо от частностей оформления). "Бейсикистам" - все равно непонятно. Только вроде как имеются частные расхождения в рамках одной "религии". Типа спора - с какого конца яйцо разбивать.
> ShaggyDoc (2006-10-25 12:50:36)
Ну, в Basic'e тоже можно рекурсии делать smile:)
http://semka.perm.ru/lj/sp1.jpg
Руководство программиста на BASIC для компьютеров ZX Spectrum 48k. Про рекурсию ((:
> semka (2006-10-25 11:35:32)
Только что выслал тебе скриншот...
Что-то заглохло доброе дело.
А между тем тут ещё есть чего сказать.
Чем больше будет знать lisp-программист о своих функциональных корнях -- тем ему зарплата больше. (Пусть это и авто-лисп программист, который и не лисп, на самом-то деле).
Ну вот, например.
Из математического определения рекурсии, плавно перенесенного на бинарное железо и Фон-Неймановскую архитектуру вытекает один не очень приятный факт: рекурсия всегда медленнее итерации. Обидно до слез (-:
Но, как известно, problems have solutions. Медлительность рекурсии обусловлена наглым захавыванием рекурсивной функцией памяти на передачу огромного числа аргументов самой себе.
Передавать, скажем, указатели ей религия не позволяет, мало-ли что там она сама над своими данными сделает? А вдруг попортит? Поэтому мы передаем данные целиком.
На счастье нашего бинарного железа, существует особая форма рекурсии -- tail recursion, или "хвостовая рекурсия".
Суть данной эзотерической техники сводится к простому действию, мы вводим "аккумулятор", который берет на себя ответственность хранить наши данные и уменьшать нагрузку на память.
Вот пример функции факториала, написанный с использованием хвостовой рекурсии:
Код

(defun factorial (number)
  (defun iterate (counter accumulator)
    (if (= counter 0)
          accumulator
    (iterate (- counter 1) (* accumulator counter))))
  (if (< number 0)
    (princ "неверный аргумент")
    (iterate number 1)))

По-хорошему, любой честный интерпретатор лиспа (или его диалектов, скажем scheme) может преобразовать такую рекурсию -- в итерацию (цикл), по-крайней мере, с математической точки зрения они абсолютно одинаковы.
Думайте над оптимизацией, господа.
Ноги, крылья... Главное -- хвост! ©
> sёmka (2007-02-13 16:59:13)
А здесь ты немного ошибаешься!
Дело в том, что при глубокой рекурсии, все именно так, как ты говоришь, а если количество интераций маленькое - все будет наоборот!
> Евгений Елпанов (2007-02-13 17:10:57)
Ну, тут все упирается в качество реализации интепретатора. В любом случае, даже исходя из логики: рекурсия использует стек данных, итерация использует счетчик (то есть одну единственную (в общем случае) переменную).
Расход памяти действительно меньше у итерации, обращений к памяти, в том числе и на "запись", тоже меньше.
Вполне допускаю, что рекурсия на малых глубинах работает быстрее, но вовсе не всегда и вовсе не на всех машинах и вовсе не потому что это рекурсия, скорее потому что создатель интерпретатора её любил.
Вот пример, выполняется итеративный и рекурсивные (тру-рекурсия, без хвоста) функции вычисления факториала 5000.
Интерпретатор GNU CLisp:
Код

(defun fac-rec (x)
  (cond
    ((= x 0) 1)
    ((= x 1) 1)
    (t (* x (fac-rec (- x 1))))))
(defun fac-it (x)
    (if (= x 0) 1
        (do ((res x (* res x)))
            ((= x 1) res)
            (setf x (- x 1)))))
(time (fac-rec 5000))
(time (fac-it 5000))
semka@abahachi:~/src/lisp$ clisp fac.lisp
Real time: 0.199741 sec.
Run time: 0.192012 sec.
Space: 15886304 Bytes
GC: 23, GC time: 0.144011 sec.
Real time: 0.164482 sec.
Run time: 0.148009 sec.
Space: 18136888 Bytes
GC: 27, GC time: 0.088005 sec.

Как видно -- итерация выигрывает во времени.
А по-памяти рекурсия выигрывает на Garbage Collector'е, который довольно шустрый и вообще молодец со всех сторон в данной реализации лиспа.
Ой, вышла ошибочка...
У меня получилось, что рекурсия всегда быстрее!
Код
(defun rec-factorial (N)
;;(setq n 10)
(if (zerop n)
  1
  (* n (rec-factorial (1- n)))
) ;_  if
) ;_  defun

Результаты сравнения:
Код
Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):
    (REC-FACTORIAL 1).....1594 / 1.11 <fastest>
    (FACTORIAL 1).........1766 / 1.00 <slowest>
Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):
    (REC-FACTORIAL 10).....1922 / 1.13 <fastest>
    (FACTORIAL 10).........2172 / 1.00 <slowest>
Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):
    (REC-FACTORIAL 20).....1156 / 1.16 <fastest>
    (FACTORIAL 20).........1344 / 1.00 <slowest>
Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):
    (REC-FACTORIAL 30).....1329 / 1.18 <fastest>
    (FACTORIAL 30).........1563 / 1.00 <slowest>
> sёmka (2007-02-13 17:26:23)
Интересно, какой интерпретатор лиспа, ты использовал, чтоб он вычислил факториал 5000?
Посмотри, что возвращает функция...
> Евгений Елпанов (2007-02-13 17:10:57)
сам когда-то увлекался рекурсивными функциями, но как говорится "доверия не оправдали". в 99% они действительно медленнее итерации. если встроить, например, в функцию rec-factorial проверку на приемлемость аргумента (N>0, (type N)='INT) скорость сразу упадет. можна конешно сделать проверку в головной функции, но это уже будет не то...
> sёmka (2007-02-13 16:59:13)
Цитата
Чем больше будет знать lisp-программист о своих функциональных корнях — тем ему зарплата больше

Это знание или предположение или мечта? Назовите адрес, где платят в зависимости от знаний "функциональных корней" smile:)
> Vovka (2007-02-14 01:23:37)
Действительно, уровнял проверки и скорость почти уровнялась...
Правда, рекурсия оказалась немного быстрее...
Код
(defun rec-factorial (N)
(if (zerop n)
  1
  (* n (rec-factorial (1- n)))
) ;_  if
) ;_  defun
(defun int-factorial (N / F)
(setq f 1)
(while (> n 0)
  (setq f (* n f)
        n (1- n)
  ) ;_  setq
) ;_  while
f
) ;_  defun

Результаты проверки скорости:
Код
Benchmarking ..................
Elapsed milliseconds / relative speed for 32768 iteration(s):
    (REC-FACTORIAL 1).....1547 / 1.01 <fastest>
    (INT-FACTORIAL 1).....1563 / 1 <slowest>
Benchmarking ..................
Elapsed milliseconds / relative speed for 32768 iteration(s):
    (REC-FACTORIAL 10).....1875 / 1.01 <fastest>
    (INT-FACTORIAL 10).....1891 / 1 <slowest>
Benchmarking .................
Elapsed milliseconds / relative speed for 16384 iteration(s):
    (REC-FACTORIAL 20).....1110 / 1.01 <fastest>
    (INT-FACTORIAL 20).....1125 / 1 <slowest>
Benchmarking .................
Elapsed milliseconds / relative speed for 16384 iteration(s):
    (REC-FACTORIAL 30).....1297 / 1.02 <fastest>
    (INT-FACTORIAL 30).....1328 / 1 <slowest>
> Евгений Елпанов (2007-02-14 08:18:50)
В том конкретном примере я использовал GNU CLisp (о чем писал, кстати).
Вот пример на Scheme, цлиспа сейчас под рукой нет. (Интерпретатор MzScheme R5RS):
Код

(define (fac-rec x)
  (cond
    ((= x 0) 1)
    ((= x 1) 1)
    (#t (* x (fac-rec (- x 1))))))
Welcome to DrScheme, version 360.
Language: Standard (R5RS).
> (fac-rec 5000)
42285779266055435222010642002335844053907866746266­467488
49782402181358052708108200690899047871706387537084­746657
30068544587848606668381273633721089377278763127939­036305
84621606439044789869822398719297088962116126529683­217755
00399242196837031469072644728787897904047548841622­152266
71928410969236910449565971736352948400223840381120­644820
23085767110450230617489475542830976178172404080532­480992
78093287840554861993645482912118762582488021891739­779000
50213212598043639244626460770511358846595108675470­585833
92465522558903547443598834738317898803463300845863­151020
90915099356538200109330479657425567419309170551728­052002
36075085991197635228755907902043369743123506916831­211924
49597155626740752146219898623308862599830285986485­757874
94459631152869708867100462684236481789899054546908­613916
13218344174148807186234448114831209490361196546872­767755
61788682872026910481409245641034183597560427645816­151317
85759016610717825441569808833593727299956033713712­004710
49437656291142488605335299499642300699972204918120­100819
05943914067505326500477553385089909794510155109148­6907004407...

Можно я не буду весь вывод сюда вписывать? (-:
Неужели это кажется так сложно -- реализовать длинную арифметику на лиспе? Любой нормальный интерпретатор так и работает, не вижу ничего удивительного. А что касается стека, дак я уже говорил о гарбаж коллекторе и оптимизации рекурсий.
А что у вас рекурсия быстрее получилась -- то поклоны и всяческие ништяки в сторону разработчиков данного интерпретатора. (Я ошибаюсь или это автолисп? Чем мерили?)
> ShaggyDoc (2007-02-14 06:40:46)
Человек понимающий сущность лиспа -- просто перестаёт забивать микроскопом гвозди. Было бы странно предполагать, что ему зарплату не повысят, если он станет чуточку лучше (-:
(Ну или по-крайней мере он найдёт себе достойную работу).
> sёmka (2007-02-14 10:12:11)
Да, мерял автолиспом, но автолисп не умеет работать с такими большими целыми числами, т.е. на автолиспе можно вычислить факториал только до 31 при использовании целочисленных вычислений и без шаманства для обхода ограничений...
Короче, автолисп работает с целыми числами в диапазоне
Код
от +2147483647 до -2147483648
Угу, просто в автолиспе нет встроенной системы приведения к длинной арифметике, при переполнении буфера, в принципе оно там и не нужно.
Так, на всякий случай, длинная арифметика -- это когда операции производятся не с типом int, а с типом string. То есть число представляется в виде строки и описываются элементарные правила арифметики применительно к строкам.
> Евгений Елпанов (2007-02-14 08:18:50)
проверял ваши функции у себя - итерация работает быстрее. может влияет версия автокада, может железо...
но что бы рекурсия победила, плюс отсекаем минусовые аргументы, предлагаю немного изменить вашу функцию, вот так:
Код
(defun rec-factorial (N)
  (if (< n 2)
    1
    (* n (rec-factorial (1- n)))
  )
)
http://www.caduser.ru/forum/index.php...&TID=21922
Вы, конечно, будете смеяться, но сумма ряда в задаче, представленной нам > PalStudio (2007-02-15 22:15:26), просто равна exp(x).
Страницы: Пред. 1 2 3 4 5 След.
Читают тему (гостей: 1, пользователей: 0, из них скрытых: 0)