Re: Уроки создания рекурсивных функций

Ребят, вы вообще мои сообщения читаете?
Я где-то писал, что не надо ставить комментарии?
У вас экстрасенсорные способности хромают, по поводу проектов под заказчика, кстати.
Я писал только то, что оформление скобочек, которое принято автокад-автоформаттером это изврат в высшей степени.
Комментарии писать надо, они хорошие очень.

Re: Уроки создания рекурсивных функций

> semka
Я еще раз повторю, если между открывающей и закрывающей скобкой несколько тысяч строк, то быстро просмотреть такой код не получится, но очень помогает стандартное форматирование с пояснением (имеется в виду стандартное пояснение от автоформата), какое действие заканчивается на этой скобке!
Короче! Если открывающая и закрывающая скобки умещаются на экране, то можно форматировать как угодно. Если при стандартном форматировании обе скобки не умещаются на экране, а при вашем варианте умещаются, думаю, ваше форматирование лучше. Если между открывающими и закрывающими скобками умещается несколько экранов, то стандартное форматирование очень помогает, не смотря на увеличение количества строк!
PS. Если хочешь, могу выслать скриншот с экрана, у меня экран 1200х1600 (портретный режим) и уверен, что все сразу станет понятно...
Например, представь себе цикл FOREACH внутри которого еще несколько таких циклов по несколько сотен строк и  куча мелких циклов  - пойди разберись, где что заканчивается. Может помочь только выделение всего диапазона программы, ограниченного скобками, но этого не достаточно, если нужно не просто посмотреть, но и внести правки или отредактировать.

Re: Уроки создания рекурсивных функций

> semka
И с этим не согласен. Опять же, предположим необходимо дописать в функцию что либо между определёнными скобками. Намного легче это сделать, имея пояснения на каждую закрытую скобку. Тем более от этого ничего не старадет, Lisp-интерпретатор всё равно это отбрасывает при компилировании.
Я раньше извращался примерно таким образом. в 14 версии можно было присвоить допустим (setq s setq) и дальше вместо setq использовать s. Вместо polar p. Писалось намного быстрее. Но потом ничего не понятно.

Re: Уроки создания рекурсивных функций

PahRam пишет:

(setq s setq) и дальше вместо setq использовать s. Вместо polar p.

Это и сейчас можно, только про оптимизацию при компиляции можно забыть, а работать это будет медленнее...

Re: Уроки создания рекурсивных функций

> Евгений Елпанов
Не. Сейчас нельзя.
Command: (setq s setq)
#<SUBR @085a29ec SETQ>
Command: (s d 1)
Command: cannot apply special form: SETQ

Re: Уроки создания рекурсивных функций

