Est-il possible d'implémenter un algorithme récursif avec un itérateur?

Question

J'ai donné un arbre comme ceci:

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

Je peux accéder à chaque nœud avec l'opérateur suivant.

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

mais je veux utiliser un algorithme récursif sur l'arbre.
Existe-t-il un moyen de rendre l'algorithme récursif (à l'exclusion du plus gros sous-arbre de chaque nœud) itératif?
ou comment puis-je accéder aux éléments de manière non récursive?

Modifier: Le problème actuel:
J'ai donné un algorithme récursif, qui fonctionne sur les arbres. (récursif)
J'utilise aussi une bibliothèque où je peux seulement accéder aux éléments avec un itérateur (non standard, itératif)

récursif < - > itératif.
Comment puis-je résoudre ce problème?

Answer 1

Si votre itérateur ne prend en charge que la traversée en avant (et éventuellement en arrière), sans suivre les liens sur l’arbre ou l’accès aléatoire rapide, vous aurez beaucoup de difficulté à y adapter un algorithme d’arbre. Cependant, à la fin, toute réponse dépendra de l'interface présentée par vos itérateurs personnalisés, que vous n'avez pas fournie.

Par exemple, considérons l’algorithme de recherche arborescente simple. Si la seule opération donnée par votre itérateur est & "; Commencez à partir du premier élément et passez au coup par coup &"; Vous ne pouvez évidemment pas implémenter efficacement la recherche arborescente. Vous ne pouvez pas non plus implémenter la recherche binaire. Vous devez donc fournir une liste précise des opérations prises en charge et (de manière critique) les limites de complexité pour chacune.

Answer 2

Vous pouvez convertir cette fonction récursive en une fonction itérative à l'aide d'une pile.

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

En fonction de la manière dont vous souhaitez traverser les nœuds, la mise en œuvre sera différente. Toutes les fonctions récursives peuvent être transformées en fonctions itératives. Un usage général sur comment nécessite des informations sur le problème spécifique. Utiliser des piles / files et transformer en une boucle for sont des méthodes courantes qui devraient résoudre la plupart des situations.

Vous devriez également vous renseigner sur la récursion de la queue et son identification, car ces problèmes se traduisent par une boucle for, de nombreux compilateurs le font même pour vous.

Certains relations de récurrence peuvent résoudre des appels récursifs plus mathématiques. Il est peu probable que vous rencontriez des problèmes qui n’ont pas encore été résolus, mais cela pourrait vous intéresser.

// édition, performance? Cela dépend vraiment de votre implémentation et de la taille de l’arbre. S'il y a beaucoup de profondeur dans votre appel récursif, vous obtiendrez un débordement de pile, alors qu'une version itérative fonctionnera correctement. Je comprendrais mieux la récursivité (comment la mémoire est utilisée) et vous devriez être capable de décider lequel est le mieux adapté à votre situation. Voici un exemple de ce type d'analyse avec les nombres de fibonacci .

Answer 3

Toute fonction récursive peut également être implémentée avec des piles. Si telle est la question que vous vous posez.

Voici un article de Phil Haack sur le sujet.

Les gains de performance d’une manière ou d’une autre sont spéculatifs, le compilateur fait des choses avec notre code en coulisses qui ne peuvent pas toujours prédire. Implémentez les deux et obtenez des nombres réels. S'ils sont similaires, utilisez celui que vous trouvez plus lisible.

Answer 4

Même avec une itération récursive, vous vous retrouvez avec une visite nœud par nœud.

Ce que vous devez savoir, c'est: comment dire à mon itérateur d'aller en profondeur d'abord, puis: comment serai-je averti qu'un niveau a commencé / s'est terminé (c'est-à-dire le début / la fin d'une étape de récursivité)?

Cette connaissance peut être mappée sur l'algorithme récursif.