люди, как рекурсию сделать?

чеж вы так ругаетесь то?

>иди в школу или садик, если тебе не больше 10 лет, можешь попробовать поступить ко мне, если сможешь конечно ..

Опят личные наезды, с такими нервами в общество выходить нельзя :) Уважаемый lg, вами несколько раз было употреблено слово ЭФФЕКТИВНОСТЬ. Как человек образованый (по вашим заявлениям) вы должны понять что ЭФФЕКТИВНОСТИ без критериев не бывает. Вы так и не объяснили что вы имели в виду говоря о том что "рекурсия эффективнее всего". Вообще нашей "беседе" вы сделали множество голословных и неподтвержденных утверждений.

нет, предельное число есть конечно... рекурсия единственно возможное решение. Потом, если я опишу задачу полностью, я засвечусь тут на лоре, а пока пошифроваться хочу :)

А вообще, longjmp/setjmp. :)

Как-то так:

[...]
jmp_buf continuation;
if(setjmp(continuation) == 0) {
    superRecurrent(params, continuation);
}
/* Сюда выходим */
[...]


void superReccurent(params, jmp_buf continuation) {
   ...
   if(someCondition) {
        superRecurrent(params);
   } else {
       // Выходим из мега-рекурсии
       longjmp(continuation, 1);
   }
   ...
}

Но это не очень хороший вариант.

>по моему таки есть ситуации где рекурсия гораздо удобнее (напр обработка массивов ПРОИЗВОЛЬНОЙ размерности)

К сожалению для обработки массивов произвольной размерности с помощью рекурсии необходима идеальная машина с объемом памяти (стеком) стремящемся к бесконечности. Во первых пямять необходима если предполагается не просто проход по массиву а выполнение над данными каких либо действий требующих введения временных переменных - локальные переменные. Во вторых память необходима для сохранения последовательности рекурсивных вызовов. Для достижения приемлимой производительности наша машина должна будет обладать еще и близкой к 0 латентностью памяти. И если бы такая машина была циклический обход по критериям производительности, объема программы и используемой был бы на много эффективнее.

>Например, для корректной реализации Scheme стек в случае хвостовой рекурсии _обязательно_ _не_ будет расти (не совсем корректное утверждение, но фактически это так)

А если не секрет у _чего_ в Scheme не будет рости стек?? Это вопрос-провокация, сначала подумайте :)

ЗЫ.Предупреждал меня ананимус, ой предупреждал.

>А если не секрет у _чего_ в Scheme не будет рости стек?? Это вопрос-провокация, сначала подумайте :)

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

>не потребляет память.

буквоедство: не потребляет дополнительную память

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

Уитывая что Shceme интерпретируемый язык, поддержка рекурсии в интерпритаторе может быть реализована как угодно, хоть переводом к промежуточному коду циклического вида:)

>Уитывая что Shceme интерпретируемый язык

Этого не требуется спецификацией. Более того, есть реализация Scheme на C/JVM backend-е. Bigloo называется. Правда, она не properly tail-recursive (вызов continuation-а можно делать только из его dynamic extent-а, т.е из "глубины" вызовов :) ), но это скорее ограничение JVM.

>, поддержка рекурсии в интерпритаторе может быть реализована как угодно, хоть переводом к промежуточному коду циклического вида:)

Более того, я приводил пример на C, где хорошо видно оптимизация хвостовой рекурсии gcc. Тут даже ссылка пробегала, там как раз про оптимизацию хвостовых вызовов в gcc было написано. От реализации Scheme просто требуется, чтобы такая оптимизация проводилась всегда. Вот и все.

>Правда, она не properly tail-recursive (вызов continuation-а можно делать только из его dynamic extent-а, т.е из "глубины" вызовов :) )

Поправка: то, что в скобках и то, что вне скобок - никак не соотносится (т.е я неверную импликацию привел). :)

>Более того, я приводил пример на C, где хорошо видно оптимизация хвостовой рекурсии gcc

Вот то то и дело :) Как видно из вашего примера С оптимизирует рекурсию путем перевода ее в _циклический_ вид. Никаких вызовов функций, нет и в помине. Я лишь отстаиваю мысль что самому использовать циклический вид записи алгоритма вместо рекурсивного полезнее, ибо не все компиляторы одинаково полезны и умны. А не оптимизированная рекурсия ,не преобразованая в цикл, а сохранившаяся в виде вызовов функций со всеми накладными расходами не эффективна по памяти и производительности.

Не стоит полагаться на "умный" компилятор, надо не "тупить" самому.

Это конечно не относится к языкам изначально ориентированным на рекурсивную структуру программ (lisp и друзья).

Определение рекурсии захотел? Дуй сюды: http://en.wikipedia.org/wiki/Fixed_point_combinator

> Как видно из вашего примера С оптимизирует рекурсию путем перевода ее в _циклический_ вид.

Нет там никакого цикла - обычные переходы.

> Никаких вызовов функций, нет и в помине.

Никакого loop нет и в помине.

> Я лишь отстаиваю мысль что самому использовать циклический вид записи алгоритма вместо рекурсивного полезнее

Циклический вид записи использовать _вредно_, надо использовать goto, а не рассчитывать на умный компилятор.

Про практику - читать caml-list, там были примеры про Itanium и Xeon.

ну хоть один стоящий пост, спасибо!

> Вот то то и дело :) Как видно из вашего примера С оптимизирует рекурсию путем перевода ее в _циклический_ вид.

ну конечно! мы тебе про это долдычим долдычим ..

> Не стоит полагаться на "умный" компилятор, надо не "тупить" самому.

верно!

----------- > Опят личные наезды

где? у меня все советы дружественные если ты не заметил .. то что я посоветовал человеку пойти поучиться еще не значит что я на него наехал - я дал ему дельный совет

> вами несколько раз было употреблено слово ЭФФЕКТИВНОСТЬ.

было

> Как человек образованый (по вашим заявлениям)

где это мои заявления о моей образованности? И какое отношение образованность имеет пониманию рекурсии?

> вы должны понять что ЭФФЕКТИВНОСТИ без критериев не бывает. Вы так и не объяснили что вы имели в виду говоря о том что "рекурсия эффективнее всего".

я не говорил что рекурсия эффективней всего, я говорил что рекурсия эффективней любого лупа ..

хорошо давай определимся. Я говорю с точки зрения программирования и реализации математической модели. Меня не интересует оптимизированный кодинг под конкретный электрочайник.

В основе любой программы на любом яп лежит алгоритм который задает действия программы для конкретных условий. В основе любого алгоритма лежит некий математический тезис.

Эффективность алгоритма определяется его близостью к математическому тезису используемого для этого алгоритма.

Конечный вариант программы это некий набор команд для модели компьютера. То есть программа лимитированна терминами комьютера. Эффективность программы в терминах модели компьютера определяется использованием эффективных средств модели комьютера. Эффективные средства модели комьютера - это операции наиболее удобные/быстрые для исполнения этой моделью комьютера ..

теперь приведи хоть один пример математического тезиса в котором есть интеративность :)

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

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

рекурсия дает больше простора для преобразования на уровень модели комьютера, нежели лупы

> Вообще нашей "беседе" вы сделали множество голословных и неподтвержденных утверждений.

так и есть, если кто-то заинтересуется он сам будет искать подтверждения/опровержения. Зачем мне то это делать? я никому ничего нихочу доказывать если ты не понял, я всего лишь хочу подтолкнуть народ к анализу вещей

Жаль что мы сразу друг друга не поняли :)

И что не сразу все поняли о Moridin :))))

2Moridin:

Виталий, ты чтоль?

> Определение рекурсии захотел? Дуй сюды: http://en.wikipedia.org/wiki/Fixed_point_combinator

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

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

Э-м-м-м. Не понял. Что это означает, поясни?

Лямбда исчисление эквивалентно машине Тьюринга.

Вычислим-шмудислим... Какая хер разница? Спросили определенеи рекурсии - дал определение, чего ещё надыть?

Наконецто ушли от стратегии "обосри ближнего своего" и начался разговор :)

>ну конечно! мы тебе про это долдычим долдычим ..

Нет уж позвольте это я вам долдычу :)!

>где? у меня все советы дружественные если ты не заметил .. то что я посоветовал человеку пойти поучиться еще не значит что я на него наехал - я дал ему дельный совет

Эх! Ну если я послал кого-нибудь на @#$ не взыщите, я просто пытался сказать что занят:)

>где это мои заявления о моей образованности? И какое отношение образованность имеет пониманию рекурсии?

