Recursão em Python: como funciona, quando usar e exemplos

Q: O que vem a seguir?

O próximo tutorial é map(), filter() e reduce(), as poderosas ferramentas de programação funcional do Python. Você vai aprender a transformar, filtrar e combinar coleções de dados numa única linha.

Intermediário25 min6 exercícios85 XP

Este tutorial foi traduzido do original em inglês.Read in English Leer en español Читать на русском อ่านภาษาไทย Avisar sobre um erro de tradução

Antes de começar

Funções em Python: definir, chamar e retornar valores

0/6 exercícios

Imagine um conjunto de bonecas russas, as matrioscas. Você abre a maior e encontra uma menor dentro. Abre essa, e lá está outra ainda menor. Você continua abrindo até chegar à bonequinha que não abre mais: é o fim.

A recursão funciona do mesmo jeito. Uma função recursiva chama a si mesma com uma versão menor do problema, de novo e de novo, até chegar a um ponto de parada. É uma das técnicas mais elegantes da programação, e depois que você entende, passa a enxergá-la em todo lugar.

Neste tutorial, você vai aprender o que é recursão, como a pilha de chamadas acompanha cada passo, quando a recursão é a ferramenta certa e como evitar os erros mais comuns. Vamos partir de exemplos simples até chegar a algoritmos clássicos como fatorial e Fibonacci.

O que é recursão?

Recursão é quando uma função chama a si mesma. A definição é só essa. Mas por que você iria querer que uma função chamasse a si mesma?

Pense numa contagem regressiva a partir de 5. Você poderia descrever o processo assim: "Para fazer a contagem regressiva a partir de N, diga N e depois faça a contagem regressiva a partir de N menos 1. Pare quando chegar a 0." Essa é uma descrição recursiva: a instrução faz referência a si mesma.

Uma contagem regressiva recursiva

def countdown(n):

if n == 0:

print("Go!")

return

print(n)

countdown(n - 1)

countdown(5)

Saída

5
4
3
2
1
Go!

A função countdown(5) exibe 5 e depois chama countdown(4). Essa exibe 4 e chama countdown(3). Isso continua até countdown(0) exibir "Go!" e parar. Não há mais chamadas.

Toda função recursiva tem duas partes essenciais. Sem as duas, a função roda para sempre (ou até o Python interrompê-la).

O caso base: quando parar

O caso base é a condição que interrompe a recursão. É a menor boneca, aquela que não abre. Sem um caso base, a função chama a si mesma para sempre.

O caso recursivo é a parte em que a função chama a si mesma com uma entrada mais simples. Cada chamada deve deixar você mais perto do caso base.

Caso base e caso recursivo

def countdown(n):

# BASE CASE - the stopping condition

if n == 0:

print("Go!")

return

# RECURSIVE CASE - do work, then call with smaller input

print(n)

countdown(n - 1)

countdown(3)

Saída

3
2
1
Go!

Uma boa regra prática: escreva sempre o caso base primeiro. Depois escreva o caso recursivo que caminha em direção a ele. Essa ordem evita que você esqueça a condição de saída sem querer.

Como funciona a pilha de chamadas

Quando uma função chama a si mesma, o Python não esquece onde estava. Ele usa uma pilha de chamadas: uma pilha de "quadros" (frames), em que cada quadro guarda as variáveis locais da função e o ponto onde ela deve continuar.

Pense numa pilha de post-its. Cada vez que você chama uma função, o Python escreve um post-it novo com os detalhes dessa chamada e coloca no topo. Quando uma função retorna, o Python tira o post-it de cima e volta para o que está embaixo.

Vendo a pilha de chamadas em ação

def factorial(n):

print(f" Calling factorial({n})")

if n <= 1:

print(f" Base case! factorial({n}) = 1")

return 1

result = n * factorial(n - 1)

print(f" factorial({n}) = {n} * factorial({n-1}) = {result}")

return result

print("Result:", factorial(5))

Saída

  Calling factorial(5)
  Calling factorial(4)
  Calling factorial(3)
  Calling factorial(2)
  Calling factorial(1)
  Base case! factorial(1) = 1
  factorial(2) = 2 * factorial(1) = 2
  factorial(3) = 3 * factorial(2) = 6
  factorial(4) = 4 * factorial(3) = 24
  factorial(5) = 5 * factorial(4) = 120
Result: 120

