Recursão de Cauda (Tail Recursion)

Definição

Recursão de Cauda (Tail Recursion) é um tipo especial de recursão em que a última operação da função é a chamada recursiva. Isso significa que não há mais nada para ser feito depois do retorno da função recursiva.

Esse padrão permite que compiladores — como o do Scala — apliquem uma otimização automática chamada Tail Call Optimization (TCO). Com essa otimização, a chamada recursiva não consome espaço extra na pilha, evitando estouros e permitindo loops recursivos eficientes.

Por que usar

• Evita o estouro da pilha em chamadas recursivas profundas;
• Permite escrever código funcional com segurança de desempenho;
• Ideal para linguagens como Scala, que suportam a otimização nativamente.

Problema: estouro de pilha com recursão comum

Considere uma função fatorial tradicional em Scala:

def fatorial(n: Int): BigInt = {
  if (n == 0) 1
  else n * fatorial(n - 1)
}

Essa função funciona para valores pequenos:

println(fatorial(5))  // Saída: 120

Mas se você tentar:

println(fatorial(100000))

Vai resultar no erro:

java.lang.StackOverflowError

Isso ocorre porque a função empilha uma nova chamada a cada passo, acumulando milhares de frames na pilha de execução.

Solução: fatorial com recursão de cauda

import scala.annotation.tailrec

def fatorialTail(n: Int): BigInt = {
  @tailrec
  def loop(x: Int, acumulador: BigInt): BigInt = {
    if (x == 0) acumulador
    else loop(x - 1, acumulador * x)
  }

  loop(n, 1)
}

Esse código usa a anotação @tailrec, que obriga o compilador a verificar se a recursão é otimizada. Agora é seguro chamar:

println(fatorialTail(100000))  // Sem estouro de pilha

Comparação

Relacionados

• Programação Dinâmica
• Memoization
• Backtracking