Ладно, я не настаиваю :) Только что-то много заявлений о моей образованности. Прямое.

>я не говорил что рекурсия эффективней всего, я говорил что рекурсия эффективней любого лупа ..

Опять критерии забыли, чуть больше конкретики пожалуйста, по каким критериям рекурсия эффуктивнее лупа?

>хорошо давай определимся.

Давай, давно пора.

>Я говорю с точки зрения программирования и реализации математической модели.

Я тоже говорю с точки зрения программирования, но причем тут модель? Мат. модель это описание _интересующих_ свойств и процессов некоторого объекта. Мат. модель строится с целью моделирования и может не полностью, а лишь в исследуемой части, совпадать с объектом. См. ту же Теорию вычислительных систем по поводу рассчета сложности и производительности алгоритмов. Поэтому мат. модель алгоритма может дать нам знания о некоторых свойствах этого алгоритма. То что могло бы называться полной и точной моделью алгоритма на некотором языке принято называть его реализацией на этом языке.

>В основе любой программы на любом яп лежит алгоритм который задает действия программы для конкретных условий

Не обязательно, например в языках VHDL и Verilog широко используется структурный подход, при котором описывается именно структура вычислительного утсройства но никак алгоритм его поведения. Сам лично на С++ реализовал протокол РРР(HDLC,PPP,LCP,LQP,NCP) в автоматном виде, алгоритмя и не разбереш только таблицы. В основе программы может лежать и более абстрактная субстанция нежели алгоритм.

>Эффективность алгоритма определяется его близостью к математическому тезису используемого для этого алгоритма.

Не проверял, может быть, спорно. Можно конкретный пример?

>теперь приведи хоть один пример математического тезиса в котором есть интеративность :) Интегрирование :) Дифференциальное исчисление :) >заметь также что даже не смотря на то что рекурсия превращается в итеративность в модели комьютера, Это зависит от средств компиляции, канонически без оптимизации и циклизации %) рекурсия тянет накладные расходы как по памяти так и по скорости. >она работает часто так же эффективно, а иногда даже эффективней нежели изначальная итеративная форма .. Опять:) Ну где пример?

KIV (20.01.2005 15:11:17):

> То что могло бы называться полной и точной моделью алгоритма на некотором языке принято называть его реализацией на этом языке.

lg просто утверждает, что в процессе перевода реализации алгоритма на некотором языке в реализацию его в машинных кодах преимущество имеет рекурсивные алгоритмы.

Я правильно понял?

>рекурсия дает больше простора для преобразования на уровень модели комьютера, нежели лупы

Вообще чума. Как докажите? :) Уровень модели компьютера это ISA имелась ввиду? Так со времен Фон Неймана и Тьюринга, команды переходы - базовая сотавляющая практически любой ISA. Команды переходов дают достаточно большой простор по организации циклов :) уж поверьте:)

Первый раз слышу чтобы понятие рекурсии опускали до уровня ISA, так пройдемте к микрокоду, там тоже рекурси.. тьфу переходы есть и условные есть :) и бузусловные! Так и вижу в учебниках по какому нибудь ассемблеру гда так 2020: jmp - команда организации рекурсивных переходов. Говорить о рекурсии на столь низком уровне не стоит, не грамотно как то.

WFrag (20.01.2005 14:59:29):

> Э-м-м-м. Не понял. Что это означает, поясни? Лямбда исчисление эквивалентно машине Тьюринга.

Современные процессоры ближе к машине Тьюринга и по своей прирове итеративны.

Moridin (20.01.2005 15:06:16):

> Спросили определенеи рекурсии - дал определение, чего ещё надыть?

Ну, вообще-то, вопрос, скорее, был риторическим.

Кстати, ты НЕ дал определние, Ты дал ссылку на топик, пройдя по которой можно найти ссылку на другой топик, в котором приводится определение рекурсивных функций. А в соседнем топике можно найти "напальцевые" рассуждения о рекурсии.

2KIV:

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

Либо подробнее формулируй, либо вообще не пиши. Сейчас опять ругань начнется...

>lg просто утверждает, что в процессе перевода реализации алгоритма на некотором языке в реализацию его в машинных кодах преимущество имеет рекурсивные алгоритмы.

Вот я что-то не очень понял. Рекурсивный алгоритм - это одно, а рекурсия в реализации это другое.

