Estou tentando entender a recursão da cauda em Haskell. Acho que entendo o que é e como funciona, mas gostaria de ter certeza de que não estou estragando tudo.

Aqui está a definição fatorial "padrão":

factorial 1 = 1
factorial k = k * factorial (k-1)

Ao executar, por exemplo,factorial 3, minha função se chamará 3 vezes (mais ou menos). Isso pode representar um problema se eu quiser calcular o fatorial 99999999, pois poderia haver um estouro de pilha. Depois que eu chegarfactorial 1 = 1 Vou ter que "voltar" na pilha e multiplicar todos os valores, então eu tenho 6 operações (3 para chamar a própria função e 3 para multiplicar os valores).

Agora, apresento outra possível implementação fatorial:

factorial 1 c = c
factorial k c = factorial (k-1) (c*k)

Este também é recursivo. Ele se chamará 3 vezes. Mas não tem o problema de ainda ter que "voltar" para calcular as multiplicações de todos os resultados, pois já estou passando o resultado como argumento da função.

Isto é, pelo que entendi, o que é a recursão da cauda. Agora, parece um pouco melhor que o primeiro, mas você ainda pode sobrecarregar a pilha com a mesma facilidade. Ouvi dizer que o compilador de Haskell converterá funções Tail-Recursive em loops nos bastidores. Eu acho que essa é a razão pela qual vale a pena fazer funções recursivas de cauda?

Se esse for o motivo, não há absolutamente nenhuma necessidade de tentar tornar as funções recursivas se o compilador não fizer esse truque inteligente - estou certo? Por exemplo, embora em teoria o compilador C # possa detectar e converter funções recursivas de cauda em loops, eu sei (pelo menos é o que ouvi dizer) que atualmente não faz isso. Portanto, hoje em dia não há absolutamente nenhum sentido em tornar as funções recursivas. É isso?

Obrigado!