Última atualização：2026-10-12

Recursão de cauda em C++¶

A otimização de recursão de cauda é uma técnica especial de otimização aplicável a funções recursivas, capaz de reduzir drasticamente o uso de espaço de pilha pelas chamadas recursivas. Com ela, o compilador pode evitar a criação de novos stack frames ao executar a recursão de cauda, reutilizando diretamente o frame atual, o que reduz o risco de estouro de pilha e melhora o desempenho.

O que é recursão de cauda?¶

Quando a chamada recursiva retorna, não há outras operações a executar; uma recursão assim é chamada de recursão de cauda. Nesse caso, o compilador pode substituir a recursão por uma estrutura de repetição, evitando o custo das múltiplas chamadas de função.

Exemplo sem recursão de cauda (sequência de Fibonacci)¶

A função fibonacci_non_tail() que você forneceu é uma implementação padrão sem recursão de cauda:

int fibonacci_non_tail(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci_non_tail(n - 1) + fibonacci_non_tail(n - 2);
}

Nessa implementação, após as chamadas recursivas fibonacci_non_tail(n - 1) e fibonacci_non_tail(n - 2), ainda é necessário somar os resultados delas; portanto, não se trata de recursão de cauda. Cada chamada precisa salvar informações de contexto para continuar o cálculo depois que a recursão retorna, o que faz o espaço de pilha crescer rapidamente.

Exemplo com recursão de cauda otimizada¶

fibonacci_tail() usa a forma de recursão de cauda:

int fibonacci_tail_helper(int n, int a, int b) {
    if (n == 0) {
        return a;
    }
    return fibonacci_tail_helper(n - 1, b, a + b);
}

int fibonacci_tail(int n) {
    return fibonacci_tail_helper(n, 0, 1);
}

Aqui, fibonacci_tail_helper() é uma recursão de cauda. Como você pode ver, após a chamada recursiva fibonacci_tail_helper(n - 1, b, a + b), a função não precisa fazer mais nenhum trabalho: ela retorna diretamente o resultado da chamada recursiva. Por isso, a chamada recursiva está na "cauda" da função, sem operações extras a executar depois dela.

Vantagens da otimização de recursão de cauda¶

Redução do uso de espaço de pilha: como não é preciso salvar o contexto das chamadas recursivas, o compilador pode reutilizar o stack frame, evitando o crescimento da pilha.
Prevenção de estouro de pilha: a otimização de recursão de cauda permite que a profundidade da recursão atinja valores muito grandes sem causar estouro de pilha.
Maior eficiência: em compiladores que suportam a otimização de recursão de cauda, o desempenho fica próximo ao da implementação iterativa, eliminando o custo das chamadas de função recursivas.

Teste de desempenho¶

Por fim, foi feito um benchmark com base no exposto acima, e constatou-se que a otimização de recursão de cauda é muito útil nesse cenário — a diferença de desempenho é enorme!