Не прямое решение задачи.

[Olegator]

Можно ли решать программистскую задачу как в том анекдоте про математиков и физиков:
Анекдот:
Первая задача. Надо согреть воду в кастрюле. Дано: пустая кастрюля, кран. И дано решение этой задачи: Наливается вода из крана в кастрюлю. Кастрюля ставится на огонь и вода подогревается.
Вторая задача. Надо согреть воду в кастрюле. Дано: наполненная водой кастрюля, кран. А решения нет.
Что делает физик. Просто ставит кастрюлю на огонь и вода подогревается.
Что делает математик. Выливает из кастрюли воду. И таким образом приводит начальные условия этой задачи к начальным условиям первой задачи, у которой решение уже существует. И дальше не думая, действует по решению первой задачи.

Можно ли так же сделать в случае с рекурсией и итерацией.

Т.е., допустим, для меня решить задачу рекурсивно проще, чем итеративно, но выходит расточительно по отношению к ресурсам компьютера. Я делаю рекурсивно, а потом переделываю итеративно. Не выйдет ли так проще.

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

[Alf]

Olegator, опытный проектировщик тем и отличается от дилетанта, что подходит к задаче творчески.

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

1. Быстренько набрасываешь решение, которое временно затыкает дыру.
2. Выиграв время, спокойно решаешь задачу достаточно приемлемым путем.
3. Параллельно обдумываешь будущее задачи, если она имеет будущее (например, стыковку с другими системами или расширение ее применимости).

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

Во-вторых, в программировании действует своя разновидность закона Парето, согласно которой примерно 10% кода занимает примерно 90% времени выполнения программы. Отсюда следует, что далеко не все, что напимано неоптимально, непременно следует оптимизировать. Например, у тебя есть массив из 10 элементов, в котором ты ищешь один раз простым перебором. Ты можешь показать класс кодирования, реализовав его в виде ассоциативного массива с быстрым доступом, сбалансированного В-дерева и т.д. В результате окажется, что программа стала выполняться на 50 микросекунд быстрее при общем времени выполнения полчаса. То есть твое рабочее время, потраченное  на оптимизацию, было потеряно практически впустую.

Я в своей группе практикую следующий подход:

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

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

[Olegator]

Я спрашивал про разделение не по времени, а по мышлению. Как в анекдоте. Ну не вижу я, что можно сразу поставить кастрюлю на огонь и всё тут. Вот и привожу начальные условия второй задачи к начальным условиям первой. Т.е. если я бы мог совершенно (или почти совершенно) формально из рекурсивно решённой задачи сделать итеративно решённую. Это ведь проще по отношению к тем задачам которые рекурсивно решаются проще.

[Alf]

Я как раз не о разделении времени говорил, а об использовании имеющегося задела (возможно, неоптимально работающего).

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

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

[Olegator]

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

Я как раз не о разделении времени говорил, а об использовании имеющегося задела (возможно, неоптимально работающего).

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

Всё это я прекрасно понял.
Мне не нужно пробовать потом реализовывать итеративный вариант.
Допустим, я вообще, в принципе, не могу решить задачу итеративно. Т.е. рассмотрим совсем крайний случай, чтобы ты понял, что я имею ввиду. Но я могу решить рекурсивно. Могу преобразовать (именно преобразовать, а не сделать заново) рекурсивную задачу в итеративную. И таким образом я всё-таки прихожу к задаче решённой итеративно.
Т.е. есть три задачи.
1. Придти к решению итеративно. – не могу решить.
2. Придти к решению рекурсивно. – могу решить.
3. Преобразовать рекурсивное решение в итеративное – могу решить.

Представь себе треугольник, в котором гипотенуза – первая задача, а катеты вторая и третья задача.

[Finch]

А можно примерчики таких задач. Даже стало интересно. Что за такие задачи, по которым рекурсивный метод сразу очевиден. Для меня очевидна рекурсия в основном в задачах по проходу деревьев (директорий и т.д.). Итерактивные методы здесь намного сложнее. Поскольку самому приходится организовывать своеобразный стэк состояний.

[Alf]

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

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

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

[Olegator]

Возможно по двум катетам получится проще. Не знаю. Это моё предположение. Надо попробовать с обходом дерева, как Finch сказал.
Хотя может есть и более удачные примеры такого подхода.

[Alf]

Дерево так дерево, надо же с чего-то начинать. Только полезно было бы сделать такую вещь: реализовать и рекурсивную, и итеративную версии и сравнить их по объему и сложности исходного кода, по скорости работы и требуемым ресурсам. Может оказаться, что возня с преобразованием рекурсии в итерацию не имеет никакого смысла.

Если нет на примете задачи, могу предложить такую: построить дерево каталоговой структуры диска, в котором для каждой ветки хранится суммарный размер файлов в ней. IMHO такая штука пригодится, если хочешь разобраться, куда подевалось дисковое пространство. Сделай два варианта, сравним.

[Finch]

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

[Alf]

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

[Olegator]

Квадратное ур-ие
Смотря каким способом решать. Если аналитически, то да. А если численно то методом деления отрезка пополам решается как раз рекурсивно и итеративно. Правда для полинома второй степени это наверно избыточно.

[Alf]

Квадратное уравнение - методом деления отрезка?.. Сколько лет программирую, но такого фокуса еще не видел

Это покруче, чем воду из кастрюли выливать...

[Olegator]

Ладно, соглашусь с Alf`ом. Перебор. Решать таким способом квадратное уравнение кроме как в учебных целях не стоит. Отрезок в котором находится решение замучаешся искать. Только если точно знаешь где этот отрезок находится.

[Alf]

Так любую задачу легче решать, когда решение известно заранее

[Olegator]

Не решние а отрезок в котором находится решение

[Alf]

Оно заведомо находится на отрезке от минус бесконечности до плюс бесконечности. Легче нам от этого?

[Olegator]

Продолжу основную тему.
Так можно ли совершенно формально преобразовать рекурсию в итерацию.
Ты вот говоришь:

Вообще-то в принципе рекурсия и итерация эквивалентны - для каждого рекурсивного алгоритма существует парный итеративный, и наоборот.

[Alf]

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

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

[npak]

Вообще-то в принципе рекурсия и итерация эквивалентны - для каждого рекурсивного алгоритма существует парный итеративный, и наоборот.

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

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

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

[Alf]

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

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

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

P.S. По ходу пришла мысль - FIFO можно имитировать двумя стеками LIFO, сначала набив первый, а потом переложив элементы во второй. Полнейшее уродство, но ведь теория вовсе не обещает равной эффективности итерации и рекурсии, речь ведь только о принципиальной реализуемости.