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

aa_dav

Задача замены рекурсии на комбинацию циклов в большинстве случаев не тривиальна даже для продвинутого программиста, и совершенно неподъёмна для "вменяемого ФЯ-компилятора".

Семантика языка принципиально не имеющая циклов и перходов, потому как "рекурсия универсальна" это однозначно маразм

 

Да, нахрена тогда деление, умножение, ведь всё это можно заменить сложением и логическими операциями. Эта концепция хороша для теории, для практики это бред и ещё раз бред.

 

diamond
Да... наверное, Вы правы... Не то, что для меня было бы очевидно, что никакие навороты не нарушат инварианту (лексикографическое увеличение состояния задачи), но похоже таки не нарушат. Либо стек должен быть бесконечным, либо код процедуры.
Booster

Не забываем, что прыжки назад запрещены. Значит копироваться вперёд придётся постоянно. Соответственно мы выйдем за пределы доступной памяти, и "бесконечный цикл" завершится.
Y_Mur

У diamond получилось более формальное объяснение.

Если речь идёт о раскрытии рекурсии по стеку, то это тривиальный способ, и получится та же рекурсия, которая в своё время вызовет переполнение. Если нет... стандартная задача - брутфорс пароля по заданному алфавиту. Перебирать пароли нужно от одного символа до заданного их количества. Соответственно нужно реализовать n вложенных циклов, где n — нефиксировано. Как Вы это сделаете без рекурсии?
Booster

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

Ну это довольно серьёзное ограничение, чтобы рекурсию называть более мощным инструментом.
aa_dav

Я бы сказал наоборот: прыжок назад - это оптимизация рекурсии только технически. Во всех остальных смыслах прыжок назад - это цикл, который нельзя использовать в претендующих на тьюринговую полноту функциональных языках.

На любой такой вменяемый компилятор найдётся маловменяемая реализация (а может даже и задача), которая не требует рекурсивного решения, но при этом не сможет быть преобразована компилятором в код, не переполняющий стек.
Y_Mur

Меня функциональные языки тоже не вдохновляют. Но наш преподаватель приводил статистику, согласно которой функциональные языки по производительности в среднем уступают тому же C++ раза в два-три, в то время как .Net со своим байт-кодом тормозит по сравнению с плюсами порядка на два-три. Это было его слово защиты в пользу функциональных языков. В общем мне как-то не очень верится в такую статистику.
Booster

Ну... по большому счёту оно и заменяется. Аппаратно, разумеется.
Что же до практики, то выкидывание циклов в функциональных языках в частности мотивируется примерно тем же, чем мотивировался в своё время запрет на goto: повышается читабельность программы, уровень абстракции, и соответственно также значительно увеличивается скорость разработки ПО.

P.S. Похоже код из поста 26 (ассемблер) (слегка модфицированная идея Booster) - это максимально возможное приближение к бесконечной рекурсии, не вызывающей переполнение стека.

 

l_inc

Почему n — нефиксировано? алфавит задан - значит количество символов в нём известно, "от одного символа до заданного их количества" тоже означает заданность.
Частный случай здесь вообще генерация последовательности:
0, 1, 2, ... 10, 11, 12, ... 21, 22 и т.д. допустим до 9999 - согласись, что рекурсия тут совершенно излишня
Аналогично любой фиксированный алфавит можно представить соответсвующей системой счисления.

 

Y_Mur

Не... тут не заданность. Скажем n - это ввод пользователя. Т.е. цикл от 1 до числа символов алфавита перебирает один символ. Два таких цикла (один в другом) - два символа и т.д. Хотя с системами счисления верно... гоню... помню, были какие-то задачи, в которых было необходимо заранее неизвестное количество друг в друга вложенных циклов... и тогда у меня были серьёзные сомнения, что эти задачи можно было реализовать нерекурсивно. Может и можно было.

 

l_inc
Предельная глубина рекурсии в этом случае будет, если не ошибаюсь, n. Ничего бесконечного. И вообще, сдается мне, можно явно проще как-то реализовать.
И, кстати, зря так про те лекции. Оттуда становится ясно, почему и когда рекурсия в грамотных компиляторах/интерпретаторах ФЯ может быть бесконечной.

