Python Recursão

Você já sabe que uma função pode chamar outra: dentro de uma função, você usa print(), len() ou uma função sua. Mas uma função também pode chamar a si mesma. Isso se chama recursão (do latim recurrere, "voltar a correr"). Parece um truque estranho, e tem um perigo (a função que se chama para sempre), mas é um jeito elegante de resolver problemas que se repetem "em tamanho menor". Nesta aula você vai ver como ela funciona por dentro, quando usar e o que acontece quando dá errado.

Você vai aprender

O que é uma função recursiva e as suas duas partes: o caso base e o passo recursivo.
A fazer uma contagem regressiva sem laço nenhum.
A calcular o fatorial com return e a acompanhar, passo a passo, as chamadas que o Python faz.
A somar uma lista com recursão.
A comparar recursão com o laço for e a escolher o melhor para cada caso.
O erro real quando falta o caso base: RecursionError: maximum recursion depth exceeded.

A ideia: a fila do cinema

A Ana está numa fila enorme de cinema, no escuro, e quer saber em que lugar está. Ela não consegue contar as pessoas lá na frente. Então ela cutuca a pessoa da frente e pergunta: "em que lugar você está?". Essa pessoa também não sabe, e faz a mesma pergunta para a pessoa da frente dela. E assim por diante, até chegar na primeira pessoa da fila, que olha para a frente, não vê ninguém e responde: "eu sou a número 1".

Aí a resposta volta: a segunda pessoa diz "então eu sou a 2", a terceira diz "eu sou a 3"… até chegar na Ana.

Repare nas duas partes dessa história:

A pergunta repetida em tamanho menor: cada pessoa faz a mesma pergunta, para uma fila que tem uma pessoa a menos. Em programação, é o passo recursivo: a função chama a si mesma com um problema menor.
Alguém que sabe a resposta sem perguntar: a primeira da fila. É o caso base: o ponto em que a função para de se chamar e responde direto.

Sem a primeira pessoa da fila, a pergunta passaria de mão em mão para sempre. Guarde isso: toda função recursiva precisa de um caso base.

1. A primeira função recursiva: a contagem regressiva

Um foguete vai ser lançado. A contagem começa em 3 e, quando chega a zero, aparece "Fogo!". Com recursão:

def contagem(n):
    if n == 0:
        print("Fogo!")
    else:
        print(n)
        contagem(n - 1)


contagem(3)

def contagem(n):: Uma função comum, com um parâmetro n: o número de onde a contagem começa.
if n == 0:: O caso base: quando a contagem chega a zero, não há mais o que contar.
print("Fogo!"): O que fazer no caso base. Aqui a função termina, sem chamar a si mesma.
print(n): Fora do caso base, mostra o número atual…
contagem(n - 1): …e o passo recursivo: a função chama a si mesma com um número menor. Cada chamada chega um pouco mais perto do zero.
contagem(3): A primeira chamada, feita de fora da função. É ela que põe tudo em movimento.

$ python3 contagem.py
3
2
1
Fogo!

Não há for nem while no programa, e mesmo assim os números se repetiram. O que aconteceu, chamada por chamada:

contagem(3): 3 não é zero. Mostra 3 e chama contagem(2).
contagem(2): mostra 2 e chama contagem(1).
contagem(1): mostra 1 e chama contagem(0).
contagem(0): é o caso base. Mostra Fogo! e não chama mais ninguém.
A contagem(0) termina e volta para a contagem(1), que não tem mais nada para fazer e termina também; o mesmo com a 2 e a 3. O programa acaba.

Cada chamada tem o seu próprio n

Quando contagem(3) chama contagem(2), o n que vale 3 não muda: a nova chamada ganha um n novo, só dela, que vale 2. É como as pessoas da fila: cada uma tem a sua resposta. Você viu isso na aula Escopo: as variáveis de dentro de uma função são locais, e cada chamada tem as suas.

Missão: é 31 de dezembro! Mude o programa para contar de 10 até 1 e, no zero, mostrar Feliz Ano Novo! no lugar de Fogo!. Continue usando a recursão (nada de for).

def contagem(n):
    if n == 0:
        print("Fogo!")
    else:
        print(n)
        contagem(n - 1)


contagem(3)

def contagem(n):
    if n == 0:
        print("Feliz Ano Novo!")
    else:
        print(n)
        contagem(n - 1)


