Рекурсия против петель

Question

Я пытаюсь работать с примерами на деревьях, приведенными здесь: http://cslibrary.stanford.edu/110/BinaryTrees.html Все эти примеры решают проблемы с помощью рекурсии. Интересно, можем ли мы предоставить итеративное решение для каждого из них, имея в виду, можем ли мы всегда быть уверены, что у проблемы, которая может быть решена с помощью рекурсии, в целом также будет итеративное решение. Если нет, то какой пример мы можем показать, чтобы показать проблему, которая может быть решена только с помощью рекурсии / итерации?

-

Answer 1

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

Answer 2

По моему опыту, большинство рекурсивных решений действительно может быть решено итеративно.

Это также хороший метод, поскольку рекурсивные решения могут иметь слишком большие накладные расходы на использование памяти и ЦП.

Answer 3

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

Answer 4

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

Прочитайте этот вопрос для доказательства.

Answer 5

Будучи «старым парнем», я вспоминаю о том, что рекурсивные синтаксические анализаторы проще в написании, но итеративные парсеры на основе стека работают лучше. Вот статья, которая, кажется, поддерживает эту идею с помощью метрик:

http://www.texttoolkit.com/index.php?option=com_content&view=article&catid=35%3Atechnology&id=60%3Abeyond-recursive-descent&Itemid=55

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

Answer 6

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

Вы не можете создавать дополнительные циклы, но вы можете создавать новые темы с помощью рекурсии.