È possibile implementare un algoritmo ricorsivo con un Iteratore?

Question

Ho dato un albero come questo:

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

posso accedere a ciascun nodo con l'operatore successivo.

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

ma voglio usare un algoritmo ricorsivo sull'albero.
Esiste un modo per rendere iterativo l'algoritmo ricorsivo (escludere la sottostruttura più grande su ciascun nodo)?
o come posso accedere agli elementi in modo non ricorsivo?

Modifica: Il problema reale:
Ho dato un algoritmo ricorsivo, che funziona sugli alberi. (Ricorsiva)
Uso anche una libreria in cui posso accedere agli Articoli solo con un iteratore (non standard, iterativo)

ricorsivo < - > iterativo.
Come posso risolvere questo?

Answer 1

Se il tuo iteratore supporta solo l'attraversamento in avanti (e possibilmente all'indietro), ma non seguendo i collegamenti sull'albero o un accesso casuale rapido, avrai difficoltà ad adattare un algoritmo ad albero ad esso. Tuttavia, alla fine qualsiasi risposta dipenderà dall'interfaccia presentata dai tuoi iteratori personalizzati, che non hai fornito.

Ad esempio, considera l'algoritmo semplice della ricerca dell'albero. Se l'unica operazione fornita dal tuo iteratore è & Quot; inizia dal primo elemento e passa a uno a uno & Quot; ovviamente non puoi implementare la ricerca dell'albero in modo efficiente. Né puoi implementare la ricerca binaria. Quindi è necessario fornire un elenco di quali operazioni sono supportate e (criticamente) i limiti di complessità per ciascuna.

Answer 2

Puoi convertire quella funzione ricorsiva in una funzione iterativa con l'aiuto di uno stack.

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

a seconda di come si desidera attraversare i nodi, l'implementazione sarà diversa. Tutte le funzioni ricorsive possono essere trasformate in funzioni iterative. Un uso generale su come richiede informazioni sul problema specifico. L'uso di stack / code e la trasformazione in un ciclo for sono metodi comuni che dovrebbero risolvere la maggior parte delle situazioni.

Dovresti anche esaminare la ricorsione della coda e come identificarli, poiché questi problemi si traducono bene in un ciclo for, molti compilatori lo fanno anche per te.

Alcune chiamate ricorsive più orientate matematicamente possono essere risolte da relazioni di ricorrenza . È improbabile che si verifichino questi problemi che non sono stati ancora risolti, ma potrebbero interessarti.

// modifica, prestazioni? Dipende molto dalla tua implementazione e dalle dimensioni dell'albero. Se c'è molta profondità nella tua chiamata ricorsiva, otterrai uno stack overflow, mentre una versione iterativa funzionerà bene. Avrei una migliore comprensione della ricorsione (come viene utilizzata la memoria) e dovresti essere in grado di decidere quale sia la migliore per la tua situazione. Ecco un esempio di questo tipo di analisi con i numeri di fibonacci .

Answer 3

Qualsiasi funzione ricorsiva può in alternativa essere implementata con stack. Se questa è la domanda che stai ponendo.

Ecco un articolo di Phil Haack sull'argomento.

Le prestazioni aumentano in un modo o nell'altro sono speculative, il compilatore fa cose con il nostro codice dietro le quinte che non possono sempre prevedere. Implementa entrambi e ottieni alcuni numeri reali. Se sono simili, usa quello che ritieni più leggibile.

Answer 4

Anche con l'iterazione ricorsiva, si finisce con una visita nodo per nodo.

Quello che devi sapere è: come può essere detto al mio iteratore di approfondire prima, e poi: come verrò avvisato che un livello è iniziato / finito (cioè l'inizio / fine di una fase di ricorsione).

Quella conoscenza può essere mappata sull'algoritmo ricorsivo.