contagem(10)

2. Recursão com `return`: o fatorial

O fatorial de um número, escrito 5! na matemática, é a multiplicação dele por todos os números inteiros menores, até o 1:

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

Ele aparece quando você quer saber de quantos jeitos dá para arrumar coisas em fila: 5 livros numa prateleira podem ficar em 120 ordens diferentes. Agora repare num detalhe: 4 × 3 × 2 × 1 é o 4!. Então:

5! = 5 × 4!, e 4! = 4 × 3!, e assim por diante, até 1! = 1.

É o mesmo problema "em tamanho menor", como a fila do cinema. Em Python, fica quase igual à matemática:

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


print(fatorial(5))
print(fatorial(1))
print(fatorial(10))

if n == 1:: O caso base: o fatorial de 1 é 1, sem conta nenhuma.
return 1: Devolve a resposta direto (veja a aula return). O return também termina a função, por isso não precisa de else.
return n * fatorial(n - 1): O passo recursivo: "o fatorial de n é n vezes o fatorial de n - 1". Para fazer a multiplicação, o Python precisa primeiro descobrir quanto vale fatorial(n - 1), e para isso chama a função de novo.

$ python3 fatorial.py
120
1
3628800

Acompanhando as chamadas

Na contagem, cada chamada fazia o seu trabalho antes de chamar a próxima. No fatorial é diferente: cada chamada fica esperando a resposta da próxima para poder multiplicar. Para enxergar isso, esta versão mostra uma mensagem quando cada chamada começa e quando devolve a resposta. O parâmetro extra nivel só serve para empurrar o texto para a direita a cada chamada (4 espaços por nível):

def fatorial(n, nivel=0):
    recuo = "    " * nivel
    print(f"{recuo}fatorial({n}) começou")
    if n == 1:
        print(f"{recuo}fatorial(1) devolve 1")
        return 1
    resultado = n * fatorial(n - 1, nivel + 1)
    print(f"{recuo}fatorial({n}) devolve {resultado}")
    return resultado


print("Resposta:", fatorial(4))

$ python3 fatorial_passos.py
fatorial(4) começou
    fatorial(3) começou
        fatorial(2) começou
            fatorial(1) começou
            fatorial(1) devolve 1
        fatorial(2) devolve 2
    fatorial(3) devolve 6
fatorial(4) devolve 24
Resposta: 24

Leia a saída de cima para baixo. Primeiro, as chamadas descem: a 4 chama a 3, que chama a 2, que chama a 1. Nenhuma delas consegue responder ainda. A fatorial(1) é o caso base e responde na hora: 1. Aí as respostas sobem, cada uma usando a resposta de baixo:

Chamada	Espera por	Conta que faz quando a resposta chega	Devolve
`fatorial(1)`	ninguém (caso base)	nenhuma	1
`fatorial(2)`	`fatorial(1)`	`2 * 1`	2
`fatorial(3)`	`fatorial(2)`	`3 * 2`	6
`fatorial(4)`	`fatorial(3)`	`4 * 6`	24

A pilha de chamadas

Enquanto uma chamada espera a próxima, o Python guarda o lugar dela (onde parou e quanto valem as suas variáveis), como pratos numa pilha: cada chamada nova vai para o topo, e só depois que ela termina o Python volta para a de baixo. Essa pilha se chama pilha de chamadas (em inglês, call stack). Ela tem um tamanho máximo, e é isso que você vai ver estourar em Quando dá errado.

3. Somando uma lista com recursão

A recursão não serve só para números. A Ana anotou os preços da feira numa lista e quer o total. Pense assim: o total da lista é o primeiro preço mais o total do resto. E o total de uma lista vazia é zero (o caso base).

def somar(precos):
    if not precos:
        return 0
    return precos[0] + somar(precos[1:])


compras = [12.5, 8.0, 4.25, 30.0]
print(somar(compras))
print(somar([]))

if not precos:: O caso base. Uma lista vazia vale False numa condição (veja a aula Booleanos), então not precos é verdade quando a lista está vazia.
return 0: A soma de nenhum preço é zero.
precos[0]: O primeiro preço da lista (aula Acessando Itens).
precos[1:]: Uma fatia com todos menos o primeiro: uma lista um item menor. É o "problema em tamanho menor".
somar(precos[1:]): O passo recursivo: a soma do resto.

