É possível implementar um algoritmo recursivo com um Iterator?

Question

Eu dei uma árvore como esta:

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

i pode acces cada nó com o próximo operador.

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

mas eu quero usar um algoritmo recursivo na árvore.
Existe uma maneira que eu posso fazer o algoritmo recursivo (exlude o maior subárvore em cada nó) iterativa?
ou como eu posso acessar os elementos não-recursiva?

Editar: O problema real:
Eu dei um algoritmo recursivo, que funciona em árvores. (Recursivo)
Eu também uso uma biblioteca onde eu só posso acessar os itens com um iterador (não standard, iterativa)

recursiva <->. Iterativo
Como posso resolver isso?

Answer 1

Se o seu iterador apenas suportes para a frente (e possivelmente para trás) travessia, mas não seguir links na árvore ou acesso rápido aleatório, você terá um tempo muito difícil adaptar um algoritmo de árvore para ele. No entanto, no final, qualquer resposta vai depender da interface apresentado por seus iterators personalizados, que você não ter fornecido.

Por exemplo, considere o algoritmo fácil de pesquisa árvore. Se a única operação dada pelo seu iterador é "começar a partir do primeiro elemento e passar um por um", você obviamente não pode implementar a pesquisa de árvore de forma eficiente. Também não se pode implementar busca binária. Portanto, você deve fornecer uma lista de exatamente quais operações são suportadas, e (criticamente) os limites de complexidade para cada um.

Answer 2

Você pode converter que função recursiva para uma função iterativa com a ajuda de uma pilha.

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

dependendo de como você deseja percorrer os nós da implementação será diferente. Todas as funções recursivas podem ser transformados para aqueles iterativos. Um uso geral sobre como exige informações sobre o problema específico. Usando pilhas / filas e se transformando em um loop são métodos comuns que deve resolver a maioria das situações.

Você também deve olhar para recursão de cauda e como identificá-los, uma vez que estes problemas bem traduz em um loop for, muitos compiladores até fazer isso para você.

Alguns, mais orientados matematicamente chamadas recursivas podem ser resolvidos por recorrência relações . A probabilidade de que você se deparar com estas que não foram resolvidos ainda é improvável, mas poderia interessá-lo.

// editar desempenho? Realmente depende da sua implementação e o tamanho da árvore. Se houver um monte de profundidade em sua chamada recursiva, então você vai ter um estouro de pilha, enquanto uma versão iterativa irá executar bem. Gostaria de obter uma melhor compreensão sobre a recursividade (como a memória é usado), e você deve ser capaz de decidir o que é melhor para sua situação. Aqui está um exemplo deste tipo de análise com os números de Fibonacci .

Answer 3

Qualquer função recursiva pode, alternativamente, ser implementado com pilhas. Se esta é a pergunta que você está pedindo.

Aqui está um href="http://haacked.com/archive/2007/03/04/Replacing_Recursion_With_a_Stack.aspx" rel="nofollow artigo por Phil Haack sobre o assunto.

Os ganhos de desempenho de uma forma ou de outra são especulativos, o compilador faz as coisas com o nosso código nos bastidores que nem sempre pode prever. Implementar ambos e obter alguns números reais. Se eles são de uso semelhante a um que você achar mais legível.

Answer 4

Mesmo com iteração recursiva, você acaba com uma visita nó por nó.

O que você precisa saber é: como pode o meu iterador ser dito para ir em profundidade, e depois:. Como vou ser notificado de que um nível começou / terminou (ou seja, o início / fim de uma etapa recursão)

Esse conhecimento pode ser mapeado para o algoritmo recursivo.