21

Nas linguagens de programação funcional, diz-se que é possível evitar estouros de pilha usando "recursão de cauda". Mas qual é a diferença entre a recursão normal e a recursão de cauda?

2 Respostas 2

28

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@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);
}

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

Conceitualmente a execução de um programa (processo) ocorre da seguinte maneira: O programa é carregado em memória. Cada instrução do programa corresponde a um endereço (de memória). Durante a chamada de função, o seguinte procedimento é executado:

  1. A posição atual do programa é empilhado.
  2. Todas as variáveis locais e parâmetros são empilhados.
  3. Todas os parâmetros da função são empilhados.
  4. A execução salta para a posição correspondente à função a ser executada.
  5. Os parâmetros são desempilhados.
  6. A vida continua... (as linhas são executadas a partir daquele ponto).
  7. Ao término da função o processo desempilha o desvio para a posição do programa onde foi chamado.
  8. E finalmente desempilha as variáveis locais e parâmetros do ponto onde ocorreu a chamada.

Isso significa que a cada chamada de função, a pilha de execução recebe todas as informações que estão no escopo local e uma porção de comandos para empilhar e desempilhar ocorrem. Se ocorrerem muitas chamadas as chances são que ocorra um estouro dessa pilha. A propósito, o nome que se dá para essas operações que permitem permutar as variáveis locais entre funções é mudança de contexto.

Sempre que se opta por recursão todos os problemas relacionados a mudança de contexto podem ocorrer (portanto: mais operações para manipular a pilha de execução e eventualmente o estouro da pilha). Mas, observando que algoritmos recursivos poderiam ser transformados algoritmos iterativos, os projetista de compiladores criaram otimizações para algumas chamadas de funções. Uma dessas otimizações é a Otimização para Chamada em Cauda (TCO do inglês Tail call optimization).

Funciona exatamente como foi explicado pelo @andre-leria com as seguintes observações:

  1. A sequência de chamadas de A -> B -> C -> A também é recursiva, e também estaria sujeita a otimização para chamada de cauda. Alguns compiladores/interpretadores conseguem realizar a otimização em recursões que envolvam mais de uma função: Ex: Erlang. Scala, por exemplo só consegue garantir otimizações em cauda para a mesma função (http://www.scala-lang.org/docu/files/ScalaByExample.pdf):

    In principle, tail calls can always re-use the stack frame of the calling function. However, some run-time environments (such as the Java VM) lack the primitives to make stack frame re-use for tail calls efficient. A production quality Scala implementation is therefore only required to re-use the stack frame of a directly tail-recursive function whose last action is a call to itself. Other tail calls might be optimized also, but one should not rely on this across implementations.

  2. Alguns compiladores utilizam uma estrutura chamada trampolim que transforma uma chamada em cauda, numa iteração com acumuladores. Isso acontece por exemplo em Scheme que converte o código-fonte para C que não tem suporte para TCO.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .