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