Можно ли реализовать рекурсивный алгоритм с помощью итератора?

Question

Я дал дерево, как это:

http://www.seqan.de/dddoc/html/streePreorder.png http://www.seqan.de/dddoc/html/streePreorder.png

я могу получить доступ к каждому узлу с помощью следующего оператора.

// postorder dfs
Iterator< Index<String<char> >, BottomUp<> >::Type myIterator(myIndex);
for (; !atEnd(myIterator); goNext(myIterator)) 
    // do something with myIterator

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

Edit: Актуальная проблема:
Я дал рекурсивный алгоритм, который работает на деревьях. (Рекурсивный)
Я также использую библиотеку, где я могу получить доступ только к элементам с помощью итератора (нестандартный, итеративный)

рекурсивный <-> итеративный.
Как я могу решить это?

Answer 1

Вы можете преобразовать эту рекурсивную функцию в итерационную функцию с помощью стека.

//breadth first traversal pseudo-code
push root to a stack
while( stack isn't empty )
    pop element off stack
    push children
    perform action on current node

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

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

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

// редактировать, производительность? На самом деле зависит от вашей реализации и размера дерева. Если в вашем рекурсивном вызове много глубины, вы получите переполнение стека, в то время как итеративная версия будет работать нормально. Я лучше разбираюсь в рекурсии (как используется память), и вы сможете решить, что лучше для вашей ситуации. Вот пример такого типа анализа с числами Фибоначчи .

Answer 2

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

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

Answer 3

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

Вот статья Фила Хаака на эту тему.

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

Answer 4

Даже при рекурсивной итерации вы в конечном итоге посещаете узел на узел.

Что вам нужно знать, так это: как моему итератору сказать, что он должен идти вглубь, а затем: как я получу уведомление о том, что один уровень начался / закончился (то есть начало / конец шага рекурсии).

Это знание может быть отображено на рекурсивный алгоритм.