$ python3 soma_lista.py
54.75
0

As chamadas foram: somar([12.5, 8.0, 4.25, 30.0]) → somar([8.0, 4.25, 30.0]) → somar([4.25, 30.0]) → somar([30.0]) → somar([]), que devolve 0. Na volta: 30.0 + 0, 4.25 + 30.0, 8.0 + 34.25 e 12.5 + 42.25 = 54.75.

Como pensar uma função recursiva

Faça sempre as mesmas duas perguntas:

Qual é o caso mais simples, que eu sei responder sem conta nenhuma? (zero, 1, a lista vazia, o texto vazio.) Esse é o caso base.
Se alguém me der a resposta do problema um pouco menor, como eu chego na resposta do problema inteiro? Esse é o passo recursivo.

E confira: cada chamada tem de chegar mais perto do caso base (n - 1, precos[1:]). Se não chegar, a função nunca para.

Formas diferentes de fazer a mesma coisa

Tudo o que se faz com recursão também se faz com um laço. O fatorial de 5, de três jeitos:

1. Com recursão, como você viu acima (fatorial.py).

2. Com um laço for (aulas for e range()): começa em 1 e vai multiplicando por 2, 3, 4 e 5.

def fatorial(n):
    resultado = 1
    for numero in range(2, n + 1):
        resultado = resultado * numero
    return resultado


print(fatorial(5))

$ python3 laco.py
120

3. Com a função pronta do módulo math (aula O Módulo math):

$ python3 -c "import math; print(math.factorial(5))"
120

Forma	Quando usar
Recursão	Quando o problema é naturalmente "ele mesmo, em tamanho menor": pastas dentro de pastas, uma árvore genealógica, um menu com submenus, dicionários dentro de dicionários. Aí a versão recursiva costuma ser a mais curta e a mais fácil de ler
Laço (`for` / `while`)	Na maioria dos casos do dia a dia, como somar, contar e repetir. Não tem limite de profundidade e é o que os programadores Python esperam ler
Função pronta (`math.factorial`, `sum`)	Sempre que existir. Já está testada e é mais rápida. Para somar uma lista, use `sum(compras)` (aula Funções Embutidas)

Por que aprender recursão, então?

Porque há problemas em que o laço fica complicado e a recursão fica simples: percorrer uma pasta que tem subpastas, que têm outras subpastas, sem saber quantos níveis existem. E porque você vai encontrá-la no código dos outros. Os exemplos desta aula (contagem, fatorial, soma) são simples de propósito, para você ver o mecanismo; no dia a dia, para eles, prefira o laço ou a função pronta.

Quando dá errado

Esqueceu o caso base: RecursionError

A Ana apagou, sem querer, o if da contagem. Agora a função sempre chama a si mesma:

def contagem(n):
    print(n)
    contagem(n - 1)


contagem(3)

O programa mostra 3, 2, 1, 0 e não para: -1, -2, -3… Ninguém diz "chega". No terminal da Ana, depois de 999 números, o Python desiste:

$ python3 sem_base.py
3
2
1
0
-1
-2                                          « …e assim por centenas de linhas…
-994
-995
Traceback (most recent call last):
  File "/home/ana/sem_base.py", line 6, in <module>
    contagem(3)
    ~~~~~~~~^^^
  File "/home/ana/sem_base.py", line 3, in contagem
    contagem(n - 1)
    ~~~~~~~~^^^^^^^
  File "/home/ana/sem_base.py", line 3, in contagem
    contagem(n - 1)
    ~~~~~~~~^^^^^^^
  File "/home/ana/sem_base.py", line 3, in contagem
    contagem(n - 1)
    ~~~~~~~~^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

(As linhas do meio, de -3 a -993, foram cortadas aqui; no terminal da Ana elas aparecem todas.) Linha por linha, o traceback (a "mensagem de erro"; veja a aula Lendo uma Mensagem de Erro):

