Задачка

[Anonymous]

а, дошло!  

______
1153

[grozny]

Был уверен, что это не так, но захотелось убедиться воочию. в предыдущую программку ввел "слово" размером 50. Проскочила.
Длиннее было лень буквы считать, тем более что наверняка этот предел уж куда больше.

да не настаиваю, что для данной задачи рекурсивное решение - непригодное с практической точки зрения. Всё зависит от граничных условий. 50 буковок - мало, конечно, 1 Мб стэк не вычерпать. И разницы в скорости не ощутить.

А чё, я разве утверждал, что реверсия 50 буковок исчерпает стэк? Если так, то неясно выразился. По-моему, я приводил пример из разбиения отрезков в несколько тыщ отрезков на интерацию и 6-7 итераций на отбой...

Вот фразы на немецком, например, знаш какие длинные бывают - на 200 символов.

А вот попробуй, реверсировать текст "Войны и Мир", например. Всего-то пара мегабайт.

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

Если не лень, то сравни время обработки набора из, ну скажем, 100000 случайных слов твоего любимого размера (50? ) рекурсивным и развёрнутым алгоритмом.

Мне - лень, 8)  поэтому нагло утверждаю, что рекурсия будет медленнее раза эдак в 3 минимум.

[Alf]

А чё, я разве утверждал, что реверсия 50 буковок исчерпает стэк? Если так, то неясно выразился.

Скорее всего, действительно неясно. Ибо фраза "Глубина рекурсии в MSVC 6.0 реально то ли 6, то ли 8, но всяко меньше 10" действительно может быть понята по-разному. Я воспринял это как глубину вызова, а что имел в виду ты?

Вот фразы на немецком, например, знаш какие длинные бывают - на 200 символов.

Именно это, кстати, мне и пришло в голову, когда писал об ограничениях программы. Ну что ж, если на перевернутые тексты создастся повышенный спрос, выпустим специальную версию для Германии с увеличенным стеком  
А если серьезно, то на один вызов уходит немного меньше 100 байт. Думаю, и 20-килобайтный стек современный комп выделить сумеет.

А вот попробуй, реверсировать текст "Войны и Мир", например. Всего-то пара мегабайт.

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

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

Кто же спорит. Если нужна жесткая оптимизация по времени выполнения, то однозначный выбор в пользу итерации. Хотя наперед тут я бы не зарекался. Во всех представленных итерационных алгоритмах присутствуют либо вызовы библиотечных функций для определения длины цепочки, либо собственные заменители, а они тоже не мгновенны.

Если не лень, то сравни время обработки набора из, ну скажем, 100000 случайных слов твоего любимого размера (50? ) рекурсивным и развёрнутым алгоритмом.

Давай только выберем, какой из вариантов берем за эталон итеративного подхода. Их много накидали все-таки. С рекурсией проще - выбирать не из чего.

[Kuzmich]

Объясните пожалуйста как это понимать:
(char* p) понятно, а что значит (char* &p)  :?:

[Alf]

Объясните пожалуйста как это понимать:
(char* p) понятно, а что значит (char* &p)  :?:

Я так понял, вопрос ко мне? Проглядел другие варианты, ни у кого больше не нашел эту конструкцию.
Сам по себе значок амперсанда & означает оператор поименования (получения ссылки). Если раньше не приходилось сталкиваться, то проще всего представить его себе как обратный к оператору разыменования *. Наверное, это выглядит сумбурно, поэтому поясню небольшим примером:

Код:

SomeType st; // переменная какого-то типа
SomeType *stp; // указатель на тот же тип
...
stp = &st; // присвоили stp ссылку на st
// отныне stp указывает на st,
//   т.е. *stp и st на самом деле одно и то же

В данном случае конструкция (char* &p) означает, что я передаю в функцию указатель на char по ссылке.
Дело в том, что параметры в С и С++ передаются в функцию по значению, т.е. функция получает копию значения аргумента. Таким образом функции защищают программу от побочных действий (правила хорошего тона диктуют явный возврат значения через результат функции, но не всегда так получается).
Передавая указатель на char по ссылке (фактически передается адрес указателя), я получил возможность в качестве побочного эффекта функции продвигать его на следующий символ, что в данном случае пришлось весьма кстати.
Надеюсь, не запутал еще сильнее?

[grozny]

А чё, я разве утверждал, что реверсия 50 буковок исчерпает стэк? Если так, то неясно выразился.

Скорее всего, действительно неясно. Ибо фраза "Глубина рекурсии в MSVC 6.0 реально то ли 6, то ли 8, но всяко меньше 10" действительно может быть понята по-разному. Я воспринял это как глубину вызова, а что имел в виду ты?

Да, это глубина вызова, но для моей задачи (а не для ревервирования слов), которую я реализовал под MSVC 6 (покрытие отрезков) . Перечитал свой мессадж - и вправду непонятно.  :oops:

Как было: быстренько написал "красивое" рекурсивное решение, протестировал на простеньких случаях (10-20 отрезков) - всё отлично, но на первом же боевом случае (5-6 тыщ отрезков) задачка упала в рекурсии (на глубине то ли 6, то ли 8) и пришлось разворачивать рекурсию в цикл.

А вот попробуй, реверсировать текст "Войны и Мир", например. Всего-то пара мегабайт.

уточняю условие  :twisted: - вся "Война и Мир" - одно слово. Мой пойнт в том, что реализация рекурсии - всегда хрупкая и малопредсказуемая программа. Т.е. малейшие модификации граничных условий убивают твою программу (что часто бывает в реальной жизни, ага - назавтра приходит заказчик  и говорит, что слова у пигмейском языке бывают и 1000 буковок, и вообще он задумывается над реверсированием Торы в 10 книгах .

Применение рекурсии даёт неустойчивое решение к вариации граничных условий, учёно выражаясь.

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

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

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

Что там у нас? один вызов strlen() на слово (не глядя в код). Против рекурсивного вызова ф-ции на каждой букве. Те самые разы.

Давай только выберем, какой из вариантов берем за эталон итеративного подхода. Их много накидали все-таки. С рекурсией проще - выбирать не из чего.

да пофигу - какой нравится. Я ж утверждаю, что они в разных скоростных категориях. Ну мой, например  

[Alf]

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

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

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

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

[grozny]

Мизерная такая вариация граничных условий, на каких-то жалких 6 порядков

Не, неверная аналогия. Главная задача у авто - ездить, а не груз выдерживать. И вариация граничных условий - проехать километр опытному образцу или триста тыщ серийному - вполне реальна.

Возьмём берцовую кость человека - она выдерживает до 2-3 тонн, хотя в реальной жизни нагрузка не превышает пары сотен кг.

Так что сильная вариация (3-6-20 порядков) прямых входных параметров всегда имеет смысл и должна учитываться. Тем более, что альтернативный рекурсии метод масштабируется намного луче.

Тем не менее, экстремизм - вредная вещь. Рекурсия, как и goto, должна быть в арсенале любого программиста - бесспорно. Можно жить и без того и без другого, но зачем ограничивать? Важно понимать, чем ты рискуешь (стабильностью продукта) и что теряешь (масштабируемость), применяя рекурсию.

на том и порешим.  

На ЛИСПе (или Прологе) можно написать *всё* и программа для машины Тьюринга представима рекурсией *всегда*.

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