Recursão é um dos conceitos que mais confunde estudantes de programação — e também um dos mais elegantes quando você “clica”. Funções que chamam a si mesmas parecem paradoxais à primeira vista. Mas uma vez que você internaliza os dois ingredientes fundamentais de qualquer função recursiva (o caso base e o passo recursivo), problemas que pareciam complicados se revelam surpreendentemente simples.
A ideia central
Uma função recursiva resolve um problema chamando a si mesma com uma versão menor ou mais simples do mesmo problema, até chegar em um caso tão simples que pode ser resolvido diretamente (o caso base). É como as bonecas russas matryoshka: abra uma boneca, tem outra menor dentro, e outra menor, até chegar na menor que não abre mais. Ou como a definição matemática de fatorial: 5! = 5 × 4!, e 4! = 4 × 3!, e assim por diante até 1! = 1 (o caso base).
Sem caso base, a recursão nunca para — é o equivalente de um loop infinito, que em recursão resulta num erro de “maximum recursion depth exceeded” (Python) ou stack overflow (Java) — a pilha de chamadas transborda. Sempre identifique o caso base primeiro ao projetar uma função recursiva.
Fatorial: o exemplo clássico
Fatorial de n (escrito n!) é o produto de todos os inteiros de 1 até n. 5! = 5 × 4 × 3 × 2 × 1 = 120. A versão recursiva em Python é elegante: o caso base é if n == 0: return 1 (fatorial de 0 é 1 por definição). O passo recursivo é return n * fatorial(n - 1). Quando você chama fatorial(5), o Python empilha chamadas: fatorial(5) espera fatorial(4), que espera fatorial(3), que espera fatorial(2), que espera fatorial(1), que chama fatorial(0) — que retorna 1. Então as chamadas se desenrolam: fatorial(1) retorna 1×1=1, fatorial(2) retorna 2×1=2, fatorial(3) retorna 3×2=6, fatorial(4) retorna 4×6=24, fatorial(5) retorna 5×24=120.
Fibonacci: entendendo o por quê do memoization
A sequência Fibonacci é outro clássico: cada número é a soma dos dois anteriores: 0, 1, 1, 2, 3, 5, 8, 13… A versão recursiva ingênua: caso base é n<=1 retorna n; passo recursivo é fib(n-1) + fib(n-2). Funciona perfeitamente para valores pequenos. Mas fib(40) já demora perceptivelmente. Por quê? Porque calcula os mesmos subproblemas repetidamente: fib(38) é calculado duas vezes, fib(37) quatro vezes, etc. O número de chamadas é exponencial: O(2^n).
Memoization resolve isso: guarde o resultado de cada chamada num dicionário e reutilize em vez de recalcular. Com memoization, Fibonacci recursivo vira O(n) — cada subproblema é resolvido uma única vez. Em Python, o decorador @functools.lru_cache faz isso automaticamente. Essa lição — que recursão ingênua pode ser exponencial mas recursão com memoization pode ser linear — é um dos insights centrais de programação dinâmica.
Quando recursão brilha: problemas hierárquicos
Recursão é especialmente natural para problemas com estrutura hierárquica. Percorrer uma estrutura de pastas e arquivos: uma pasta pode conter arquivos e outras pastas, que podem conter arquivos e outras pastas… recursão modela isso perfeitamente. Percorrer uma árvore binária (estrutura de dados fundamental em ciência da computação) é definida recursivamente: visitar a raiz, visitar recursivamente a subárvore esquerda, visitar recursivamente a subárvore direita. Algoritmos como Quick Sort e Merge Sort são naturalmente recursivos.
Recursão vs iteração
Todo problema recursivo pode ser resolvido iterativamente (com loops) e vice-versa. A recursão geralmente produz código mais expressivo e próximo da definição matemática do problema, mas usa memória da pilha de chamadas — para recursões muito profundas pode causar stack overflow. Iteração é mais eficiente em memória mas às vezes mais verbosa. Linguagens funcionais como Haskell e Erlang preferem recursão; linguagens imperativas como Python e Java preferem iteração para casos simples. Aprenda os dois e escolha o que torna o código mais claro. Recursão, uma vez entendida, muda como você vê problemas — você passa a reconhecer decomposição recursiva natural em todo lugar.
Tem um projeto em mente?
Somos especialistas em transformar ideias em produtos digitais. Apps, sites, automações e IA — vamos construir juntos.