Traceback (most recent call last):: "Rastro (a chamada mais recente por último)". Abaixo vem o caminho das chamadas, da primeira até a que deu erro.
File "/home/ana/sem_base.py", line 6, in <module>: A primeira chamada: a linha 6 do arquivo, fora de qualquer função (<module> quer dizer "no corpo do programa").
contagem(3) e ~~~~~~~~^^^: A linha que foi executada. Os sinais ~ e ^ embaixo marcam o trecho exato: a chamada da função.
File "/home/ana/sem_base.py", line 3, in contagem: Dentro da contagem, a linha 3 chamou a contagem de novo. O mesmo trecho aparece três vezes…
[Previous line repeated 996 more times]: "A linha anterior se repetiu mais 996 vezes". Em vez de encher a tela com mil blocos iguais, o Python resume. Somando: 3 blocos mostrados + 996 = 999 chamadas da contagem empilhadas, uma esperando a outra.
RecursionError: maximum recursion depth exceeded: O nome do erro e a explicação: "erro de recursão: a profundidade máxima de recursão foi ultrapassada". A pilha de chamadas encheu.

Como consertar: devolva o caso base (if n == 0:) para a função.

Qual é o limite?

O Python limita quantas chamadas podem ficar empilhadas, para que uma recursão sem fim termine num erro claro em vez de travar o computador. No Python 3.14 do Ubuntu da Ana, o limite é 1000, e dá para consultá-lo:

$ python3 -c "import sys; print(sys.getrecursionlimit())"
1000

O <module> (o corpo do programa) conta como uma das mil; por isso couberam 999 chamadas da contagem. Os números do traceback podem variar de um lugar para outro. No editor do guia, que roda o Python dentro do navegador, o sys.getrecursionlimit() também responde 1000 e cabem as mesmas chamadas: a contagem também vai até o -995, e o traceback diz o mesmo [Previous line repeated 996 more times]. Em outros computadores e versões, o limite pode ser outro. Não decore o número; lembre que existe um limite. Existe também a função sys.setrecursionlimit(), que muda esse limite, mas ela não conserta uma função sem caso base: só faz o erro demorar mais para aparecer.

O caso base existe, mas a chamada passa direto por ele

O fatorial da seção 2 está certo para 1, 2, 3… Mas veja o que acontece com fatorial(0):

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


print(fatorial(0))

$ python3 fatorial_negativo.py
Traceback (most recent call last):
  File "/home/ana/fatorial_negativo.py", line 7, in <module>
    print(fatorial(0))
  File "/home/ana/fatorial_negativo.py", line 4, in fatorial
    return n * fatorial(n - 1)
               ~~~~~~~~^^^^^^^           « daqui em diante, o mesmo bloco se repete
  File "/home/ana/fatorial_negativo.py", line 4, in fatorial
    return n * fatorial(n - 1)
               ~~~~~~~~^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

(Algumas repetições do bloco foram cortadas aqui.) O caso base é n == 1, mas a conta começou no 0: 0, -1, -2, -3… a função nunca passa pelo 1. O caso base existe, mas está fora do caminho. Como consertar: use um caso base que pegue esses números também. Na matemática, o fatorial de 0 é 1, então:

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

Com n <= 1 (menor ou igual a 1), tanto o 1 quanto o 0 param a recursão. (Para números negativos, que não têm fatorial, o certo seria avisar com um erro; a aula raise mostra como.)

Esqueceu o return no passo recursivo: TypeError

Aqui o caso base está certo, mas falta a palavra return na última linha:

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


print(fatorial(5))

$ python3 sem_return.py
Traceback (most recent call last):
  File "/home/ana/sem_return.py", line 7, in <module>
    print(fatorial(5))
          ~~~~~~~~^^^
  File "/home/ana/sem_return.py", line 4, in fatorial
    n * fatorial(n - 1)
        ~~~~~~~~^^^^^^^
  File "/home/ana/sem_return.py", line 4, in fatorial
    n * fatorial(n - 1)
        ~~~~~~~~^^^^^^^
  File "/home/ana/sem_return.py", line 4, in fatorial
    n * fatorial(n - 1)
    ~~^~~~~~~~~~~~~~~~~
TypeError: unsupported operand type(s) for *: 'int' and 'NoneType'

Desta vez o erro é outro. As chamadas desceram até fatorial(1), que devolveu 1. A fatorial(2) calculou 2 * 1… e jogou o resultado fora, porque não tem return. Uma função que termina sem return devolve None (aula O Valor None). Aí a fatorial(3) tentou fazer 3 * None, e o Python reclamou: "tipos não suportados para *: 'int' (número inteiro) e 'NoneType' (o tipo do None)". Repare na última marca, ~~^~~~~~~~~~~~~~~~~: o ^ aponta para o *, a operação que falhou. Como consertar: return n * fatorial(n - 1).

