Recursão em Python – uma introdução prática para iniciantes

Recursão ocorre quando uma função resolve um problema chamando a si mesma.

Parece estranho à primeira vista — por que uma função chamaria a si mesma? – mas assim que clicar, você descobrirá que geralmente é a maneira mais natural de expressar certos tipos de problemas no código.

Neste artigo, você aprenderá o que é recursão, como ela funciona nos bastidores e como usá-la em Python com exemplos que vão desde o básico até casos de uso práticos do mundo real.

Você pode obter o código no GitHub.

Pré-requisitos

Antes de começarmos, certifique-se de ter:

• Python 3.10 ou superior instalado

• Compreensão básica das funções Python e como elas funcionam

• Familiaridade com loops e condicionais

Índice

O que é recursão?

A recursão é uma técnica onde um função resolve um problema dividindo-o em uma versão menor do mesmo problema e chamando a si mesma nessa versão menor.

Pense em um conjunto de bonecas russas ou matryoshkas. Para encontrar a boneca menor, você abre a boneca externa, depois abre a próxima dentro dela e continua até que não haja mais nada para abrir. Cada etapa é a mesma ação – abrir a boneca – apenas em uma boneca menor do que antes.

Resumindo, isso é recursão: a mesma ação, aplicada a um problema cada vez menor, até chegar a um ponto em que não há mais nada a fazer.

As duas regras de cada função recursiva

Toda função recursiva correta deve ter exatamente duas coisas:

1. Um caso básico — a condição em que a função para de chamar a si mesma e retorna um resultado diretamente.

2. Um caso recursivo — a parte onde a função chama a si mesma com uma versão menor ou mais simples da entrada.

Se você esquecer o caso base, a função continuará se chamando para sempre — até que o Python gere um RecursionError. Falaremos mais sobre isso mais tarde.

Sua primeira função recursiva

Comecemos com o exemplo clássico: calcular um fatorial.

O fatorial de n (escrito como n!) é o produto de todos os inteiros de 1 a n. Então 5! = 5 × 4 × 3 × 2 × 1 = 120.

Observe o padrão: 5! = 5 × 4!. E 4! = 4 × 3!. Cada fatorial é apenas n multiplicado pelo fatorial do número abaixo dele. Esse é um ajuste perfeito para recursão.

def factorial(n):
    # Base case: factorial of 0 or 1 is 1
    if n <= 1:
        return 1
    # Recursive case: n! = n * (n-1)!
    return n * factorial(n - 1)

print(factorial(5))
print(factorial(10))

Isso produz:

120
3628800

O caso básico é n <= 1. Quando atingimos 0 ou 1, paramos e retornamos 1. O caso recursivo é n * factorial(n - 1). Nós multiplicamos n pelo fatorial do número abaixo dele, confiando na função para descobrir o resto.

Como Python lida com chamadas recursivas

Quando uma função chama a si mesma, o Python não apenas substitui a chamada atual – ele as empilha. Cada chamada espera que a chamada abaixo retorne um valor antes de terminar.

Vamos rastrear factorial(4) passo a passo:

factorial(4)
  └── 4 * factorial(3)
            └── 3 * factorial(2)
                      └── 2 * factorial(1)
                                └── returns 1   ← base case
                      └── 2 * 1 = 2
            └── 3 * 2 = 6
  └── 4 * 6 = 24

Cada chamada é enviada para o Python pilha de chamadas. Assim que o caso base retorna, a pilha se desenrola – cada chamada em espera recebe sua resposta e termina. É por isso que a recursão profunda pode ser um problema: muitas chamadas empilhadas e o Python fica sem espaço na pilha.

Recursão vs Iteração

A maioria dos problemas que você pode resolver recursivamente também pode resolver com um loop. Vamos comparar as duas abordagens para somar uma lista de números.

Abordagem iterativa:

def sum_iterative(numbers):
    total = 0
    for n in numbers:
        total += n
    return total

Abordagem recursiva:

def sum_recursive(numbers):
    if not numbers:       # base case: empty list
        return 0
    return numbers(0) + sum_recursive(numbers(1:))

print(sum_recursive((10, 20, 30, 40)))

A chamada de função recursiva fornece a seguinte saída:

100

A versão recursiva diz: a soma de uma lista é o primeiro elemento mais a soma de todo o resto. O caso base é uma lista vazia, cuja soma é 0.

Ambas as abordagens iterativa e recursiva funcionam. A recursão tende a ser mais expressiva. É mais próximo de como você descreveria o problema em inglês simples. A iteração tende a ser mais eficiente em Python. Saber quando usar qual delas é uma habilidade que você desenvolverá com a prática.

Trabalhando com dados aninhados

É aqui que a recursão realmente começa a fazer sentido. Os loops são ótimos para dados simples, mas estruturas aninhadas — como uma árvore de pastas ou um dicionário profundamente aninhado — costumam ser difíceis de lidar apenas com loops.

Digamos que você tenha um dicionário aninhado que representa um catálogo de produtos e deseja encontrar todos os preços ocultos nele:

catalog = {
    "electronics": {
        "laptops": {
            "ThinkPad X1": 1299.99,
            "MacBook Air": 1099.99
        },
        "accessories": {
            "USB-C Hub": 49.99,
            "Laptop Stand": 34.99
        }
    },
    "stationery": {
        "Notebook A5": 8.99,
        "Gel Pen Set": 12.49
    }
}

def find_all_prices(data):
    prices = ()
    for value in data.values():
        if isinstance(value, dict):
            # It's a nested dict — recurse into it
            prices.extend(find_all_prices(value))
        else:
            # It's a price — collect it
            prices.append(value)
    return prices

