Бесконечная рекурсия без переполнения стека

Тема в разделе "WASM.HEAP", создана пользователем l_inc, 18 мар 2009.

  1. diamond

    diamond New Member

    Публикаций:
    0
    Регистрация:
    21 май 2004
    Сообщения:
    507
    Адрес:
    Russia
    Ещё раз: там нет замены на обычную формулу для общего случая. Только для первых частных значений. Некоторое количество первых значений, конечно, можно вбить руками, но IMHO нельзя написать код, в котором не будет рекурсии (явной или эмулируемой) и который будет вычислять все значения функции Аккермана (для любых пар параметров) в предположении наличия чисел сколь угодно большой длины.
     
  2. Y_Mur

    Y_Mur Active Member

    Публикаций:
    0
    Регистрация:
    6 сен 2006
    Сообщения:
    2.494
    В функциях подобных Аккермановской порочна сама постановка задачи - рекурентная функция первична, а применение её результатов и способ их вычисления вторичны и должны подстраиваться под рекурсию :)
    Именно за этот порочный подход ратуют ФЯ и это их главный недостаток ;)
    На самом деле следует идти другим путём - есть потребность в такой-то последовательности данных / алгоритме действий и т.п. определёнными практической стороной задачи, а не извращённой потребностью "куда-то приткнуть рекурсивную формулу, только потому что её кто-то придумал" :)) А дальше уже начинаем думать как это реализовать с помощью рекурсии или без оной ;)

    А общая нерекурентная формула там возможна, только над ней никто не заморачивался по причине отсутствия её практической значимости ;)
     
  3. ozzman2k

    ozzman2k New Member

    Публикаций:
    0
    Регистрация:
    7 июл 2008
    Сообщения:
    10
    Y_Mur
    Дык тебе может встретиться подобная задача(вычисление НЕ примитивно-рекурсивной функции) и решить её без рекурсии ты не сможешь. А порочна постановка задачи или нет, это не важно, есть задача и ты должен её решить =]

    з.ы. только не надо меня просить привести подобную задачу)))
     
  4. Y_Mur

    Y_Mur Active Member

    Публикаций:
    0
    Регистрация:
    6 сен 2006
    Сообщения:
    2.494
    ozzman2k
    Конечно не буду :)) гы-гы - даже если сам предложишь - подумаю браться или отмазываться :)), а так конечно полностью согласен и уже писал в #53
     
  5. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    aa_dav
    А ничего так.. похожая получилась история. :) Особенно в том месте, где ученик радуется, что он был прав. Теперь перейдём к неточностям. Если то, что "спустя годы" на самом деле означает примерно пару месяцев, — это не суть, то суть в том, что пример получился далеко не аналогичный. В частности в том, что для циклов, ветвлений и даже свитчей я могу довольно точно представить, во что будет скомпилирован код. Здесь же я понятия не имею, как компилятор себя поведёт в случае нерепетитивной рекурсивной процедуры. Мало того, недалёкость компилятора может мне стоить не просто нехилых тормозов при выполнении, но и вообще потери функциональности в случае, если стека для каких-то вычислений не хватит. Это комментарий к:
    Если Вам абсолютно безразлично, свалится ли Ваша программа при вызове akkermanFunc(3,13) (моя благодарность Y_Mur за наглядный пример), то мне это важно. Кстати, это Вы уводите разговор в сторону реализации рекурсии в функциональных языках. На самом же деле...
    Покажите мне конкретное место, откуда видно, что я так решил. Я изначально говорил только об идее, а Вы мне пытаетесь навязать, что я её путаю с реализацией. Так вот идеологически рекурсия есть вызов процедуры из самой себя независимо от того, репетитивная это рекурсия или нет. И соответственно идеологически вызов процедуры обязан сохранять за собой в стеке как минимум адрес возврата. Вот исходя из этого я и попытался сформулировать вопрос и условия задачи (кое-что сначала не учёл, но суть не в этом).
    Что же до упомянутого мной в начале топика спора с преподавателем, там я действительно был прав, т.к. тогда шла речь о вполне конкретном коде (правда, не помню, о каком). Преподаватель утверждал, что он не приводит к переполнению стека. Позже я просто сам проверил и убедился, что таки приводит.
     
  6. jaja

    jaja New Member

    Публикаций:
    0
    Регистрация:
    23 июл 2008
    Сообщения:
    243
    Выше головы не прыгнешь!
     
  7. aa_dav

    aa_dav Active Member

    Публикаций:
    0
    Регистрация:
    24 дек 2008
    Сообщения:
    512
    l_inc

    > В частности в том, что для циклов, ветвлений и даже свитчей я могу довольно точно представить, во что будет скомпилирован код.

    Угу угу. А что вам мешает представить себе аналогичное для ФЯ? Рзаве что только незнание их компиляторов/интерпретаторов - но это же вас, разумеется оправдывает, ведь незнание законов - освобождает от ответственности за их невыполнение, так что ли? =)
    Мы, ей богу, скатываемся в совершенно глупую полемику ни-о-чем.
    Напомнить ли вам сколько молодоых и начинающих энтузиастов пользуются stl или (не дай бог!) boost-ом в C++ и получают суперзначительный фейл по перфомансу забывая делать банальнейший до рвоты в спазмах const & string, там где это возможно?
    Да, они действительно НЕ ПРЕДСТАВЛЯЮТ во что скомпилируется их код. И ФЯ тут совершенно не при чем.
    Но разве владение ФЯ не обязывает так же, как и владение C++-ом некоторых, хотя бы примитивных понятий о том во что превратится рекурсия, а во что - хвостовая рекурсия? Да почитайте же наконец самый распоследний учебник по Scheme! Что вы тут огород вокруг канавы городите, ей богу, я не понимаю....
    Если вы новичок в ФЯ - так и скажите. Как и Y_Mur, который из незнания своего вытаскивает "факты" о порочности рекурсии, более чем полностью являющиеся литературнуми эквилибристикой голыми эмоциями, нежели чем-то относящимся к реальности более чем романы Донцовой.
    Особенно про то что их аппаратно никак не улучшить - тут ржал, но не буду рассеивать тайну завесы над тем чем именно прикольно ФЯ для аппаратной начинки для автора сиих изысков.... Может сам где найдет и проникнется... Это всяко большее влияние оказывает, чем противоборство в споре...
     
  8. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    aa_dav
    Новичок. У нас с первой встречи не сложилось. Поэтому продолжение отношений не планируется. Хотя бы потому, что в функциональном стиле я могу писать на практически любом императивном языке. В то время, как функциональные языки отбирают у меня возможность вольного оформления кода, и для того, чтобы писать на чисто функциональном языке в императивном стиле, нужны нифиговые извращения (вспомнить только, как у нас потенциально императивный ввод-вывод вводился: горы вложенных-поперевложенных функций высших порядков, которые по сути ничего не делают, и такие же горы закрывающих скобок в конце функции ввода/вывода). А ещё вспоминается, каких нехилых наворотов стоила организация простой очереди на основе связного списка, чтобы затраты на внесение/вынесение элементов в/из очереди понизить из класса сложности O(n) до нормального константного.
    +1 Я вопрос (по большому счёту к функциональным языкам не относящийся) сформулировал и ответ на него получил. А Вы непонятно к чему решили вдруг защитить функциональные языки.
     
  9. Y_Mur

    Y_Mur Active Member

    Публикаций:
    0
    Регистрация:
    6 сен 2006
    Сообщения:
    2.494
    Каюсь - про ФЯ узнал только в этом топике ;) Зная по предидущему опыту о коварстве рекурсии сразу же понял, что язык не имеющий ничего кроме неё будет содержать нелепые извращения и неочевидные подводные камни - источники трудноловимых багов, но всё-же решил последовать совету
    Увиденное превзошло все ожидания - я конечно предполагал неважную читаемость синтаксиса, но такое не могло даже присниться в кошмарах :))
    Код (Text):
    1. ;; сумма элементов списка в характерном для Scheme стиле
    2. ;; (вспомогательная функция loop выражает цикл с помощью
    3. ;; хвостовой рекурсии и переменной-аккумулятора)
    4. (define (sum-list x)
    5.   (let loop ((x x) (n 0))
    6.     (if (null? x)
    7.         n
    8.         (loop (cdr x) (+ (car x) n)))))
    9. ;; вызов функции
    10. (sum '(6 6 6 100))
    11. ;; где:
    12. (null? <список>) — проверяет, а есть ли ещё какие элементы в списке,
    13. (car <список>) — возвращает первый элемент списка,
    14. (cdr <список>) — возвращает список из всех элементов, кроме первого, а если больше ничего не осталось, то пустой список.
    И всё это чтобы просто просуммировать набор чисел :))
    Если я когда нибудь захочу всерьёз поизвращаться с нечитаемым синтаксисом - лучше уж освою что-нибудь из этого :))
     
  10. oxcc

    oxcc New Member

    Публикаций:
    0
    Регистрация:
    26 сен 2008
    Сообщения:
    51
    елси в самой функции редактировать стек нельзя, то не юзая каких-либо системных фокусов реализовать невозможно
     
  11. Voodoo

    Voodoo New Member

    Публикаций:
    0
    Регистрация:
    9 апр 2003
    Сообщения:
    297
    Адрес:
    Новосибирск
    Lisp по синтаксису уродлив и пугающ. Рекомендую haskell или весьма полезный на будущее Erlang.
    И читать нужно не учебник по SCHEME, а вовсе даже SICP. Ну, или для начала - опять же, лекции на которые я кидал ссылку где-то тут.
     
  12. Y_Mur

    Y_Mur Active Member

    Публикаций:
    0
    Регистрация:
    6 сен 2006
    Сообщения:
    2.494
    В нормальных языках программирования встретив рекурсию всегда следует выдать себе варнинг: "стоп - с этого места будь внимательнее - здесь может скрываться коварный маразм".
    Ни один здравомыслящий программист при вычислении допустим факториала не будет лепить конструкцию:
    Код (Text):
    1. UINT factorial_1 (UINT n)
    2. {
    3.     UINT result = 1;
    4.     if (n > 1)
    5.     {
    6.         std::stack<UINT> myStack;
    7.         while (n > 1)
    8.         {
    9.             myStack.push(n);
    10.             n--;
    11.         }
    12.         while (!myStack.empty())
    13.         {
    14.             result *= myStack.top( );
    15.             myStack.pop();
    16.         }
    17.     }
    18.     return result;
    19. }
    наивно полагая, что умный компилятор сам разберётся, что подразумевается всего-лишь:
    Код (Text):
    1. UINT factorial_2 (UINT n)
    2. {
    3.     UINT result = 1;
    4.     while (n > 1) result *= n--;
    5.     return result;
    6. }
    Но "простенькая" рекурсивная конструкция
    Код (Text):
    1. UINT factorial_recursion (UINT n)
    2. {
    3.     if (0 == n) return 1;
    4.     return n * factorial_recursion(n - 1);
    5. }
    которую пихают в большинство учебников - это как раз первый а не второй вариант ;)
    И это не "особенность реализации компилятора" а самая суть рекурсии - её "мощность" как раз и заключается в способности скрывать навороченные аглоритмы под маской "простеньких" конструкций. Разумеется обращаться с этой "скрытной мощью" нужно очень осторожно, чтобы не оказаться в положении "эспериментатора", дёрнувшего чеку гранаты из соображений - "а что это тут за колечко?" :))

    В ФЯ всё поставлено с ног на уши :)
    Навороченный рекурcивный вариант (см. первый код) выглядит простенько и изящно:
    Код (Text):
    1. (define (factorial n)
    2.   (if (= n 0)
    3.       1
    4.       (* n (factorial (- n 1)))))
    а нормальный (если конечно это слово применимо к ФЯ) итерационный, на основе хвостовой рекурсии, по сравнению с ним настоящий монстр:
    Код (Text):
    1. (define (fact-iter result counter)
    2. (if (= counter 0)
    3.     result
    4.     (fact-iter (* counter result)
    5.                (- counter 1))))
    6. (define (factorial n) (fact-iter 1 n))
    которого так и тянет "упростить" до рекурсивного, задействовав её "мощь" (см. про гранату с интересным таким колечком :))

    Разумеется такая извращённая семантика неизбежно порождает соотвествующий извращённый стиль программирования, превращающий код в "минное поле".

    Имхо в классификаторе Wiki ошибка - ФЯ должно находится в разделе: Эзотерические языки / Языки-«чёрные ящики». Созданы с целью затруднить написание кода.
     
  13. Y_Mur

    Y_Mur Active Member

    Публикаций:
    0
    Регистрация:
    6 сен 2006
    Сообщения:
    2.494
    Обратите внимание:
    Код (Text):
    1. UINT factorial_recursion (UINT n)
    2. {
    3.     if (0 == n) return 1;
    4.     return n * factorial_recursion(n - 1);
    5. }
    это явное и недвусмысленное указание компилятору - составить два цикла - в первом создаётся список вида n, n-1, ... 3, 2, 1, а во втором элементы этого списка извлекаются и перемножаются. Соответственно у оптимизирующего компилятора есть выбор - сохранить этот список в общем программном стеке, выделить специальный объект "стек" для этой функции, использовать динамический массив с указателями, но нет никакого права объединить эти циклы в один, поскольку такие попытки "оптимизации" на более сложных алгоритмах приведут к полному бреду.
    Возможность "математически доказать сходимость рекурсии" тут совершенно ничего не изменит ;) она даже не сможет предупредить о нелепости такого решения задачи.
    Попытки что-то тут оптимизировать вручную, не отказываясь от рекурсии, тоже окажутся безуспешными - в этой "простой" конструкции просто не за что зацепиться :)

    Другое дело, что нетривиальная комбинация циклов, порождаемая рекурсией, может быть в некоторых случаях достаточно эффективно применена для решения соответсвующих нетривиальных задач, при этом накладные расходы на захламление общего стека лишними адресами возврата могут оказаться существенно меньшими, чем расходы на поддержание к примеру пересыщенного избыточными проверками объекта std::stack, позволяющего отказаться от сохранения этих лишних адресов возврата и сохранять только полезные данные, эмулируя эквивалент рекурсии.
    Но эффективное применение рекурсии это искусство, требующее аккуратности и квалификации - задача сродни задаче спецназовца - "пробраться к штабу противника и кинуть гранату точно в окно штаба, как раз в тот момент когда всё их начальство в сборе".
    А пропаганда рекурсии как "универсального средства решения любых задач" - это раздача боевых гранат детишкам - "пусть поиграют, может быть спецназовцами вырастут". И вреда от этого намного больше чем от пресловутого "VB формошлёпства".
     
  14. aa_dav

    aa_dav Active Member

    Публикаций:
    0
    Регистрация:
    24 дек 2008
    Сообщения:
    512
    Рассуждать о сложности того чего не знаешь толком - это конечно забавно. =)
    С++ вон тоже дико сложен до абсурда - пишешь if ( a = 1 ), а условие всегда срабатывает, даже если a не равно 1. о ужос. мозг поломан, программист повержен. =)))
     
  15. Y_Mur

    Y_Mur Active Member

    Публикаций:
    0
    Регистрация:
    6 сен 2006
    Сообщения:
    2.494
    aa_dav
    Гы-гы забавно путать синтаксическую ошибку в программе с "особенностями сложного языка" :)), кстати в #73 показан стандартный приём if(0 == n), позволяющий сильно понизить вероятность возникновения подобных ошибок ;)
     
  16. aa_dav

    aa_dav Active Member

    Публикаций:
    0
    Регистрация:
    24 дек 2008
    Сообщения:
    512
    Y_Mur

    Да что ты, всё же совсем просто! Всего через год усиленного C-шного программинга программер способен без заглядывания в справочник описать массив указателей на функцию, возвращающую int и принимающую в качестве аргумента массив чаров и указатель на функцию не возвращающую значаение и не принимающую аргументов! Это же так просто! =)))
    Поверь, ты просто долго программишь в императивном стиле, поэтому и считаешь его проще и понятнее.
     
  17. Y_Mur

    Y_Mur Active Member

    Публикаций:
    0
    Регистрация:
    6 сен 2006
    Сообщения:
    2.494
    aa_dav
    В C++ можно свободно использовать "морально устаревший" стиль программирования базирующийся на обычных функциях и глобальных/локальных переменных (литературы по этой теме имхо даже больше чем по классам), а пространства имён, перегрузки, классы, наследования и т.п. осваивать по мере прихода опыта и понимания, что это действительно удобно и позволяет избегать многих проблем в больших проектах. Этот подход полюбому проще и лучше "рекурсивного", а третьим плюсом такого освоения С++, является наработка низкоуровневого понимания механизма работы и программы и компилятора.
    В ФЯ же выбор программиста сводится к альтернативам:
    - изуродовать алгоритм за счёт неуместной рекурсии
    или
    - изуродовать исходник применив "хвастливую рекурсию", которая на самом деле и рекурсией не является и в общую структуру ФЯ не больно хорошо вписывается, а скорее выглядит как "второпях прилепленная заплатка".
    Наглядные примеры в #72
     
  18. Voodoo

    Voodoo New Member

    Публикаций:
    0
    Регистрация:
    9 апр 2003
    Сообщения:
    297
    Адрес:
    Новосибирск
    Y_Mur
    Когда тебе что-то непонятно - проблема не в языке, а в голове. Потому не надо говорить за всех, что рекурсия - зло. А в концепцию ФЯ гораздо лучше вписывается рекурсия, чем циклы.
    Скорей всего, N лет назад так же говорили про ООП. И что теперь?.. Вобщем, хватит убеждать окружающих в своей ограниченности и нетерпимости. Языки и стили нужны всякие, разнообразие - это хорошо, важно и правильно.
     
  19. CyberManiac

    CyberManiac New Member

    Публикаций:
    0
    Регистрация:
    2 сен 2003
    Сообщения:
    2.473
    Адрес:
    Russia
    aa_dav
    [Ухмыляясь в 3 ряда зубов] А ничего, что в качестве шутки юмора я такое ещё аж на "Спектруме" делал? Правда, число имитаций команды jp ограничивалось 50 штуками в секунду - маскируемые прерывания там ходили строго по расписанию. Но если у нас есть платформа, у которой вся память сделана из ОЗУ (Кворум-128, например), то можно использовать всякие комбинации ld+rst xx.
     
  20. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    Voodoo
    На самом деле вместо того, чтобы пинать друг друга, можно организовать небольшое сравнение.
    Взять по несколько сторонников каждой из концепций. Например, по два с каждой стороны. Также с каждой стороны берётся по одному человеку, которые придумывают по две не слишком сложных задачи. Придумывающие, разумеется, не участвуют в решении задач.
    В результате можно сравнить концепции функционального (сторонники, скажем, используют haskell) и императивного (сторонники используют, например, C/C++) программирования по трём критериям: время разработки, время исполнения и количество ошибочных релизов (т.е. надёжность).
    Для упрощения проверки программы должны быть консольными, брать входные данные из stdin, а выводить в stdout. Программы проверки через пайпы прогоняют тестовые примеры. Их пишут составители задач, опять таки используя заранее оговоренные языки.
    Каждая сторона должна решить все четыре задачи.
    Другое дело, что всем будет лень этим заниматься. :)