Recursão em Python: É Mais Simples do que Parece

Entenda, passo a passo, como uma função pode chamar a si mesma, por que a condição de parada é indispensável e onde a recursão aparece na prática.

Uma função pode chamar ela mesma?

Pode, e isso tem nome: recursão. Na primeira vez que a gente vê, parece estranho — como uma função pode usar a si mesma se ela ainda nem terminou? Mas a ideia por trás é bem mais simples do que parece, e neste artigo vamos entender cada passo com calma.

O que é recursão?

Recursão acontece quando uma função chama ela mesma para resolver um problema aos poucos. Em vez de resolver tudo de uma vez, a função resolve um pedacinho e passa o resto do problema — agora um pouco menor — para uma nova chamada dela mesma.

Uma boa forma de imaginar é pensar naquelas bonecas russas, uma dentro da outra. Para chegar na menor, você abre a primeira, encontra outra boneca igual, só que menor, e repete o mesmo gesto: abrir. Você faz isso até chegar na última, que não abre mais. É aí que você para.

Repare em duas coisas nessa história, porque elas valem para toda recursão:

a cada passo, o problema fica menor (uma boneca menor);
existe um momento em que é preciso parar (a última boneca).

Exemplo prático: contando de 5 até 1

Vamos ver um exemplo bem simples: uma função que conta de 5 até 1.

def contar(n):
    if n == 0:
        return

    print(n)
    contar(n - 1)

contar(5)

Resultado:

Vamos ler essa função linha por linha:

def contar(n): — cria a função contar, que recebe um número n;
if n == 0: return — se o número for zero, a função termina ali mesmo, sem fazer mais nada;
print(n) — mostra o número atual na tela;
contar(n - 1) — aqui está a recursão: a função chama ela mesma, mas com um número menor.

Como funciona, passo a passo

A função começa com 5 e chama ela mesma com um número menor. Cada chamada é um passo menor:

contar(5) → 5 não é zero, então mostra 5 e chama contar(4);
contar(4) → mostra 4 e chama contar(3);
contar(3) → mostra 3 e chama contar(2);
contar(2) → mostra 2 e chama contar(1);
contar(1) → mostra 1 e chama contar(0);
contar(0) → o número é zero, então a função para.

Quando chega em 0, nenhuma nova chamada é feita. A partir daí, cada chamada que estava esperando termina, uma por uma, até voltar para o contar(5) original, e o programa segue em frente.

E a condição de parada?

A parte mais importante da recursão é a condição de parada (também chamada de caso base). No nosso exemplo, é este trecho:

if n == 0:
    return

Sem isso, a função continuaria chamando a si mesma indefinidamente: contar(0) chamaria contar(-1), que chamaria contar(-2), e assim por diante, sem nunca terminar. A condição de parada é o que evita esse loop infinito.

Na prática, o Python não deixa o programa rodar para sempre. Ele tem um limite de chamadas empilhadas (por padrão, cerca de 1000) e, quando esse limite é ultrapassado, o programa é interrompido com um erro:

RecursionError: maximum recursion depth exceeded

Se você encontrar esse erro, a primeira coisa a conferir é a condição de parada: ela existe? Ela é realmente alcançada?

As duas partes de toda função recursiva

Toda função recursiva bem escrita tem duas partes:

Caso base: a situação mais simples possível, em que a função responde direto, sem chamar a si mesma. É a condição de parada.
Caso recursivo: a situação em que a função chama a si mesma com uma versão menor do problema.

A palavra "menor" é essencial. Se a função chamar a si mesma com o mesmo valor, ou com um valor que se afasta do caso base, ela nunca vai parar. Em contar(n - 1), o número diminui a cada chamada e, por isso, uma hora chega em zero.

O que acontece por trás: a pilha de chamadas

Quando uma função chama outra, o Python precisa lembrar onde parou para continuar depois. Ele faz isso usando a pilha de chamadas. Pense em uma pilha de pratos: cada nova chamada é um prato colocado em cima, e só dá para tirar o prato de cima.

Em contar(5), a pilha vai crescendo: contar(5), depois contar(4) em cima, depois contar(3)... até contar(0). Quando contar(0) termina, ela sai da pilha, e o Python volta para contar(1), exatamente no ponto em que ela tinha parado. E assim por diante, até a pilha esvaziar.

Dá para ver isso acontecendo com uma pequena mudança: colocar o print depois da chamada recursiva.

def contar(n):
    if n == 0:
        return

    contar(n - 1)
    print(n)

