Рекурсия по сравнению с циклами
Я пытаюсь сделать работу с примерами на Деревьях, как дали здесь: http://cslibrary.stanford.edu/110/BinaryTrees.html Эти примеры, все решают проблемы через рекурсию, интересно, можем ли мы предоставить повторяющееся решение для каждого из них, значения, можем мы всегда быть уверенными, что проблема, которая может быть решена рекурсией, будет также иметь повторяющееся решение в целом. В противном случае, что пример мы можем дать для показа проблемы, которая может быть решена только рекурсией/Повторением?
--
6 ответов
Единственная разница между итерацией и рекурсией на компьютере заключается в том, используете ли вы встроенный стек или стек, определенный пользователем. Так что они эквивалентны.
По моему опыту, большинство рекурсивных решений действительно может быть решено итеративно.
Это также хороший метод, поскольку рекурсивные решения могут иметь слишком большие накладные расходы на память и потребление ресурсов ЦП.
Как "старичок", я вспоминаю, как узнал, что рекурсивные парсеры спуска легче писать, но что итеративные парсеры на основе стека работать лучше. Вот статья, которая, кажется, поддерживает эту идею с помощью показателей:
Следует отметить упоминание автором переполнения стека вызовов рекурсивным спуском. Итеративная реализация на основе стека может быть намного эффективнее с точки зрения ресурсов.
Рекурсия имеет то преимущество, что она будет продолжаться без известного конца. Прекрасным примером этого является настроенная и многопоточная быстрая сортировка.
Вы не можете создавать дополнительные циклы, но можете создавать новые потоки с помощью рекурсии.
Рекурсия и итерация - это два инструмента, которые на очень фундаментальном уровне делают одно и то же: выполняют повторяющуюся операцию над определенным набором значений. Они взаимозаменяемы в том смысле, что нет проблемы, которую нельзя было бы каким-либо способом решить только одним из них. Однако это не означает, что один не может быть более подходящим, чем другой.
Поскольку рекурсия использует неявный стек, в котором хранится информация о каждом вызове, вы всегда можете реализовать этот стек самостоятельно и избежать рекурсивных вызовов. Итак, да, каждое рекурсивное решение можно преобразовать в итеративное.
Прочтите этот вопрос для доказательства.