Skip to main content
2 de 4
replaced http://pt.stackoverflow.com/ with https://pt.stackoverflow.com/

A resposta depende muito do contexto.

Situações em que usar recursão

Quando o desempenho for igual ou superior à versão iterativa do código

Há várias situações onde usar recursão é mais eficiente.

Uma delas é quando se sabe de antemão que não haverão muitos níveis de chamada e a versão iterativa gastaria mais processamento e memória com uma pilha de estados.

Outra é quando há a possibilidade de Otimização de Chamada em Cauda (Tail Call Optimization), como já discutido aqui no SOPT em algumas perguntas.

Quanto a versão iterativa é complicada demais

Toda implementação recursiva pode ser "convertida" em iterativa de alguma forma. Em último caso, usa-se uma pilha para simular o estado de cada chamada. Veja alguns links do SO em Inglês para uma discussão mais completa.

O problema é que às vezes a solução é tão mais complexa que na prática a versão recursiva tem um melhor custo-benefício. Um exemplo que conheço pessoalmente é o caso que pode ser vista na minha pergunta e resposta sobre a versão iterativa (não recursiva) do algoritmo LCA.

Quanto técnicas naturalmente usadas em recursão puderem ser utilizadas

Algoritmos recursivos naturalmente podem obter vantagens de técnicas de caching e memoization para obter resultados muito mais rápidos.

Situações em que não devemos usar recursão

A recursão como regra geral deve ser evitada principalmente pelos seguintes motivos:

  • Comumente produz código complexo, de mais difícil manutenção e entendimento
  • Pode dar origem a mais um site de perguntas e respostas, i.e., causar um StackOverflow, após estourar o empilhamento máximo da linguagem ou do processador.

Conclusão

Não há uma resposta absoluta, pois há casos onde a solução iterativa é difícil de se obter ou tem desempenho inferior à recursiva. Porém, sempre que possível deve-se optar por uma solução não recursiva.

utluiz
  • 74,6mil
  • 8
  • 162
  • 254