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][1] aqui no SOPT em [algumas][2] [perguntas][3].

## 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][4] [links][5] [do SO em Inglês][6] 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][7].

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

Algoritmos recursivos naturalmente podem obter vantagens de técnicas de *caching* e *[memoization][8]* 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.


  [1]: https://pt.stackoverflow.com/q/2467/227
  [2]: https://pt.stackoverflow.com/q/4282/227
  [3]: https://pt.stackoverflow.com/questions/3959/como-simular-recurs%C3%A3o-de-cauda-no-c
  [4]: https://stackoverflow.com/questions/1094679/is-there-a-problem-that-has-only-a-recursive-solution?lq=1
  [5]: https://stackoverflow.com/q/931762/1683070
  [6]: https://stackoverflow.com/q/1011448/1683070
  [7]: https://pt.stackoverflow.com/q/1242/227
  [8]: http://en.wikipedia.org/wiki/Memoization