Poucos assuntos na área da computação são tão confusos ao primeiro contato quanto a recursão. Você, assim como a maioria dos desenvolvedores, seguiu um trajeto bastante comum. Provavelmente, iniciou usando Python para fazer pequenos scripts e exercícios de lógica, depois se aventurou com JavaScript e a manipulação de objetos gráficos no DOM e, talvez, acabou indo para o Java, com sua verbosidade e suas classes.
O importante é que esse fluxo, seguido por muitos com poucas variações, agrega conhecimento a cada estágio. Mesmo que, aos poucos, o desenvolvedor perceba que está cada vez mais confortável em solucionar algoritmos e problemas lógicos, e mesmo que a sintaxe mude — da maneira direta e simples do Python para a verbosa e explícita do Java —, algo permanece em comum entre todas elas: o paradigma imperativo.
A quebra dessa crescente ocorre, entretanto, no momento em que nos deparamos com o paradigma funcional. Provavelmente você já se deparou com algum código semelhante a este:
int fibonacci(int num) {
// Caso base, fibonacci de 1 e 2 são 1
if (num == 1 || num == 2) return 1;
// Caso recursivo, fibonacci de N = fibonacci(N - 1) + fibonacci(N - 2)
return fibonacci(num - 1) + fibonacci(num - 2);
}
Normalmente, decoramos essa função, entendemos a lógica básica por trás dela e seguimos em frente, confiantes de que temos a recursão como mais um item em nossa caixa de ferramentas.
Aprofundando um pouco
A função aparenta calcular Fibonacci corretamente, certo? Bem, como não podemos depender apenas de argumentos vagos, vamos fazer alguns testes.
Esta é a máquina que usarei para rodar esses testes. Obviamente, ela possui potência mais que suficiente para rodar um simples cálculo de Fibonacci.
▗▄▄▄ ▗▄▄▄▄ ▄▄▄▖ lucasbrt@nixos
▜███▙ ▜███▙ ▟███▛ --------------
▜███▙ ▜███▙▟███▛ OS: NixOS 25.11 (Xantusia) x86_64
▜███▙ ▜██████▛ Host: R78512AI-15
▟█████████████████▙ ▜████▛ ▟▙ Kernel: Linux 6.12.52
▟███████████████████▙ ▜███▙ ▟██▙ Uptime: 3 hours, 33 mins
▄▄▄▄▖ ▜███▙ ▟███▛ Packages: 1555 (nix-system), 28 (nix-user)
▟███▛ ▜██▛ ▟███▛ Shell: bash 5.3.3
▟███▛ ▜▛ ▟███▛ Display (BOE0AF7): 1920x1080 in 15", 60 Hz [Built-in]
▟███████████▛ ▟██████████▙ DE: COSMIC
▜██████████▛ ▟███████████▛ WM: cosmic-comp (Wayland)
▟███▛ ▟▙ ▟███▛ Cursor: Cosmic
▟███▛ ▟██▙ ▟███▛ Terminal: .cosmic-term-wr
▟███▛ ▜███▙ ▝▀▀▀▀ CPU: AMD Ryzen 7 5700U (16) @ 4.37 GHz
▜██▛ ▜███▙ ▜██████████████████▛ GPU: AMD Lucienne [Integrated]
▜▛ ▟████▙ ▜████████████████▛ Memory: 2.63 GiB / 15.00 GiB (18%)
▟██████▙ ▜███▙ Swap: 0 B / 16.50 GiB (0%)
▟███▛▜███▙ ▜███▙ Disk (/): 57.34 GiB / 451.15 GiB (13%) - ext4
▟███▛ ▜███▙ ▜███▙ Local IP (wlo1): 192.168.0.28/24
▝▀▀▀ ▀▀▀▀▘ ▀▀▀▘ Battery (499866-3S1P): 90% [Charging, AC Connected]
Locale: en_US.UTF-8
Usaremos o comando time, que veio no shell Fish, para medir o tempo de execução do programa. Para situar os que não o conhecem, vamos usá-lo junto ao comando sleep para demonstrar a exibição. O programa sleep, por sua vez, espera um determinado tempo.
lucasbrt@nixos ~> time sleep 1
________________________________________________________
Executed in 1.00 secs fish external
usr time 0.73 millis 729.00 micros 0.00 millis
sys time 4.35 millis 620.00 micros 3.73 millis
Ok, tudo indo conforme o planejado. O tempo de 1 segundo mostra que o programa executou em 1 segundo, excelente. O próximo passo será configurar o código C completo para testarmos de maneira mais prática. Para simplificar nossa vida, consideremos o código abaixo, que será compilado com clang versão 21.1.1, sem nenhuma otimização customizada.
#include <stdio.h>
#include <stdlib.h>
int fibonacci(int num) {
if (num == 1 || num == 2) return 1;
return fibonacci(num - 1) + fibonacci(num - 2);
}
int main(int argc, char *argv[]) {
if (argc > 1) {
printf("%i", fibonacci(atoi(argv[1])));
}
return 0;
}
Bem, tudo configurado. Vamos rodar alguns testes. Para deixar claro, a bateria será realizada com uma sequência dos seguintes valores: 1, 10, 30 e 50.
lucasbrt@nixos /t/benchmark> clang main.c && time ./a.out 20 && time ./a.out 30 && time ./a.out 40 && time ./a.out 50
6765
________________________________________________________
Executed in 1.93 millis fish external
usr time 0.00 millis 0.00 micros 0.00 millis
sys time 2.05 millis 938.00 micros 1.12 millis
832040
________________________________________________________
Executed in 4.78 millis fish external
usr time 3.38 millis 323.00 micros 3.06 millis
sys time 1.46 millis 437.00 micros 1.02 millis
102334155
________________________________________________________
Executed in 346.08 millis fish external
usr time 344.65 millis 539.00 micros 344.12 millis
sys time 1.52 millis 521.00 micros 1.00 millis
-298632863
________________________________________________________
Executed in 41.93 secs fish external
usr time 41.93 secs 0.14 millis 41.93 secs
sys time 0.00 secs 1.21 millis 0.00 secs
Bom, como podemos ver, existe um certo padrão: o tempo de execução para Fibonacci de 20 é basicamente irrisível; o de 30 é um salto pequeno; estranhamente, o salto para 40 já é bem significativo, mas o que realmente impressiona é o de 50. Primeiro, o resultado está obviamente errado, mas isso se deve a uma falha em nossa implementação do código em C, já que decidi usar apenas int para armazenar o resultado, e o limite de overflow é significativamente baixo. Mas, além do resultado, o custo em tempo de execução é obviamente drástico, ainda mais considerando que estamos calculando um número tão pequeno.
Obviamente, algo não está muito certo aqui, mas, se pararmos para analisar, é até simples de entender a fonte do problema. O problema está, obviamente, na recursão. Para cada chamada de um número N, precisamos chamar a mesma função para mais dois números: N - 1 e N - 2. Podemos desenhar esse problema como uma árvore de chamadas de funções.
Como podemos ver, a árvore de chamada de Fibonacci de 3 é relativamente pequena, o que explica a execução rápida.
Mas, ao observarmos uma chamada de Fibonacci de 5, podemos notar alguns pontos curiosos:
- A quantidade de chamadas da função subiu de 3 para 9, um crescimento significativo, dada a pequena diferença entre os dois números iniciais.
- Em vários pontos, a árvore de chamada invoca a função repetidas vezes com os mesmos valores. Fibonacci de 3 é chamado duas vezes e, mesmo já sabendo o valor após a primeira iteração, o programa continua a ter de recalculá-lo, quebrando-se em mais dois galhos da árvore.
O problema aqui está cada vez mais claro: a abordagem simples e recursiva do cálculo de Fibonacci tem um grande ponto negativo: a performance. Não só pelo processamento, mas também pelo uso de memória, já que cada chamada de função precisa ter sua própria cópia dos valores utilizados dentro do escopo, o que aumenta, e muito, a memória desperdiçada com informações duplicadas.
Uma possível solução
Ok, agora já vimos que não é viável usar essa abordagem para calcular números grandes de Fibonacci (para ser realista, nem os pequenos). Então, o que fazer agora? Bem, podemos usar mais uma vez o paradigma imperativo. Vamos ver como resolver esse problema usando-o, já que qualquer problema pode ser solucionado tanto na abordagem imperativa quanto na funcional.
Aqui, pedi para o ChatGPT gerar essa função, já que eu, pessoalmente, não lembrava como implementá-la, mas, para propósitos didáticos, será o suficiente. Caso não compreenda o que está acontecendo aqui, aproveite para parar um pouco e tentar entender o algoritmo. É uma boa maneira de comparar as duas abordagens e ver que, mesmo que a troca de paradigmas tenha um custo neural até nos acostumarmos, às vezes, esse custo é menor do que ter de resolver o problema com a abordagem "incorreta".
int fibonacci(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
int a = 0;
int b = 1;
int temp;
for (int i = 2; i <= n; i++) {
temp = a + b;
a = b;
b = temp;
}
return b;
}
Bem, para ver como nos saímos com essa abordagem, vamos rodar novamente nossos testes e ver como o programa se comporta. Por falta de paciência, vamos rodar todos os testes de uma vez.
lucasbrt@nixos /t/benchmark> clang main.c && time ./a.out 20 && time ./a.out 30 && time ./a.out 40 && time ./a.out 50
6765
________________________________________________________
Executed in 1.81 millis fish external
usr time 0.04 millis 0.04 millis 0.00 micros
sys time 1.88 millis 1.10 millis 771.00 micros
832040
________________________________________________________
Executed in 1.24 millis fish external
usr time 676.00 micros 0.00 micros 676.00 micros
sys time 604.00 micros 604.00 micros 0.00 micros
102334155
________________________________________________________
Executed in 1.27 millis fish external
usr time 0.00 millis 0.00 micros 0.00 micros
sys time 1.32 millis 621.00 micros 699.00 micros
-298632863
________________________________________________________
Executed in 2.31 millis fish external
usr time 0.74 millis 0.00 micros 744.00 micros
sys time 1.68 millis 931.00 micros 744.00 micros
Veja que curioso: mesmo considerando as pequenas variações de execução, é óbvio que a performance foi drasticamente melhorada. Mas, calma, isso tem uma implicação curiosa. Até o momento, passamos por código em C, falamos sobre recursão e paradigmas, mas o ponto principal da postagem ainda não foi abordado. Onde Haskell entra nessa história?
Haskell, como já devem estar cientes, é uma linguagem funcional; logo, não existem loops explícitos, e tudo é resolvido com o uso de recursão. Então, como ela consegue ser minimamente performática?
A solução proposta pelas linguagens funcionais
Curiosamente, por padrão, Haskell não otimiza milagrosamente suas recursões. Para entendermos isso, vamos primeiro compreender como seria o equivalente da primeira implementação de Fibonacci recursiva em Haskell.
-- Definimos uma função fib que, ao receber 0, retorna 0
fib 0 = 0
-- Definimos outra função fib, essa que, ao receber 1, retorna 1
fib 1 = 1
-- Finalmente, no caso recursivo, definimos que, ao receber N, fib retorna a chamada dela mesma -1 + a chamada dela mesma -2
fib n = fib (n - 1) + fib (n - 2)
Caso esteja curioso sobre como em Haskell podemos definir a mesma função três vezes, sinta-se à vontade para ver mais sobre um conceito chamado pattern matching.
Executando o código acima em nossa bateria de testes, temos o seguinte resultado:
lucasbrt@nixos /t/benchmark> ghc main.hs && time ./main 20 && time ./main 30 && time ./main 40 && time ./main 50
6765
________________________________________________________
Executed in 6.46 millis fish external
usr time 1.43 millis 660.00 micros 0.77 millis
sys time 5.29 millis 645.00 micros 4.65 millis
832040
________________________________________________________
Executed in 106.30 millis fish external
usr time 99.88 millis 0.00 micros 99.88 millis
sys time 6.85 millis 918.00 micros 5.93 millis
102334155
________________________________________________________
Executed in 12.16 secs fish external
usr time 12.13 secs 1.21 millis 12.13 secs
sys time 0.06 secs 0.40 millis 0.06 secs
12586269025
________________________________________________________
Executed in 25.15 mins fish external
usr time 25.11 mins 0.00 micros 25.11 mins
sys time 0.13 mins 801.00 micros 0.13 mins
Como podemos notar — e meu notebook sofreu neste último teste —, o crescimento da performance segue um padrão em comum com o código em C. Isso se deve ao fato de a abordagem ser a mesma; então, tirando pequenas diferenças devido a otimizações da linguagem em si, a curva de performance tende a seguir um padrão exponencial, como anteriormente.
Mas, então, como podemos solucionar esse problema? Como tornar possível o cálculo de Fibonacci ou outros cálculos recursivos sem gastar todo o processamento e a memória disponíveis na máquina?
Bem, aqui vamos explorar três maneiras que podem solucionar esse problema.
Recursão de Cauda (TCO)
Já iniciamos nossa lista com uma técnica curiosa. A ideia por trás dela é, basicamente, garantir que a última operação realizada pela função seja a chamada recursiva dela mesma.
module Main where
import System.Environment (getArgs)
go 0 a _ = a
go 1 _ b = b
go k a b = go (k - 1) b (a + b)
fib_tco n = go n 0 1
main :: IO ()
main = do
(n:_) <- getArgs
print . fib_tco . read $ n
Rodando a bateria de testes com essa nova abordagem, temos os seguintes resultados:
lucasbrt@nixos /t/benchmark> ghc main_tco.hs && time ./main_tco 20 && time ./main_tco 30 && time ./main_tco 40 && time ./main_tco 50
6765
________________________________________________________
Executed in 5.05 millis fish external
usr time 1.21 millis 1.21 millis 0.00 millis
sys time 4.06 millis 0.17 millis 3.89 millis
832040
________________________________________________________
Executed in 5.81 millis fish external
usr time 2.03 millis 1.07 millis 0.96 millis
sys time 3.88 millis 0.03 millis 3.86 millis
102334155
________________________________________________________
Executed in 6.17 millis fish external
usr time 3.13 millis 1.05 millis 2.08 millis
sys time 3.13 millis 0.01 millis 3.11 millis
12586269025
________________________________________________________
Executed in 4.12 millis fish external
usr time 1.15 millis 0.00 micros 1.15 millis
sys time 3.11 millis 806.00 micros 2.30 millis
Como é possível perceber, o ganho de performance foi gritante, mas, curiosamente, o que ocorre aqui "por baixo dos panos" é mais um truque do compilador do que uma mudança no algoritmo em si.
Como foi comentado, a última operação realizada nessa recursão é a própria chamada da função. Ao perceber isso, o compilador do Haskell (no meu caso, o GHC) identifica esse padrão e substitui a chamada recursiva por uma operação de jump, o que seria equivalente a transformar todo o código recursivo acima em uma versão imperativa, assim como a otimização que fizemos em C anteriormente.
Isso, além de evitar o consumo de memória descontrolado — pelo fato de não haver várias cópias da função sendo acumuladas na stack —, também evita a perda de processamento, já que, apesar de ainda termos de recalcular cada função toda vez, o programa não tem o processo de esperar a memória copiar os valores da pilha para a nova chamada.
Memoização
O termo "memoização" já deve ser conhecido por alguns desenvolvedores, especialmente os desenvolvedores front-end React, que adoram usar useMemo() em todos os lugares, e também por desenvolvedores que participam de maratonas de programação e precisam lutar pela otimização de problemas usando Programação Dinâmica.
Se observarmos com atenção a primeira implementação, notamos algumas chamadas repetidas. Para ser exato, Fibonacci de 3 é chamado duas vezes, Fibonacci de 2 é chamado três vezes, e Fibonacci de 1 é chamado duas vezes. Nesse exemplo, não parece muita coisa, mas já vimos que isso crescerá de maneira exponencial.
A ideia por trás da memoização é, basicamente, ter alguma variável externa para armazenar as informações que já foram calculadas.
Então, que tal se, em vez de gastarmos processamento realizando uma nova chamada de função, verificarmos primeiro se já realizamos aquele cálculo? Se já o realizamos, vamos simplesmente pegar o valor que já foi calculado. Se não, calculamos e armazenamos o resultado.
Observe que em vez de recalcularmos o fib de 3 e 2 novamente na esquerda da arvore, podemos apenas usar o valor que já foi calculado previamente no galho direito, economizando tempo e chamadas repetidas de operações que já foram executadas.
Um exemplo de código de Fibonacci usando memoização em Haskell ficaria assim:
module Main where
import System.Environment (getArgs)
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
fib_memo n = fibs !! (fromInteger n)
main :: IO ()
main = do
(n:_) <- getArgs
print . fib_memo . read $ n
Não entendeu nada? Tudo bem, nem eu. A sintaxe de Haskell é realmente um pouco estranha, ainda mais para quem não tem tanta prática com a linguagem. Vamos tentar mostrar um código equivalente em C mais a frente.
E as linguagens imperativas?
Curiosamente, essas técnicas de otimização aplicadas em linguagens funcionais também podem ser usadas em linguagens imperativas. Vamos implementar essas otimizações em C e ver como se comportam.
Memoização em C
#include <stdio.h>
#include <stdlib.h>
#define MAX_GLOBAL_CACHE 1000
long long memo[MAX_GLOBAL_CACHE];
void init_memo() {
for (int i = 0; i < MAX_GLOBAL_CACHE; i++) {
memo[i] = -1;
}
}
long long fibonacci(int n) {
if (n == 1 || n == 2) return 1;
if (memo[n] != -1) return memo[n];
memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
return memo[n];
}
int main(int argc, char *argv[]) {
if (argc > 1) {
init_memo();
printf("%lld", fibonacci(atoi(argv[1])));
}
return 0;
}
Vamos quebrar o código em partes para entendê-lo com mais precisão:
Primeiro, definimos o tamanho máximo do cache que usaremos para armazenar os resultados computados:
#define MAX_GLOBAL_CACHE 1000
Depois, definimos um array de números inteiros. Perceba que usei long long em vez de int, mas, nesse caso, é apenas para não ultrapassarmos o limite do valor máximo que o int suporta em C, como no exemplo anterior, em que já mostramos que a performance é um problema ainda maior que a memória em si:
long long memo[MAX_GLOBAL_CACHE];
Agora, vamos inicializar esse array com o valor -1, que usaremos como uma flag para sinalizar que a posição ainda não foi calculada.
void init_memo() {
for (int i = 0; i < MAX_GLOBAL_CACHE; i++) {
memo[i] = -1;
}
}
Agora, sim, vem o diferencial dessa abordagem:
long long fibonacci(int n) {
if (n == 1 || n == 2) return 1;
if (memo[n] != -1) return memo[n];
memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
return memo[n];
}
Observe que a primeira parte segue o padrão, o caso base não muda, mas, logo na segunda linha, temos algo diferente.
if (memo[n] != -1) return memo[n];
Essa linha pode ser traduzida basicamente como: "Verifique se o número N já foi calculado e está no cache; se estiver, retorne-o".
Se a linha acima não retornar nada, significa que devemos calcular a função recursivamente:
memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
Após isso, apenas retornamos o valor que foi computado:
return memo[n];
Com isso, garantimos que, ao tentarmos acessar um valor que já foi calculado, precisaremos apenas realizar um acesso à memória, e não uma nova chamada de função.
Vamos ver como fica a medição de performance dessa nova abordagem em C.
lucasbrt@nixos /tmp> clang main.c && time ./a.out 1 && time ./a.out 10 && time ./a.out 30 && time ./a.out 35
1
________________________________________________________
Executed in 3.71 millis fish external
usr time 0.88 millis 881.00 micros 0.00 millis
sys time 2.97 millis 823.00 micros 2.15 millis
55
________________________________________________________
Executed in 3.50 millis fish external
usr time 1.25 millis 1.25 millis 0.00 millis
sys time 2.35 millis 0.33 millis 2.02 millis
832040
________________________________________________________
Executed in 3.44 millis fish external
usr time 0.81 millis 812.00 micros 0.00 millis
sys time 2.71 millis 803.00 micros 1.90 millis
9227465
________________________________________________________
Executed in 3.43 millis fish external
usr time 1.25 millis 1.25 millis 0.00 millis
sys time 2.25 millis 0.32 millis 1.93 millis
Como podemos ver, o tempo de execução foi drasticamente melhorado, sendo praticamente equivalente à versão imperativa.
Recursão de Cauda (TCO)
Vamos refatorar nossa implementação inicial para implementar uma versão simples de recursão de cauda.
#include <stdio.h>
#include <stdlib.h>
typedef unsigned long long ull;
ull _fib_tco_helper(int n, ull a, ull b) {
if (n == 0) {
return a;
}
return _fib_tco_helper(n - 1, b, a + b);
}
ull fib_tco(int n) {
return _fib_tco_helper(n, 0ULL, 1ULL);
}
int main(int argc, char *argv[]) {
printf("%llu", fib_tco(atoi(argv[1])));
}
vamos comentar brevemente sobre algumas mudanças realizadas em relação ao algoritmo original.
Como sei que essa otimização irá funcionar (afinal de contas, estamos nesta parte para falar exatamente sobre isso), usarei outro valor para poder calcular números maiores.
typedef unsigned long long ull;
lucasbrt@nixos /t/benchmark> clang main_tco.c && time ./a.out 10 && time ./a.out 20 && time ./a.out 30 && time ./a.out 40 && time ./a.out 50
55
________________________________________________________
Executed in 3.85 millis fish external
usr time 1.37 millis 1.37 millis 0.00 millis
sys time 2.60 millis 0.35 millis 2.25 millis
6765
________________________________________________________
Executed in 3.95 millis fish external
usr time 0.36 millis 0.36 millis 0.00 millis
sys time 3.57 millis 1.41 millis 2.17 millis
832040
________________________________________________________
Executed in 3.35 millis fish external
usr time 1.21 millis 0.23 millis 980.00 micros
sys time 2.25 millis 1.27 millis 980.00 micros
102334155
________________________________________________________
Executed in 3.65 millis fish external
usr time 0.00 millis 0.00 millis 0.00 millis
sys time 3.78 millis 1.91 millis 1.87 millis
12586269025
________________________________________________________
Executed in 3.37 millis fish external
usr time 1.18 millis 0.22 millis 964.00 micros
sys time 2.31 millis 1.34 millis 964.00 micros
Excelente, a performance foi drasticamente aprimorada. Agora, vamos para a questão importante.
Afinal, qual abordagem usar?
Se pararmos para analisar, todas as técnicas de otimização mostradas aqui, que são aplicadas em linguagens funcionais, podem (e, na maioria das vezes, devem) ser adaptadas e aplicadas em linguagens imperativas. Sabendo disso, o mais importante é usar o paradigma que lhe for mais confortável, mas com um adendo: o fato de experimentarmos diferentes paradigmas, querendo ou não, abre a mente para uma nova maneira de abordar os problemas. Isso pode acabar gerando insights bem mais produtivos para sua carreira do que apenas decorar táticas como uma lista de conteúdos e seguir para o próximo. Sabendo disso, caso nunca tenha experimentado Haskell, experimente linguagens funcionais. Outros conceitos dela, como imutabilidade e Tipos de Dados Algébricos, são extremamente úteis e, atualmente, estão sendo implementados, pouco a pouco, em linguagens mais populares.