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.
QuantoQuando 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.