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:
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:
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#):
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.
; 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)))))