¿Es posible implementar un algoritmo recursivo con un iterador?

Question

Le he dado un árbol como este:

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

Puedo acceder a cada nodo con el siguiente operador.

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

pero quiero usar un algoritmo recursivo en el árbol.
¿Hay alguna manera de hacer que el algoritmo recursivo (excluir el subárbol más grande en cada nodo) sea iterativo?
¿O cómo puedo acceder a los elementos de forma no recursiva?

Editar: El problema real:
He dado un algoritmo recursivo, que funciona en árboles. (recursivo)
También uso una biblioteca donde solo puedo acceder a los elementos con un iterador (no estándar, iterativo)

recursivo < - > iterativo.
¿Cómo puedo resolver esto?

Answer 1

Si su iterador solo admite el recorrido hacia adelante (y posiblemente hacia atrás), pero no sigue los enlaces en el árbol o el acceso aleatorio rápido, tendrá dificultades para adaptar un algoritmo de árbol. Sin embargo, al final, cualquier respuesta dependerá de la interfaz presentada por sus iteradores personalizados, que no ha proporcionado.

Por ejemplo, considere el algoritmo fácil de búsqueda de árbol. Si la única operación dada por su iterador es & Quot; comience desde el primer elemento y avance uno por uno & Quot ;, obviamente no puede implementar la búsqueda de árbol de manera eficiente. Tampoco puedes implementar la búsqueda binaria. Por lo tanto, debe proporcionar una lista de exactamente qué operaciones son compatibles y (críticamente) los límites de complejidad para cada uno.

Answer 2

Puede convertir esa función recursiva en una función iterativa con la ayuda de una pila.

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

dependiendo de cómo desee atravesar los nodos, la implementación será diferente. Todas las funciones recursivas se pueden transformar en iterativas. Un uso general de cómo requiere información sobre el problema específico. El uso de pilas / colas y la transformación en un ciclo for son métodos comunes que deberían resolver la mayoría de las situaciones.

También debe analizar la recursividad de la cola y cómo identificarlos, ya que estos problemas se traducen muy bien en un bucle for, muchos compiladores incluso lo hacen por usted.

Algunas, llamadas recursivas más orientadas matemáticamente pueden resolverse mediante relaciones de recurrencia . La probabilidad de que encuentre estos que aún no se han resuelto es poco probable, pero podría interesarle.

// editar, ¿rendimiento? Realmente depende de su implementación y el tamaño del árbol. Si hay mucha profundidad en su llamada recursiva, obtendrá un desbordamiento de pila, mientras que una versión iterativa funcionará bien. Tendría una mejor comprensión de la recursividad (cómo se usa la memoria), y usted debería poder decidir cuál es mejor para su situación. Aquí hay un ejemplo de este tipo de análisis con los números de Fibonacci .

Answer 3

Cualquier función recursiva se puede implementar alternativamente con pilas. Si esta es la pregunta que está haciendo.

Aquí hay un artículo de Phil Haack sobre el tema.

Las ganancias de rendimiento de una forma u otra son especulativas, el compilador hace cosas con nuestro código detrás de escena que no siempre pueden predecir. Implemente ambos y obtenga algunos números reales. Si son similares, use el que le resulte más legible.

Answer 4

Incluso con la iteración recursiva, terminas con una visita de nodo por nodo.

Lo que necesita saber es: cómo se le puede decir a mi iterador que vaya primero, y luego: cómo se me notificará que un nivel ha comenzado / terminado (es decir, el inicio / final de un paso de recursión).

Ese conocimiento se puede asignar al algoritmo recursivo.