Missão: esta contagem não para nunca e termina em RecursionError. Rode para ver o erro, depois conserte a função para ela mostrar 3, 2, 1 e Fogo!.

def contagem(n):
    print(n)
    contagem(n - 1)


contagem(3)

def contagem(n):
    if n == 0:
        print("Fogo!")
    else:
        print(n)
        contagem(n - 1)


contagem(3)

Referência rápida

Termo	O que é	Exemplo
Função recursiva	Função que chama a si mesma	`def contagem(n): … contagem(n - 1)`
Caso base	Onde a função responde direto e para de se chamar	`if n == 0:`, `if not precos:`
Passo recursivo	A chamada a si mesma, com um problema menor	`return n * fatorial(n - 1)`
Pilha de chamadas	As chamadas que estão esperando a resposta da seguinte	`fatorial(4)` espera `fatorial(3)`…
`sys.getrecursionlimit()`	O tamanho máximo da pilha	1000 no Python do Ubuntu da Ana

Sintoma	Causa provável
`RecursionError: maximum recursion depth exceeded`	Falta o caso base, ou a chamada não chega nele (o número passa direto, ou não diminui)
`[Previous line repeated 996 more times]` no traceback	A mesma chamada se repetiu muitas vezes: quase sempre uma recursão sem fim
`TypeError: unsupported operand type(s) for *: 'int' and 'NoneType'`	Faltou o `return` no passo recursivo: a chamada devolveu `None`

Exercícios

1. O caso base

Complete o caso base da contagem regressiva: ela deve parar quando chegar a zero.

def contagem(n):
    if n == :
        print("Fogo!")
    else:
        print(n)
        contagem(n )

2. Quanto vale?

Usando o fatorial da seção 2, quanto vale fatorial(3)?

fatorial(3) =

3. O que é o caso base de uma função recursiva?

A primeira linha da função, o def O caso em que a função responde direto, sem chamar a si mesma A chamada que a função faz a si mesma O maior número que a função aceita

4. Um programa terminou com RecursionError: maximum recursion depth exceeded. O que é mais provável?

O computador está sem memória e precisa ser reiniciado Funções não podem chamar a si mesmas em Python A função nunca chega ao caso base (ele falta, ou a chamada passa direto por ele) Faltou importar o módulo sys

5. Para somar os preços de uma lista no dia a dia, o que é mais recomendado?

A função pronta sum(precos) Sempre uma função recursiva Aumentar o limite com sys.setrecursionlimit() Não dá para somar listas em Python

Missão final: somando de 1 até n

Missão: complete a função soma_ate(n) para devolver 1 + 2 + … + n, com recursão. Dica: a soma de 1 até 1 é 1 (caso base), e a soma até n é n mais a soma até n - 1. A resposta para 100 deve ser 5050.

def soma_ate(n):
    # escreva aqui o caso base e o passo recursivo
    pass


print(soma_ate(100))

def soma_ate(n):
    if n == 1:
        return 1
    return n + soma_ate(n - 1)


print(soma_ate(100))

Conseguiu? Agora uma curiosidade: no Python do Ubuntu da Ana, soma_ate(5000) termina em RecursionError, porque 5000 chamadas não cabem numa pilha de 1000. (No editor do guia, também.) Um laço for, ou a fórmula n * (n + 1) // 2, soma até 5000 ou até um milhão sem problema nenhum: é um bom lembrete de quando a recursão não é a melhor escolha.

Resumo

Uma função recursiva chama a si mesma, sempre com um problema menor.
Ela tem duas partes: o caso base (responde direto e para) e o passo recursivo (chama a si mesma com um problema menor).
Cada chamada tem as suas próprias variáveis. As chamadas "descem" até o caso base e as respostas "sobem" de volta.
Sem caso base, ou com um caso base fora do caminho, a função não para: RecursionError: maximum recursion depth exceeded, com [Previous line repeated … more times] no traceback.
O Python limita a pilha de chamadas (1000 no Ubuntu da Ana e no editor do guia; pode ser outro em outro lugar).
Tudo o que se faz com recursão se faz com laço. Use recursão quando o problema é "ele mesmo em tamanho menor" (pastas dentro de pastas); no resto, laço ou função pronta.