И я скажу одну кощунственную для низкоуровневого форума вещь - ФЯ, на самом деле, аццке рулят. Взять, скажем, Erlang.

 

Voodoo

Example please )
Мне тоже сначала показалось что это взможно пока не попробовал примерчик слепить

 

Voodoo

Тут речь идёт об обратном утверждении: всякую рекурсивную процедуру можно преобразовать в нерекурсивную.

Можно. Y_Mur и предложил, как.

Именно так эта вещь и звучит. ИМХО, конечно. Лично я воспринимаю функциональные языки, как настойчивую попытку лишить меня понимания того, как на самом деле работает программа.
Y_Mur

Здесь речь не об этом. Насколько я понимаю, Voodoo говорит о том, каких правил нужно придерживаться, чтобы быть уверенным, что компилятор функционального языка преобразовал рекурсию в цикл.

 

В воздух тут пердеть не стоит. Честно. Хотя бы с предметом ознакомились бы для начала. Мало мальски первая же книга по ФЯ объяснит вам в первых своих главах чем рекурсия отличается от хвостовой рекурсии и как преобразовывать алгоритм из первой во вторую (при возможности), чтобы компилятор/интерпретатор делал то, что вы назвали для него "неподьемной совершенно работой". Учитесь, это на самом деле полезно.

Я далеко не фанат ФЯ, и поэтому скажу - да, ФЯ - фигня, OPAL - упал. И мы с вами дружно хохочем над этой остроумной шуткой, особенно вы, как особенный интеллектуал в сфере обсирания того чего не знаете тем, о чём слабо догадываетесь. Брависсимо, вам, мастер потной шутки!

 

l_inc

> Я бы сказал наоборот: прыжок назад - это оптимизация рекурсии только технически.

Интересно что именно это я и сказал. А что вы тут сказали "наоброт", я не понял. =)

> Во всех остальных смыслах прыжок назад - это цикл, который нельзя использовать в претендующих на тьюринговую полноту функциональных языках.

В претендующих на тьюрингову полноту функциональных языках, ЕЩЕ РАЗ ПОДЧЕРКНУ, никаких goto НАЗАД и не существует. В них есть функции, параметры, вызовы, ну и там дефиниции.... А никаих циклов и переходов назад там нет ни совсем ни вовсе - бог с вами! Там этих вещей нет ВООБЩЕ. Как нет в современном C++ оператора переключения входа в нулевой ринг - да ведь его там нет вообще!!! тем не менее программы на C++ вполне себе вызывают процедуры из ring-0.
Вы просто совершенно попутали в уме семантику некоторого языка и вопросы реализации его семантики.
Поэтому и путаница жуткая.

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

И что, собственно? Не вижу тут опровержения "что циклы круче чем функции". Абсолютно не вижу...

 

l_inc
ну да, далеко не всякая рекурсия может превращена в итерацию.
Предупреждаю сразу - я не так уж шарю в области, могу в чем-то наврать, даже сильно.

Итак, преобразованию в итеративную форму подлежит функция, рекурсивный вызов в которой является последним в ней оператором. Хороший пример преобразования рекурсии в хвостовую в вики.

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

 

aa_dav

Интересное у Вас "именно это":

Технически - оптимизация рекурсии (у меня). И технически - стандартный цикл (у Вас). Да... прямо точь-в-точь. :-P Причём эти понятия Вы сами же и противопоставили друг другу.

А зачем подчёркивать? Кто-то говорил, что существуют?

Что-то я не пониманию, кому Вы это доказываете.

Ну да... Если существует задача, которая не решается рекурсивно, зато решается итеративно (ввиду отсутствия накладных расходов на стек), то разумеется это ни коим образом не говорит в пользу итерации.

 

