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

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

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

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

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

Answer 1

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

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

Answer 2

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

//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 3

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

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

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

Answer 4

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

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

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