(: Ну так-то все по-своему правы.
Давайте создадим отдельный тред посвящённый форматированию? Тут это оффтопик, вроде бы.
Вообще очень клёвая тема, немножко странно, конечно, что программистам на лиспе приходится "учиться делать рекурсивные функции", но раз такая необходимость есть не могу не заметить, что Вы, Евгений, проделали хорошую работу. Спасибо вам, хоть лично для себя я от треда ни чего не вынес (:
По поводу функций, которые не умещаются на экран.
Лисп -- функциональный язык программирования, что мешает разбить одну неуклюжую функцию на несколько простых и понятных для понимания?
А для освоения "good lisp programming style" лучше всего подходит изучение исходников серьёзных лисповых проектов. Не Автолисповых, увы.
Например Lisp Jpeg Library. Или банальнейшие lisp-cgi-utils.
Problems have solutions (-:
А от скриншота не откажусь, тем не менее.

Re: Уроки создания рекурсивных функций

> semka
Далеко не всё решается рекурсиями. А разбивать функции

на несколько простых и понятных

не всегда возможно. Особенно если речь идёт о скорости исполнения кода. И далеко не всегда рекурсия является наиболее выигрышным решением.
А foreach - функция. И чем же она не нравится?

Re: Уроки создания рекурсивных функций

Коллеги, не разменивайтесь на бесплодные споры по поводу форматирования. По каждому языку программирования такие ведутся. В основном, между "доценты с кандидатами". Каждый изматывает своих учеников собственным подходом. Не разрабтав при этом ни одной рабочей программы.
Смотрите в суть.
А по сути - Евгений провел блестящее, убедительное "расследование" по неоднозначному вопросу. Большое ему СПАСИБО. Весьма убедительно. Спорить по сути можно, но лично мне - не хочется. Принимаю к сведению.
И незачем доказывать друг другу преимущества функционального языка. Кто "службу понял", тому все ясно (независимо от частностей оформления). "Бейсикистам" - все равно непонятно. Только вроде как имеются частные расхождения в рамках одной "религии". Типа спора - с какого конца яйцо разбивать.

Re: Уроки создания рекурсивных функций

> ShaggyDoc
Ну, в Basic'e тоже можно рекурсии делать :)

Re: Уроки создания рекурсивных функций

http://semka.perm.ru/lj/sp1.jpg
Руководство программиста на BASIC для компьютеров ZX Spectrum 48k. Про рекурсию ((:

Re: Уроки создания рекурсивных функций

> semka
Только что выслал тебе скриншот...

Re: Уроки создания рекурсивных функций

Что-то заглохло доброе дело.
А между тем тут ещё есть чего сказать.
Чем больше будет знать 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) может преобразовать такую рекурсию -- в итерацию (цикл), по-крайней мере, с математической точки зрения они абсолютно одинаковы.
Думайте над оптимизацией, господа.
Ноги, крылья... Главное -- хвост! (c)

Re: Уроки создания рекурсивных функций

> sёmka
А здесь ты немного ошибаешься!
Дело в том, что при глубокой рекурсии, все именно так, как ты говоришь, а если количество интераций маленькое - все будет наоборот!

Re: Уроки создания рекурсивных функций

> Евгений Елпанов
Ну, тут все упирается в качество реализации интепретатора. В любом случае, даже исходя из логики: рекурсия использует стек данных, итерация использует счетчик (то есть одну единственную (в общем случае) переменную).
Расход памяти действительно меньше у итерации, обращений к памяти, в том числе и на "запись", тоже меньше.
Вполне допускаю, что рекурсия на малых глубинах работает быстрее, но вовсе не всегда и вовсе не на всех машинах и вовсе не потому что это рекурсия, скорее потому что создатель интерпретатора её любил.
Вот пример, выполняется итеративный и рекурсивные (тру-рекурсия, без хвоста) функции вычисления факториала 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'е, который довольно шустрый и вообще молодец со всех сторон в данной реализации лиспа.

Re: Уроки создания рекурсивных функций

Ой, вышла ошибочка...
У меня получилось, что рекурсия всегда быстрее!

(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>

Re: Уроки создания рекурсивных функций

> sёmka
Интересно, какой интерпретатор лиспа, ты использовал, чтоб он вычислил факториал 5000?
Посмотри, что возвращает функция...

Re: Уроки создания рекурсивных функций

> Евгений Елпанов
сам когда-то увлекался рекурсивными функциями, но как говорится "доверия не оправдали". в 99% они действительно медленнее итерации. если встроить, например, в функцию rec-factorial проверку на приемлемость аргумента (N>0, (type N)='INT) скорость сразу упадет. можна конешно сделать проверку в головной функции, но это уже будет не то...

Re: Уроки создания рекурсивных функций

sёmka пишет:

Чем больше будет знать lisp-программист о своих функциональных корнях — тем ему зарплата больше

Это знание или предположение или мечта? Назовите адрес, где платят в зависимости от знаний "функциональных корней" :)

Re: Уроки создания рекурсивных функций

> Vovka
Действительно, уровнял проверки и скорость почти уровнялась...
Правда, рекурсия оказалась немного быстрее...

(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>

Re: Уроки создания рекурсивных функций

> Евгений Елпанов
В том конкретном примере я использовал 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)
42285779266055435222010642002335844053907866746266467488
49782402181358052708108200690899047871706387537084746657
30068544587848606668381273633721089377278763127939036305
84621606439044789869822398719297088962116126529683217755
00399242196837031469072644728787897904047548841622152266
71928410969236910449565971736352948400223840381120644820
23085767110450230617489475542830976178172404080532480992
78093287840554861993645482912118762582488021891739779000
50213212598043639244626460770511358846595108675470585833
92465522558903547443598834738317898803463300845863151020
90915099356538200109330479657425567419309170551728052002
36075085991197635228755907902043369743123506916831211924
49597155626740752146219898623308862599830285986485757874
94459631152869708867100462684236481789899054546908613916
13218344174148807186234448114831209490361196546872767755
61788682872026910481409245641034183597560427645816151317
85759016610717825441569808833593727299956033713712004710
49437656291142488605335299499642300699972204918120100819
059439140675053265004775533850899097945101551091486907004407...

Можно я не буду весь вывод сюда вписывать? (-:
Неужели это кажется так сложно -- реализовать длинную арифметику на лиспе? Любой нормальный интерпретатор так и работает, не вижу ничего удивительного. А что касается стека, дак я уже говорил о гарбаж коллекторе и оптимизации рекурсий.
А что у вас рекурсия быстрее получилась -- то поклоны и всяческие ништяки в сторону разработчиков данного интерпретатора. (Я ошибаюсь или это автолисп? Чем мерили?)

> ShaggyDoc
Человек понимающий сущность лиспа -- просто перестаёт забивать микроскопом гвозди. Было бы странно предполагать, что ему зарплату не повысят, если он станет чуточку лучше (-:
(Ну или по-крайней мере он найдёт себе достойную работу).

Re: Уроки создания рекурсивных функций

> sёmka
Да, мерял автолиспом, но автолисп не умеет работать с такими большими целыми числами, т.е. на автолиспе можно вычислить факториал только до 31 при использовании целочисленных вычислений и без шаманства для обхода ограничений...
Короче, автолисп работает с целыми числами в диапазоне

 от +2147483647 до -2147483648

Re: Уроки создания рекурсивных функций

Угу, просто в автолиспе нет встроенной системы приведения к длинной арифметике, при переполнении буфера, в принципе оно там и не нужно.
Так, на всякий случай, длинная арифметика -- это когда операции производятся не с типом int, а с типом string. То есть число представляется в виде строки и описываются элементарные правила арифметики применительно к строкам.

Re: Уроки создания рекурсивных функций

> Евгений Елпанов
проверял ваши функции у себя - итерация работает быстрее. может влияет версия автокада, может железо...
но что бы рекурсия победила, плюс отсекаем минусовые аргументы, предлагаю немного изменить вашу функцию, вот так:

(defun rec-factorial (N)
  (if (< n 2)
    1
    (* n (rec-factorial (1- n)))
  )
)

Re: Уроки создания рекурсивных функций

https://www.caduser.ru/forum/topic21922.html

Re: Уроки создания рекурсивных функций

Вы, конечно, будете смеяться, но сумма ряда в задаче, представленной нам > PalStudio (2007-02-15 22:15:26), просто равна exp(x).