На самом деле рекурсия зло не столько потому, что грузит стек бесполезным хламом типа одного и того-же адреса возврата и кучи не всегда используемых аргументов - это "всего-лишь" побочный эффект и "особенности реализации" компилятора/оси и т.п.
Рекурсия зло потому что похожа на айсберг - под лаконичной и на поверхностный взгляд изящной записью в большинстве случаев скрывается очень разветвлённый и далеко не очевидный алгоритм, эквивалентный связке нескольких ваимопорождающих циклов (тривиальный случай когда рекурсия эквивалентна одном циклу следует не задумываясь заменять на цикл и не выпендриваться ). Понастоящему понять этот навороченный алгоритм можно только погрузившись в дебри отладчика. Если кто-то заявляет, что понимает любой рекурсивный алгоритм с одного взгляда на исходник - не верьте - это не понимание а "делание умного вида" ) Причём рекурсивный код практически не поддаётся оптимизации ни алгоритмической, ни низкоуровневой - как раз потому, что основная часть алгоритма скрыта в подводной части айсберга, а его поверхностная часть настолько мала, что нет места для каких бы то ни было манёвров, и даже если в отладчике видишь, множество лишних бестолковых действий, то повлиять на них, особенно из ЯВУ, весьма затруднительно.
Никакое извращённое злоупотребление goto не способно настолько запутать поведение программы, как это делает "универсальная" рекурсия, потому применять её следует в исключительных случаях, например, когда: "есть готовый алгоритм, вроде работает, а искать ему альтернативу лень/некогда и т.п."
Поэтому полный отказ от циклов и переходов в пользу рекурсии, да ещё и плюс разрешение компилятору на своё усмотрение втихаря подменять рекурсии циклами - это прямой путь в глухие и практически не отлавливаемые глюки.
А если отдельным компиляторам на простеньких программках удалось обогнать сверхтормозной NET, так это не показатель, особенно когда речь идёт о семантике языка, а не о реализации компилятора/платформы и т.п.

 

Y_Mur
одним из преимуществ функциональных языков считается возможность доказать правильность алгоритма математически.
побочные эффекты в императивных языках запутывают алгоритм гораздо больше чем рекурсия

 

l_inc

Я еще раз повторю - не нужно держать в уме вопросы технической реализации.
Это примерно что сейчас происходит, только шиворот-навыворот (пофантазируем):
а) препод убеждает ученика, что в современных ЯВУ goto не нужен и даже вреден, т.к. if/while/for прекрасно работают и без него и способствуют лучшему пониманию кода.
б) ученик спорит с преподом что это не так. доказательством он делает тот факт, что if/while/for невозможно реализовать без команды JMP процессора, которая и есть goto. Значит goto - единственно полезная вещь, а if/while/for - высокоуровневый хлам.
в) спустя годы ученик приходит на этот форум и задает вопрос "как реализовать while, только не используя JMP?" и весьма доволен тем, что ему отвечают что это невозможно.
"Так значит я всё-таки был прав" - делает вывод он, - "Без гоуту в ЯВУ нельзя!".

Таким же образом я совершенно не понимаю отчего вы решили, что ФЯ-программа на уровне реализации обязательно должна превратится в серию call-ов и ret-ов и никаких jmp! Хвостовая рекурсия - обычный приём в ФЯ и почему вы решили что реализация её должна быть обязательно сделана компилятором как call в себя - непонятно. По идее нам вообще должно быть безразлично как оно там реализуется до тех пор пока ведет себя правильным образом. А потому и "бесконечный цикл рекурсией без переполнения стека" - вполне реальное и ничему не противоречащее явление.

 

Наглядный пример к тому что я писал выше здесь.
"Простенькая" рекурентная запись, "совершенно неожиданно" привела к переполнению стека, разбор полётов показал, что на самом деле это три хитросплетённых цикла, и это не особенность реализации, а тот самый настоящий "коварный оскал рекурсии" Мастера Дзена за счёт гибкости асма кое-что соптимизировали, но оказались бессильны перед исходной бестолковостью алгоритма ("Например, при A(N,M)=A(N-1,A(N,M-1)) происходит вызов функции M раз только для того, чтобы сделать декремент M и "загадить" стек. Тоже самое с A(N,0)") см. #53 "и даже если в отладчике видишь, множество лишних бестолковых действий, то повлиять на них, особенно из ЯВУ, весьма затруднительно". А в конечном итоге альтернативный путь нашёлся и осмелюсь утверждать, что это не случайность, а фундаментальная закономерность - нерекурентный путь решения задачи существует всегда, даже если на первый взгляд он не очевиден
Программа целиком состоящая из таких "простых и универсальных" приёмов программирования - настоящее минное поле для отлаживающего и сопровождающего код )
Рекурсия действительно очень мощный иструмент, но это "мощность осколочной гранаты", которая пуляет осколки как попало, не разбирая "свой/чужой", а сила отдельных осколков (которая в конечном итоге и нужна) весьма невелика - пасует даже перед пехотной каской. Эффективный алгоритм напротив - подобен кумулятивному заряду - максимально сосредотачивает усилия на достижении конкретной поставленой цели и за счёт этого способен одолевать серьёзную броню с минимумом побочных эффектов.