Алгоритм понятие абстрактное. Рекурсия в коде это весьма неприятная штука, которй надо избегать в большинстве случаев: кодировать рекурсивные алгоритмы циклами :) но лучше самому, не полагаясь на компилятор.

алгоритмы существуют без программ, программы это реализации алгоритмов.

написание программ не реализующих какой либо алгоритм называется кодингом

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

все с меня хватит, написано уже достаточно

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

>Либо подробнее формулируй, либо вообще не пиши. Сейчас опять ругань начнется...

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

KIV (20.01.2005 15:29:45):

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

Не совсем точно выразился.

...в процессе перевода реализации алгоритма на некотором языке в реализацию его в машинных кодах преимущество имеет реализация, используюшая рекурсию.

Кстати, мне это напоминает спор "FOTRTRAN vs. C".

KIV (20.01.2005 15:36:59):

> ...алгоритм может быть описан абстракциями более высокого уровня - автоматами например.

Ты мешаешь в кучу термины из различных областей.

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

>в процессе перевода реализации алгоритма на некотором языке в реализацию его в машинных кодах преимущество имеет реализация, используюшая рекурсию

Рекурсия на уровне машинных кодов? Это как? И что отличает ее от циклов?

>Ты мешаешь в кучу термины из различных областей. Когда в одном предложении встречаются слова "алгоритм" и "автомат", то ...

Учитывают контекст разговора, как и при рассмотрении любых других терминов :). Ты же понял о чем я.

Ну не писатель я, читатель я %)

>Как видно из вашего примера С оптимизирует рекурсию путем перевода ее в _циклический_ вид.

Ты не догоняешь. Ничего он никуда не переводит. Он просто реализует вызов ф-ии jmp-ом.

>самому использовать циклический вид записи алгоритма вместо рекурсивного полезнее ... не оптимизированная рекурсия ... сохранившаяся в виде вызовов функций со всеми накладными расходами не эффективна

Давай напишем правильный обход графа в виде цикла и рекурсивно. И посмотрим, насколько он будет эффективнее. Тебе _придется_ сохранять где-то список уже обойденого, и распределять под это память. Большой вопрос, что скушает больше ресурсов - хранимые в стеке адреса возврата, или управлющие структуры "malloc"-а.

И давай сравним потребовавшееся время.

KIV (20.01.2005 15:57:29):

>>в процессе перевода реализации алгоритма на некотором языке в реализацию его в машинных кодах преимущество имеет реализация, используюшая рекурсию

> Рекурсия на уровне машинных кодов? Это как? И что отличает ее от циклов?

Еще раз:

Алгоритм реализован на языке Це.

Компилятор переводит реализацию алгоритма на Це в реализацию этого же алгоритма в машинных кодах.

Что тебе тут пытаются втолковать: Лучше переводятся те реализации, которые используют рекурсию вместо итераций.

Что ты пытаешься втолковать: На языке Це это не так. Лучше переводятся те реализации, которые используют итерации вместо рекурсии.

Очевидно, однозначного ответа нет. Можно так нагородить реализацию, что ни один компилер не разгребется. Кроме того, очевидно, ответ зависит от компилятора, алгоритма, железяки; даже от индивидуального стиля кодирования.

Короче, весьма похоже на holly war "Фортран vs. Си".

>Ты не догоняешь.

Да уж вас догонишь! А тебе советую все таки сначала тему всю прочитать а потом уже писать, а то уже повторяешься.

>Ничего он никуда не переводит.

Процесс трансляции с одного языка на другой нельзя назвать "переводом"?? Новость! :)

>Он просто реализует вызов ф-ии jmp-ом.

И по этой реализации ты можешь что-то сказать относящееся к эффективности рекурсии :)? Круто!

>Давай напишем правильный обход графа в виде цикла и рекурсивно. И посмотрим, насколько он будет эффективнее. Тебе _придется_ сохранять где-то список уже обойденого, и распределять под это память.

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

В этой задаче есть более простое решение, слышал небось о разряженных матрицах и таблицах смежности и трансцедентности :)

>Алгоритм реализован на языке Це.

Ага.

>Компилятор переводит реализацию алгоритма на Це в реализацию этого же алгоритма в машинных кодах.

Ага.

>Что тебе тут пытаются втолковать: Лучше переводятся те реализации, которые используют рекурсию вместо итераций.

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