all_prices = find_all_prices(catalog)
print(f"All prices: {all_prices}")
print(f"Total inventory value: ${sum(all_prices):.2f}")

A função verifica cada valor. Se for outro dicionário, ele recorre a ele. Se for um número, ele o coleta.

Escrever isso com loops aninhados exigiria que você conhecesse antecipadamente a profundidade da estrutura. A recursão não se importa com a profundidade.

Saída:

All prices: (1299.99, 1099.99, 49.99, 34.99, 8.99, 12.49)
Total inventory value: $2506.44

Travessia de árvore recursiva

UM árvore é uma estrutura onde cada nó pode ter nós filhos, e cada nó filho é ele próprio uma árvore. Essa estrutura auto-similar é mapeada diretamente para uma função recursiva.

Vamos construir uma árvore simples do sistema de arquivos e calcular o tamanho total de todos os arquivos:

class FileNode:
    def __init__(self, name, size=0, children=None):
        self.name = name
        self.size = size  # 0 for folders
        self.children = children or ()

def total_size(node):
    # Base case: it's a file (no children)
    if not node.children:
        return node.size
    # Recursive case: sum this node's size + all children's sizes
    return node.size + sum(total_size(child) for child in node.children)

# Build a small file tree
project = FileNode("project", children=(
    FileNode("src", children=(
        FileNode("main.py", size=12400),
        FileNode("utils.py", size=5800),
    )),
    FileNode("data", children=(
        FileNode("sales_jan.parquet", size=302914),
        FileNode("sales_feb.parquet", size=289000),
    )),
    FileNode("README.md", size=3200)
))

print(f"Total project size: {total_size(project):,} bytes")
print(f"Source files only: {total_size(project.children(0)):,} bytes")

Para cada nó, retornamos seu tamanho diretamente (caso base: é um arquivo) ou adicionamos seu tamanho à soma de todos os seus filhos (caso recursivo: é uma pasta). A estrutura do código reflete a estrutura da árvore.

A execução do procedimento acima deve fornecer a seguinte saída:

Total project size: 613,314 bytes
Source files only: 18,200 bytes

Memoização: consertando recursão lenta

Às vezes, a recursão pode realizar muito trabalho repetido. O exemplo clássico é o Sequência de Fibonaccionde cada número é a soma dos dois anteriores.

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Isso funciona, mas fib(35) já faz uma pausa perceptível. O problema é que fib(30) é calculado dezenas de vezes em diferentes ramos.

A correção é memorização que envolve o armazenamento em cache dos resultados para que cada valor seja calculado apenas uma vez. Python torna isso super simples com functools.lru_cacheque você pode usar assim:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_fast(n):
    if n <= 1:
        return n
    return fib_fast(n - 1) + fib_fast(n - 2)

print(fib_fast(10))
print(fib_fast(50))
print(fib_fast(100))

Saída:

55
12586269025
354224848179261915075

Adicionando @lru_cache armazena o resultado de cada chamada. Da próxima vez fib_fast(30) for necessário, ele retornará o valor armazenado em cache instantaneamente em vez de recalcular a subárvore inteira.

Observação: vale a pena buscar a memorização sempre que sua função recursiva puder resolver o mesmo subproblema mais de uma vez.

Limite de recursão do Python

Python define um limite de recursão padrão de 1000 chamadas. Se sua função for mais profunda do que isso, você receberá um RecursionError:

def countdown(n):
    if n == 0:
        return "Done"
    return countdown(n - 1)

print(countdown(5))     # works fine
print(countdown(2000))  # raises RecursionError

Aqui countdown(5) funciona e obtemos o Done mensagem enquanto countdown(2000) dá um RecursionError pois excede o limite de recursão predefinido de 1.000 chamadas recursivas.

Done
RecursionError: maximum recursion depth exceeded

Você pode aumentar o limite com sys.setrecursionlimit()mas isso geralmente é um sinal de que a iteração — ou memorização — é a melhor ferramenta para esse problema específico.

import sys
sys.setrecursionlimit(5000)  # use with caution

Para a maioria das travessias de árvores e dividir e conquistar algoritmos, o limite padrão é mais que suficiente. Você só acertará ao trabalhar com estruturas de entrada muito profundas.

Quando usar recursão

A recursão é uma boa opção quando:

• O problema tem uma estrutura naturalmente semelhante – árvores, gráficos, dados aninhados, sistemas de arquivos

• Você está implementando algoritmos de divisão e conquista – classificação por mesclagem, pesquisa binária, classificação rápida

• A solução recursiva é significativamente mais clara que o equivalente iterativo

• A profundidade da estrutura é desconhecida em tempo de compilação

Prefira a iteração quando:

• Você está trabalhando com sequências planas — somando uma lista, pesquisando um array

• O desempenho é crítico – Python não otimiza chamadas finais, então a recursão profunda tem sobrecarga

• A entrada pode ser muito grande ou profundamente aninhada — arriscando um RecursionError

Conclusão

A recursão demora um pouco para parecer natural, mas a ideia central é simples: resolver uma versão pequena do problema, confiar na função para lidar com o resto e sempre definir um caso base para parar.

Você abordou os fundamentos: como funciona a pilha de chamadas, como lidar com dados aninhados, travessia de árvore e como acelerar as coisas com memoização. Esses padrões surgem repetidamente na prática, especialmente ao trabalhar com sistemas de arquivos, analisadores e dados hierárquicos.

A melhor maneira de se sentir confortável com a recursão é escolher um problema adequado e tentar escrevê-lo recursivamente antes de iniciar um loop. O pensamento fica cada vez mais fácil. Você também pode resolver desafios de programação relacionados no HackerRank ou Leetcode.

Boa codificação!