Skip to main content
Troquei de dotPeek pra ILSpy (código mais limpo)
Fonte Link
André Leria
  • 5,2mil
  • 2
  • 24
  • 46
internal static long _fatorial_fatorial@8(long n, long acc)
{
  forwhile (; n > 1L; { long num; n = num; }1L)
  {
    numlong arg_1F_0 = n - 1L;
    acc *= n;
    n = arg_1F_0;
  }
  return acc;
}

public static long fatorial(long n)
{
  return Fatorial._fatorial(n, 1L);
}
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);
}
internal static long _fatorial@8(long n, long acc)
{
  while (n > 1L)
  {
    long arg_1F_0 = n - 1L;
    acc *= n;
    n = arg_1F_0;
  }
  return acc;
}

public static long fatorial(long n)
{
  return Fatorial._fatorial(n, 1L);
}
Fonte Link
André Leria
  • 5,2mil
  • 2
  • 24
  • 46

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)))))