<!-- language-all: lang-fs -->

A diferença é justamente aonde a chamada recursiva é chamada: Caso ela seja chamada na "cauda" da função, é uma chamada de cauda recursiva.

A "cauda" da função é sua última chamada. É a última computação / cálculo feito pela função, e logo depois dela, nenhum tratamento é feito antes de retornar seu valor.

Por exemplo, considerando esta função para calcular o fatorial de um número, em F#:

    let rec fatorial n : int64 = if n <= 1L then 1L else n * fatorial (n - 1L)

Essa função calcula o fatorial de qualquer número que você colocar. A menos que esse número seja muito grande. Porque nessa função, a cada chamada recursiva, a pilha aumenta, e um número muito grande pode causar um estouro de pilha. Imagine sua execução:

<!-- language: lang-none -->

    fatorial(5) -> 5 * fatorial(5 - 1) ->
    5 * fatorial(4) -> 5 * 4 * fatorial(4 - 1) ->
    5 * 4 * fatorial(3) -> 5 * 4 * 3 * fatorial(3 - 1) ->
    5 * 4 * 3 * fatorial(2) -> 5 * 4 * 3 * 2 * fatorial(2 - 1) ->
    5 * 4 * 3 * 2 * fatorial(1) -> 5 * 4 * 3 * 2 * 1 ->
    120

Se observar, a cada chamada recursiva, o número de funções sendo chamadas aumenta, porque o programa só pode calcular o resultado da última função chamada, para depois calcular o resultado das que a chamaram. Assim, a pilha estoura.

Como evitar isso? Usando chamadas recursivas de cauda. Compiladores de linguagens funcionais costumam transformar chamadas recursivas de cauda em laços, porque isso é perfeitamente possível. Porque não fazer em laços diretamente? Porque isso perderia as qualidades e vantagens da programação funcional.

Vou ilustrar uma função de fatorial em F# usando chamadas recursivas de cauda:

    let fatorial n =
      let rec _fatorial n acc : int64 =
        if n <= 1L then acc else _fatorial (n - 1L) (acc * r)
      _fatorial n 1L

Note que, nesse caso, a função recursiva NÃO é `fatorial`, e sim _`fatorial`. Eu declarei _`fatorial` dentro de `fatorial` para podermos chamá-la com apenas um argumento, sendo que a função recursiva usa um acumulador.

A principal diferença é que na função recursiva de cauda, a chamada de cauda é a chamada recursiva, e não `*` como no primeiro caso. Se observar o fluxo da chamada, ela corre assim:

<!-- language: lang-none -->

    fatorial(5)       ->
    _fatorial(5, 1)   -> _fatorial(5 - 1, 1 * 5)  ->
    _fatorial(4, 5)   -> _fatorial(4 - 1, 5 * 4)  ->
    _fatorial(3, 20)  -> _fatorial(3 - 1, 20 * 3) ->
    _fatorial(2, 60)  -> _fatorial(2 - 1, 60 * 2) ->
    _fatorial(1, 120) -> 120

Como você pode ver, a cada passo, a quantidade de chamadas nem aumenta nem diminui. A partir do momento que a função recursiva é chamada, apenas ela é chamada no final, sem precisar de mais cálculos.

Quando um compilador pronto para isso vê uma chamada recursiva na cauda, ele automaticamente a transforma em um laço durante as otimizações. Com isso, você não perde as vantagens nem a elegância da programação funcional, mas também não corre o risco de passar por um estouro de pilha.

Usando um refletor, posso ver que o código da função recursiva ficaria parecido com isso, de forma imperativa (em C#):

<!-- language: c# -->

    internal static long _fatorial(long n, long acc)
    {
      for (; n > 1L; { long num; n = num; })
      {
        num = n - 1L;
        acc *= n;
      }
      return acc;
    }

    public static long fatorial(long n)
    {
      return Fatorial._fatorial(n, 1L);
    }

O compilador realmente transforma sua função recursiva em um laço. Por outro lado, a função que não usa recursão de causa se mantém intacta.

Um bom meio de saber se sua função usa recursão na cauda ou não é tentar simulá-la em Clojure. Como Clojure não dispõe de recursividade de cauda nativamente, você deve usar a função `recur`, que lançará uma exceção caso não seja usada na cauda.

<!-- language: lang-lisp -->

    ; Causa uma exceção pois a chamada de cauda é *
    (defn fatorial [n]
      (if (<= n 1)
          1
          (* n (recur (dec n)))))

    ; Funciona pois a chamada de cauda é recur
    (defn fatorial
      ([n] (fatorial n 1))
      ([n acc] (if (<= n 1)
                   acc
                   (recur (dec n) (* acc n)))))