Repare como as mensagens "Calling" vão ficando cada vez mais profundas e depois os resultados voltam subindo. A pilha de chamadas cresce enquanto as chamadas entram e diminui enquanto os resultados saem. Esse movimento de "ida e volta" é o coração da recursão.

Exemplos clássicos de recursão

Fatorial

O fatorial de um número N (escrito como N!) é N multiplicado por todos os inteiros positivos menores que ele. Por exemplo, 5! = 5 x 4 x 3 x 2 x 1 = 120.

O fatorial é recursivo por natureza: 5! = 5 x 4!, e 4! = 4 x 3!, e assim por diante. O caso base é 1! = 1.

Fatorial com recursão

def factorial(n):

if n <= 1: # Base case

return 1

return n * factorial(n - 1) # Recursive case

print(factorial(1)) # 1

print(factorial(5)) # 120

print(factorial(10)) # 3628800

Saída

1
120
3628800

Soma de uma lista

Veja outro padrão: para somar uma lista de forma recursiva, some o primeiro elemento à soma do restante.

Soma recursiva de uma lista

def sum_list(numbers):

if len(numbers) == 0: # Base case: empty list

return 0

return numbers[0] + sum_list(numbers[1:]) # First + sum of rest

print(sum_list([1, 2, 3, 4, 5])) # 15

print(sum_list([10])) # 10

print(sum_list([])) # 0

Saída

15
10
0

O padrão é: trate o caso base (a lista vazia retorna 0) e depois divida o problema em "primeiro elemento" mais "chamada recursiva no restante". Esse padrão serve para muitas operações com listas.

Recursão ou laços: quando usar cada um

Tudo o que você faz com recursão também pode ser feito com um laço. Então, quando escolher um ou outro?

Fatorial recursivo

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))  # 120

Fatorial iterativo (laço)

def factorial(n):
    result = 1
    for i in range(2, n + 1):
        result = result * i
    return result

print(factorial(5))  # 120

Para problemas simples, como o fatorial, os laços costumam ser mais rápidos e usar menos memória. Cada chamada recursiva adiciona um quadro à pilha de chamadas, enquanto um laço reaproveita as mesmas variáveis.

A recursão brilha quando o problema tem naturalmente o formato de uma árvore ou é semelhante a si mesmo. Exemplos: explorar estruturas de pastas, analisar dados aninhados (como JSON ou HTML) e percorrer árvores e grafos. Nesses casos, a recursão gera um código mais limpo e mais curto.

Quando a recursão é a ferramenta certa

A recursão se destaca em problemas em que você precisa explorar todos os ramos de uma estrutura em forma de árvore. Veja um exemplo prático: achatar uma lista aninhada.

Achatando uma lista aninhada com recursão

def flatten(lst):

result = []

for item in lst:

if isinstance(item, list):

result.extend(flatten(item)) # Recursion for nested lists

else:

result.append(item)

return result

nested = [1, [2, 3], [4, [5, 6]], 7]

print(flatten(nested)) # [1, 2, 3, 4, 5, 6, 7]

Saída

[1, 2, 3, 4, 5, 6, 7]

Tente escrever isso sem recursão. Você precisaria de uma pilha manual e de um controle bem trabalhoso. A versão recursiva se lê quase como uma frase em português: "Para cada item, se for uma lista, achate-a. Senão, guarde o item."

Erros comuns com recursão

Erro 1: sem caso base

Sempre inclua um caso base

# DON'T run this - it would crash!

# def bad_countdown(n):

# print(n)

# bad_countdown(n - 1) # Never stops!

# The fix: add a base case

def good_countdown(n):

if n <= 0:

return

print(n)

good_countdown(n - 1)

good_countdown(5)

Saída

Erro 2: não caminhar em direção ao caso base

Cada chamada precisa chegar mais perto do caso base

# DON'T run this - n never decreases!

# def bad_factorial(n):

# if n <= 1:

# return 1

# return n * bad_factorial(n) # Oops! Should be n - 1

# The fix: make sure the argument changes

def good_factorial(n):

if n <= 1:

return 1

return n * good_factorial(n - 1) # n - 1 moves toward base case

print(good_factorial(5))

Saída

Exercícios práticos

Comece pelos mais simples e vá avançando. Cada exercício aproveita o que você aprendeu. Lembre-se: escreva sempre o caso base primeiro!

Exercício 1: preveja a saída da recursão

