Recursão é uma técnica especial de programação onde uma função chama a si mesma para resolver um problema.
No começo, essa ideia pode parecer um pouco mágica — ou um pouco estranha — mas é uma ferramenta muito poderosa quando você a entende.

Pense nela como olhar em dois espelhos um de frente para o outro. Você vê um reflexo dentro de um reflexo, que continua infinitamente… até que eventualmente ele desaparece. Na recursão, esse “desaparecer” é crucial — chamamos isso de caso base, e é o que para a repetição.

Como a Recursão Funciona

Uma função recursiva:

1. Verifica se deve parar — este é o caso base.
2. Se não, ela chama a si mesma, mas com uma versão menor ou mais simples do problema original.

Repetindo a divisão do problema em partes menores, a recursão pode alcançar a versão mais simples possível do problema, resolvê-la e depois reconstruir a resposta conforme retorna de todas as chamadas.

Exemplo: Cálculo do Fatorial

Vamos pegar o fatorial de um número.
Em matemática, o fatorial de n (escrito como n!) significa:

n! = n × (n-1) × (n-2) × ... × 1

Por exemplo:

5! = 5 × 4 × 3 × 2 × 1 = 120

Aqui está a versão recursiva em Python:

def factorial(n):
    if n == 0:  # caso base
        return 1
    return n * factorial(n - 1)

print(factorial(5))  # 120

O que acontece aqui:

• Se n for 0, chegamos no caso base — por definição, 0! é igual a 1.
• Caso contrário, multiplique n por factorial(n - 1) (uma versão menor do mesmo problema).
• Isso se repete até chegarmos no caso base.

Por Que Usar Recursão?

A recursão pode ser:

• Elegante e concisa para problemas que têm uma estrutura naturalmente repetitiva.
• Perfeita para problemas matemáticos (fatoriais, números de Fibonacci).
• Essencial para navegar dados em forma de árvore (sistemas de arquivos, árvores genealógicas, buscas em IA para jogos).

Às vezes, a recursão pode até substituir laços (loops), embora nem sempre seja a opção mais eficiente.

DICA: Recursão é frequentemente mais fácil de entender quando você pensa nela como “dividir o problema em versões menores até poder resolvê-lo diretamente.”

Armadilhas Comuns

IMPORTANTE!: Sempre defina um caso base — sem ele, a função se chamará infinitamente até o Python gerar um RecursionError.

Soluções para problemas comuns:

• “RecursionError: maximum recursion depth exceeded” → Você não atingiu o caso base, ou seu caso base está incorreto.
• Se a recursão parecer muito complexa para o problema, experimente usar um loop.

A recursão pode parecer complexa inicialmente, mas é apenas outra forma de tornar seu código mais inteligente e adaptável. Depois de praticar com alguns problemas, você verá que ela não é só poderosa, mas pode deixar seu código surpreendentemente curto e elegante.