Como otimizar as chamadas recursivas para melhorar sua eficiência?

Para otimizar chamadas recursivas, frequentemente utilizam-se os seguintes métodos:

1. Memorização — guardar os resultados de chamadas já calculadas para evitar cálculos repetidos. É especialmente útil em problemas com subproblemas sobrepostos, como o cálculo de números de Fibonacci.

2. Recursão de cauda — se a chamada recursiva for a última operação na função, o compilador pode otimizá-la transformando-a em um ciclo, o que reduz o uso de memória na pilha.

3. Transformar recursão em iteração — às vezes, um algoritmo recursivo pode ser reescrito na forma de um ciclo, eliminando completamente os custos adicionais das chamadas de funções.

Exemplo de memorização em C++ para calcular números de Fibonacci:

#include <unordered_map>

std::unordered_map<int, long long> memo;

long long fib(int n) {
    if (n <= 1) return n;
    if (memo.count(n)) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

Este método acelera significativamente os cálculos em comparação com a recursão ingênua.