GoldFinch

на практике, за редким исключением, требует серьёзной медитации, к тому же уводящей в сторону от самого процесса програмирования и при этом очень мало чего даёт, поскольку "строгое доказательство правильности алгоритма" неизбежно спотыкается на особенностях реализации, а потому не исключает ни отладку, ни стрессовое тестирование
Собственно фундаментальная вредоносность таких "доказательств" заключается в том, что отвлекает человека от наработки практического опыта приводящего к выработке "чутья на алгоритм", и подменяет это нелепой абстракцией, принципиально несовместимой ни с програмированием как таковым ни с тренировкой интуитивного восприятия кода, которое намного эфективнее "абстрактых доказательств" (которые в силу навороченности тоже могут содержать ошибки .

 

Y_Mur
функция Аккермана - это абсолютно отдельная история, я лично не уверен, что ее можно ставить в один ряд с прочими рекурсивными функциями. она такая "бестолковая" по определению. И то, где-то я видел ее вариант с хвостовой рекурсией.

 

Voodoo
Дело не в конкретной функции, а в том что рекурсия всегда скрывает истинную сложность алгоритма под простенькой записью, глядя на которую нельзя однозначно сказать -действительно это элементарная задача, или там скрывается "бестолковая по определению" супернавороченная функциональность, напичканная граблями. Потому и говорю, что рекурсия - эффективный способ безобразного запутывания алгоритма
А "безобидная хвостовая рекурсия", являющаяся альтернативным способом записи цикла, отвратительна как раз тем, что приучает бегиннерса мыслить категориями рекурсии, автоматически направляя его беззащитным (поскольку и него и мысли не возникает, что другие пути существуют) в коварные зубы остальных рекурсивных алгоритмов )

 

Ясно, что любая рекурсия может быть превращена в цикл читерским методом эмуляции аппаратного стека программным (вместо call x делаем mov eax,[our_stack_ptr] / mov [eax], <уникальный идентификатор вызываемого места> / add [our_stack_ptr], sizeof идентификатора / jmp x, вместо ret - mov eax,[our_stack_ptr] / sub eax, sizeof идентификатора / mov [our_stack_ptr], eax / movzx eax, [eax] / jmp [table + eax*4], где в table собраны возможные точки возврата). Но я склонен считать, что без подобных трюков ту же функцию Аккермана нельзя реализовать без рекурсии, она (рекурсия) там по существу. Строго сформулировать утверждение не берусь, но в реализацию хвостовой рекурсией не верю.
Ну а в "альтернативном пути" речь шла о том, что реальные ресурсы ограничены и большие значения вычислить нельзя, а для маленьких есть явные формулы. В идеальном случае переменных неограниченного размера (о которых часто и идёт речь при изучении алгоритмов) это не проходит.

 

Не по существу функции, а по исходной формулировке задачи ) Если раскрыть рекурсию в последовательность генерируемых ею чисел, то сразу станет понятно, что сгенерировать такую последовательность можно не только с помощью рекурсии, но и по другому, что собственно и сделано в конце того топика - предложена замена на обычную формулу. Аналогично здесь в #44 не буду утверждать, что этот приём есть универсальный способ замены рекурсии, но это всего лишь один из возможных приёмов - главное взглянуть на рекурсивный алгоритм со стороны, не зацикливаясь на деталях самой рекурсии и тогда альтернативные пути решения "исключительно рекурсивной" задачи найдуться и скорее всего не в единичном экземпляре