>Что ты пытаешься втолковать: На языке Це это не так. Лучше переводятся те реализации, которые используют итерации вместо рекурсии.

Нет. я пытаюсь сказать :) что действие термина рекурсия ограничивается областью языков программирования и нефиг пихать код в машинных командах как пример эффективности рекурсии. И что рекурсия - зло, ибо в случае "тупого" компилятора она приведет к большим накладным расходам, а то и неработоспособности программы за счет переполнения стека. Поэтому лучше ее избегать. Все подробности выше:)

>Тебе тоже приидется сохранять где-то список уже обойденного, и распределять под это память

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

>В этой задаче есть более простое решение

Так они всегда есть. Только их иногда искать приходится. Что может оказаться сильно сложнее.

Плюс задачи разные бывают. Можем quicksort обсудить:-)

>рекурсия - зло, ибо в случае "тупого" компилятора она приведет к большим накладным расходам, а то и неработоспособности программы за счет переполнения стека

1. В этом случае зло не в рекурсии а в тупом компиляторе:-) Это он сгенерил код, переполнивший стек.

2. Излишняя зацикленность на циклах может привести к потере средств к существованию, вследствие провала сроков сдачи проекта:-)

Ню ню. Fixed point combinator - и есть формальное определение понятия рекурсии. Другого нет. Вот блин - такой безграмотный, а модератор. Совсем ЛОР выродился...

>В этом случае зло не в рекурсии а в тупом компиляторе:-) Это он сгенерил код, переполнивший стек.

Неее, в этом случае зло в "тупом" программисте который не умеет пользоваться своими инструментами:) Кто сказал что код будет обязательно компилиться его автором или одним и тем же компилятором или для одной и той же платформы? Вообще, если абстракция (такая как рекурсия) не имеет четкой и однозначнй трактовки, то это плохая абстракция. :) ЗАМЕТЬТЕ! Я не говорю про специальные случаи когда окружение специально ориентировано на исполнение рекурсивного кода, такие как языки lisp и scheme.

>Излишняя зацикленность на циклах может привести к потере средств к существованию, вследствие провала сроков сдачи проекта:-)

Точно, у настоящего джентельмена все в меру :)

Moridin (20.01.2005 18:01:10):

>Fixed point combinator - и есть формальное определение понятия рекурсии. Другого нет.

Все же у тебя с логикой напряженка, в отличие от фантазии ;)

На просьбу дать общее определение рекурсии (в контексте разговора о машинных кодах) ты отсылаешь на сайт, где:

1) такого определения нет, зато есть,

2) определение fixed point combinator -- концепции, с помощью которой рекурсия осуществляется в контексте Лямбда-исчисления.

KIV (20.01.2005 17:24:17):

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

Видимо, ты просто не понял. Именно про это и говорили.

>>Что ты пытаешься втолковать: На языке Це это не так. Лучше переводятся те реализации, которые используют итерации вместо рекурсии.

> Нет. я пытаюсь сказать :) что действие термина рекурсия ограничивается областью языков программирования и нефиг пихать код в машинных командах как пример эффективности рекурсии. И что рекурсия - зло, ибо в случае "тупого" компилятора она приведет к большим накладным расходам, а то и неработоспособности программы за счет переполнения стека. Поэтому лучше ее избегать.

Почему "Нет", если из дальнейших твоих слов следует "Да"?

Ладно, я свою точку зрения сформулировал.

>Неее, в этом случае зло в "тупом" программисте

Спорим я могу написать такой компилятор, что любой достаточно длинный цикл будет вываливаться по нехватке стека :-)

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

Осмелюсь заметить, что основная фишка рекурсии не в том, что компилятор может (или не может) её эффективно представить в машинные коды, а в том , что некоторые алгоритмы по своей сути рекурсивны. Да, их можно реализовать с помощью циклов, но это будет уродливый и вычурный код. Его будет сложно писать/читать/поддерживать. А это зачастую важнее, чем 0.005% производительности.

P.S. Обсуждать преимущества и недостатки рекурсии полиморфно по задаче, яп и компилятору мягко--говря не умно.

P.P.S. Спасибо за внимание.

>Нет. я пытаюсь сказать :) что действие термина рекурсия ограничивается областью языков программирования

GNU

Классный тред. Смешной какой-то.

Жаль Антихриста не было. ;-|)