Iteratorで再帰アルゴリズムを実装することは可能ですか？

Question

次のようなツリーを指定しました：

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

iは、次の演算子を使用して各ノードにアクセスできます。

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

しかし、ツリーで再帰アルゴリズムを使用したい。
再帰アルゴリズム（各ノードの最大のサブツリーを除く）を反復的に実行する方法はありますか？
またはどのようにして非再帰的に要素にアクセスできますか？

編集： 実際の問題：
木で動作する再帰アルゴリズムを指定しました。 （再帰的）
また、アイテムにイテレータ（非標準、反復）のみをアクセスできるライブラリを使用しています

再帰<！> lt;-<！> gt;反復。
どうすれば解決できますか？

Answer 1

イテレータが順方向（および場合によっては逆方向）のトラバーサルのみをサポートし、ツリーまたは高速ランダムアクセスのリンクをたどらない場合、ツリーアルゴリズムをそれに適応させるのは非常に困難になります。ただし、最終的には、回答はカスタムイテレータによって提供されるインターフェイスに依存しますが、これは提供していません。

たとえば、ツリー検索の簡単なアルゴリズムを考えてみましょう。イテレータによって指定された唯一の操作が<！> quot;最初の要素から開始して1つずつ<！> quot;に移動する場合、ツリー検索を効率的に実装できないことは明らかです。また、バイナリ検索を実装することもできません。そのため、サポートされている操作の正確なリストと、（厳密には）各操作の複雑さの範囲を指定する必要があります。

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ループにうまく変換されるため、多くのコンパイラーがあなたのためにこれを行います。

一部のより数学的に指向した再帰呼び出しは、再帰関係によって解決できます。まだ解決されていないこれらに出くわす可能性は低いですが、興味があるかもしれません。

// edit、パフォーマンス？ 実装とツリーのサイズに本当に依存します。再帰呼び出しに多くの深度がある場合、スタックオーバーフローが発生しますが、反復バージョンでは問題なく実行されます。再帰（メモリの使用方法）をよりよく把握でき、状況に適した方を判断できるはずです。 フィボナッチ数によるこのタイプの分析の例 。

Answer 3

代わりに、任意の再帰関数をスタックで実装できます。これがあなたが尋ねている質問である場合。

この件に関する Phil Haackによる記事があります。

パフォーマンスはいずれかの方法で推測されますが、コンパイラーは、常に予測できるとは限らない舞台裏のコードで処理を行います。両方を実装し、実数を取得します。似ている場合は、読みやすいものを使用してください。

Answer 4

繰り返しを繰り返しても、ノードごとの訪問になります。

知っておく必要があるのは、どのようにイテレータに深さ優先を指示し、次に1つのレベルが開始/終了したかを通知する方法です（つまり、再帰ステップの開始/終了）。

その知識は再帰アルゴリズムにマッピングできます。