Preveja a saída

Leia este código e preveja a saída. Depois escreva instruções print() que produzam exatamente a mesma saída.

def mystery(n):
    if n <= 0:
        return
    mystery(n - 1)
    print(n)

mystery(3)

Repare que o print(n) vem depois da chamada recursiva. Pense com cuidado na ordem.

# Print the exact output of the code above

Exercício 2: soma recursiva de 1 a N

Escreva o código

Escreva uma função recursiva chamada sum_to que recebe um inteiro positivo n e retorna a soma de todos os números de 1 a n.

Por exemplo: sum_to(5) deve retornar 1 + 2 + 3 + 4 + 5 = 15.

Caso base: sum_to(1) retorna 1.

Exiba os resultados de sum_to(5) e sum_to(10) em linhas separadas.

def sum_to(n):

# Your code here

pass

print(sum_to(5))

print(sum_to(10))

Exercício 3: conserte a função de potência quebrada

Corrija o erro

Esta função recursiva deveria calcular base elevado à potência exp (como base ** exp). Mas ela tem dois bugs.

Corrija os dois bugs para que a saída seja:

8
1
81

def power(base, exp):

if exp == 0:

return 0

return base + power(base, exp - 1)

print(power(2, 3))

print(power(5, 0))

print(power(3, 4))

Exercício 4: Fibonacci recursivo

Escreva o código

Escreva uma função recursiva chamada fibonacci que retorna o n-ésimo número de Fibonacci.

A sequência de Fibonacci começa assim: 0, 1, 1, 2, 3, 5, 8, 13, ...

Regras:

fibonacci(0) retorna 0

fibonacci(1) retorna 1

Para n >= 2: fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)

Exiba os resultados para n = 0, 1, 5 e 10 em linhas separadas.

def fibonacci(n):

# Your code here

pass

print(fibonacci(0))

print(fibonacci(1))

print(fibonacci(5))

print(fibonacci(10))

Exercício 5: inverta uma string com recursão

Escreva o código

Escreva uma função recursiva chamada reverse que recebe uma string e a retorna invertida.

Por exemplo: reverse("hello") deve retornar "olleh".

Dica: o último caractere mais o inverso de tudo, menos o último caractere.

Exiba os resultados de reverse("hello") e reverse("Python") em linhas separadas.

def reverse(s):

# Your code here

pass

print(reverse("hello"))

print(reverse("Python"))

Exercício 6: conte os dígitos com recursão

Escreva o código

Escreva uma função recursiva chamada count_digits que recebe um inteiro não negativo e retorna quantos dígitos ele tem.

Por exemplo:

count_digits(0) retorna 1

count_digits(5) retorna 1

count_digits(123) retorna 3

count_digits(99999) retorna 5

Dica: dividir por 10 com // remove o último dígito.

Exiba os resultados para 0, 5, 123 e 99999 em linhas separadas.

def count_digits(n):

# Your code here

pass

print(count_digits(0))

print(count_digits(5))

print(count_digits(123))

print(count_digits(99999))

Resumo

Veja o que você aprendeu sobre recursão:

Conceito	O que significa
Recursão	Uma função que chama a si mesma
Caso base	A condição que interrompe a recursão
Caso recursivo	A parte que chama a si mesma com uma entrada mais simples
Pilha de chamadas	O sistema do Python para acompanhar chamadas de função aninhadas
Estouro de pilha	O que acontece quando a recursão vai fundo demais (sem caso base)
Recursão ou laços	Laços para repetições simples, recursão para problemas em forma de árvore

A regra de ouro da recursão: escreva sempre o caso base primeiro e garanta que cada chamada recursiva caminhe em direção a ele. Se você fizer isso, consegue escrever qualquer função recursiva.

O que vem a seguir?

O próximo tutorial é map(), filter() e reduce(), as poderosas ferramentas de programação funcional do Python. Você vai aprender a transformar, filtrar e combinar coleções de dados numa única linha.

O que é recursão?

O caso base: quando parar

Como funciona a pilha de chamadas

Exemplos clássicos de recursão

Fatorial

Soma de uma lista

Recursão ou laços: quando usar cada um

Quando a recursão é a ferramenta certa

Erros comuns com recursão

Erro 1: sem caso base

Erro 2: não caminhar em direção ao caso base

Exercícios práticos

Resumo

O que vem a seguir?

Tutoriais relacionados