contar(5)

Resultado:

A ordem inverteu! Isso acontece porque agora cada chamada primeiro espera a próxima terminar e só depois mostra o seu número. A primeira a mostrar é a última que foi chamada, contar(1) — do mesmo jeito que o último prato colocado é o primeiro a sair da pilha.

Recursão que devolve um valor: o fatorial

No exemplo da contagem, a função só mostrava números. Mas a recursão fica ainda mais interessante quando cada chamada devolve um resultado para quem a chamou.

Um exemplo clássico é o fatorial. O fatorial de 4 é 4 * 3 * 2 * 1 = 24. Olhando com atenção, dá para perceber que o fatorial de 4 é 4 vezes o fatorial de 3. E o fatorial de 3 é 3 vezes o fatorial de 2. O problema contém uma versão menor dele mesmo — o cenário perfeito para recursão.

def fatorial(n):
    if n == 1:
        return 1

    return n * fatorial(n - 1)

print(fatorial(4))

Resultado:

Primeiro, as chamadas vão "descendo" até o caso base:

fatorial(4) = 4 * fatorial(3)
fatorial(3) = 3 * fatorial(2)
fatorial(2) = 2 * fatorial(1)
fatorial(1) = 1

Depois, as respostas vão "subindo" de volta, cada uma completando a conta que estava esperando:

fatorial(2) = 2 * 1 = 2
fatorial(3) = 3 * 2 = 6
fatorial(4) = 4 * 6 = 24

Essa ida e volta é o coração da recursão: descer dividindo o problema e subir juntando as respostas.

Recursão ou loop?

Você pode estar pensando: "mas eu conseguiria fazer a contagem com um for". E é verdade:

for n in range(5, 0, -1):
    print(n)

Para repetições simples como essa, o loop costuma ser a melhor escolha: é direto e não empilha chamadas. A recursão brilha quando o próprio problema tem uma estrutura que se repete dentro dela mesma — uma pasta que tem pastas dentro, uma lista que tem listas dentro, um caminho que se divide em outros caminhos.

Onde a recursão é usada?

A recursão é muito utilizada em algoritmos como o DFS (Busca em Profundidade), que aparece em problemas envolvendo árvores, grafos, matrizes e labirintos. A ideia do DFS é seguir por um caminho até o fim e, quando não der mais para avançar, voltar e tentar o próximo — exatamente o "descer e subir" que acabamos de ver.

Um exemplo pequeno que mostra essa ideia: somar todos os números de uma lista que pode ter outras listas dentro.

def somar(lista):
    total = 0

    for item in lista:
        if isinstance(item, list):
            total += somar(item)
        else:
            total += item

    return total

numeros = [1, [2, 3], [4, [5, 6]]]
print(somar(numeros))

Resultado:

A função percorre a lista. Quando encontra um número, soma. Quando encontra outra lista, chama a si mesma para somar aquela lista menor. Não importa quantos níveis existam: a mesma função resolve todos. Aqui, o caso base é uma lista que só tem números — nela, nenhuma nova chamada é feita. Fazer isso só com loops, sem saber quantos níveis existem, seria bem mais trabalhoso.

É a mesma lógica usada para percorrer pastas e subpastas de um computador, navegar por menus com submenus ou explorar os caminhos de um labirinto.

Erros comuns de quem está começando

Esquecer a condição de parada. É o erro mais comum e leva direto ao RecursionError.
Ter uma condição de parada que nunca é alcançada. Chamar contar(-3) na nossa função, por exemplo: o número só diminui e nunca passa pelo zero. Usar if n <= 0 deixaria a função mais segura.
Não diminuir o problema. Escrever contar(n) no lugar de contar(n - 1) faz a função chamar a si mesma sempre com o mesmo valor.
Esquecer o return na chamada recursiva. No fatorial, escrever só n * fatorial(n - 1), sem o return, faz a função devolver None.

Para lembrar

Recursão = uma função resolvendo um problema chamando a si mesma com uma versão menor do problema.

Toda função recursiva precisa de uma condição de parada (caso base).
A cada chamada, o problema precisa ficar menor.
As chamadas ficam guardadas em uma pilha e terminam da última para a primeira.
Ela é muito usada em estruturas que se repetem dentro delas mesmas, como árvores, grafos e listas aninhadas.

Parece difícil no começo, mas com prática fica bem mais fácil. Uma boa forma de treinar é pegar os exemplos deste artigo, mudar os valores e acompanhar no papel cada chamada, uma por uma. Bora praticar?