Уроки создания рекурсивных функций (Страница 4 из 5)

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

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

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

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

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

Что-то заглохло доброе дело.
А между тем тут ещё есть чего сказать.
Чем больше будет знать 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)

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

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

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

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

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

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