Recursão vs loops

Question

Estou tentando trabalhar com exemplos em árvores, conforme dado aqui: http://cslibrary.stanford.edu/110/binarytrees.htmlTodos esses exemplos resolvem problemas por meio de recursão, me pergunto se podemos fornecer uma solução iterativa para cada um deles, ou seja, podemos sempre ter certeza de que um problema que pode ser resolvido pela recursão também terá uma solução iterativa, em geral. Caso contrário, que exemplo podemos dar para mostrar um problema que pode ser resolvido apenas por recursão/iteração?

--

Answer 1

A única diferença entre iteração e recursão em um computador é se você usa a pilha interna ou uma pilha definida pelo usuário. Então eles são equivalentes.

Answer 2

Na minha experiência, a solução mais recursiva pode realmente ser resolvida iterativamente.

Também é uma boa técnica ter, pois as soluções recursivas podem ter uma sobrecarga muito grande nos consumos de memória e da CPU.

Answer 3

Como a recursão usa uma pilha implícita na qual armazena informações sobre cada chamada, você sempre pode implementar esse empilhamento e evitar as chamadas recursivas. Então, sim, toda solução recursiva pode ser transformada em um iterativo.

Ler essa questão por uma prova.

Answer 4

Recursão e iteração são duas ferramentas que, em um nível muito fundamental, fazem a mesma coisa: execute uma operação repetida em um conjunto definido de valores. Eles são intercambiáveis, pois não há problema que não possa, em algum maneira, seja resolvida por apenas um deles. Isso não significa, no entanto, que um não pode ser mais adequado que o outro.

Answer 5

A recursão tem a vantagem em que continuará sem um fim conhecido. Um exemplo perfeito disso é uma classificação rápida sintonizada e rosqueada.

Você não pode gerar loops adicionais, mas pode gerar novos tópicos por meio de recursão.

Answer 6

Como um "velho", volto à minha memória de aprender que os analisadores de descendência recursiva são mais fáceis de escrever, mas os analisadores iterativos baseados em pilha têm melhor desempenho. Aqui está um artigo que parece apoiar essa ideia com métricas:

http://www.texttoolkit.com/index.php?option=com_content&view=article&catid=35%3atechnology&id=60%3ABeyond-Recursive-Descent&itemid=55

Uma coisa a observar é a menção do autor de invadir a pilha de chamadas com ascendência recursiva. Uma implementação iterativa baseada em pilha pode ser muito mais eficiente em recursos.