Recursividade em Python: a função que chama a si mesma (e o limite no MicroPython)

Uma função é recursiva quando chama a si mesma. Para isso funcionar sem ficar chamando para sempre, ela precisa de duas partes: um caso base, que dá a resposta direta sem nova chamada, e um passo recursivo, que reduz o problema e chama a mesma função com algo menor. A cada chamada o Python empilha um novo quadro com as variáveis locais, e quando o caso base é atingido os valores voltam pela pilha até a primeira chamada.

A recursividade é um jeito de pensar: "para resolver isto, resolvo uma versão menor e junto o resultado". Vale conhecer porque aparece em problemas naturalmente repetitivos, como o fatorial, o máximo divisor comum e a percorrida de estruturas aninhadas. Na ESP32 ela vem com um aviso, porque a memória para empilhar chamadas é pequena e o limite de profundidade é muito menor que no computador. Este artigo mostra como escrever uma função recursiva, como acompanhá-la na pilha, o que acontece quando ela não para, onde fica o limite no simulador e quando um laço é a melhor escolha.

A ideia: um problema menor igual ao primeiro

Imagine uma contagem regressiva. Para contar de 3 até 0, você diz 3 e depois faz uma contagem regressiva de 2 até 0. Essa segunda contagem é o mesmo problema, só que menor. Em Python:

def contagem(n):
    if n == 0:
        print("fogo!")
        return
    print(n)
    contagem(n - 1)

contagem(3)
print("fim")

A saída é 3, 2, 1, fogo! e fim. A função contagem mostra o número e chama contagem(n - 1), que faz o mesmo com o número seguinte. Quando n chega a 0, o if responde direto, sem nova chamada, e a cadeia termina. Aquele return sem valor, que o artigo sobre return apresentou, encerra a função.

Caso base e passo recursivo

Toda função recursiva tem as duas partes da figura. O caso base é a situação mais simples, para a qual a resposta é conhecida. O passo recursivo é o que a função faz nos outros casos: chama a si mesma com um argumento mais próximo do caso base. A soma dos números de 1 até n mostra isso com clareza:

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

print(soma_ate(4))
print(soma_ate(10))
total = 0
for i in range(1, 11):
    total = total + i
print(total)

A saída é 10, 55 e 55. A soma até 4 é 4 mais a soma até 3, que é 3 mais a soma até 2, e assim até a soma até 0, que vale 0 (o caso base). O laço do final, com o mesmo resultado, serve de comparação: a recursão repete por chamadas o que o laço repete por voltas.

A segunda condição para a recursão funcionar é que cada chamada se aproxime do caso base. No soma_ate, o n vai de 4 para 3, 2, 1 e 0, e o 0 aparece. Se o argumento não se aproximasse, o caso base nunca seria alcançado.

A pilha de chamadas

Quando uma função chama a si mesma, a chamada anterior não termina: ela fica esperando. O Python guarda cada chamada pendente numa pilha, com o n e as outras variáveis daquela chamada. O fatorial de n, o produto de 1 até n, mostra o que acontece:

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

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

A saída é 1, 120, 3628800 e 479001600. Para ver a pilha trabalhando, o mesmo programa com um print na entrada e na saída de cada chamada:

def fatorial(n):
    print("entra", n)
    if n <= 1:
        print("base, devolve 1")
        return 1
    r = n * fatorial(n - 1)
    print("sai", n, "devolve", r)
    return r

print(fatorial(4))

A saída é entra 4, entra 3, entra 2, entra 1, base, devolve 1, sai 2 devolve 2, sai 3 devolve 6, sai 4 devolve 24 e 24. Todas as entradas aparecem antes de qualquer saída, e as saídas vêm na ordem inversa. A multiplicação n * fatorial(n - 1) não é feita na ida: cada chamada fica parada na multiplicação, esperando o valor da de baixo. A conta só acontece na volta. A figura mostra a mesma sequência com os quadros empilhados.

Isso explica um fato prático: cada nível da recursão ocupa memória enquanto espera. Uma recursão com mil níveis tem mil quadros vivos ao mesmo tempo.

Mais exemplos

A potência, a base elevada ao expoente, é a base vezes a potência com o expoente menor em 1:

def potencia(base, exp):
    if exp == 0:
        return 1
    return base * potencia(base, exp - 1)

print(potencia(2, 10))
print(potencia(3, 4))
print(potencia(5, 0))

A saída é 1024, 81 e 1. O caso base é o expoente 0, e qualquer base elevada a 0 vale 1.

O máximo divisor comum, pelo algoritmo de Euclides, é recursivo por natureza: o MDC de a e b é o MDC de b e do resto de a por b, até o resto ser zero.

def mdc(a, b):
    if b == 0:
        return a
    return mdc(b, a % b)

print(mdc(48, 18))
print(mdc(17, 5))
print(mdc(100, 75))

A saída é 6, 1 e 25. Num programa de ESP32, o MDC tem um uso concreto: se um LED deve piscar a cada 500 ms e outro a cada 300 ms, o menor passo de tempo que serve aos dois é mdc(500, 300), que é 100 ms, e um temporizador único nesse passo basta. O artigo sobre programar sem travar trata de temporizadores e estados.

A soma dos dígitos de um número separa o último dígito (n % 10) do resto (n // 10):

def soma_digitos(n):
    if n < 10:
        return n
    return n % 10 + soma_digitos(n // 10)

print(soma_digitos(7))
print(soma_digitos(1234))
print(soma_digitos(99999))

A saída é 7, 10 e 45. E a inversão de um texto usa fatias, texto[1:] para tudo menos o primeiro caractere:

def inverter(texto):
    if len(texto) <= 1:
        return texto
    return inverter(texto[1:]) + texto[0]

print(inverter("python"))
print(inverter("a"))
print(inverter(""))

A saída é nohtyp, a e uma linha vazia. O caso base cobre o texto vazio e o de um caractere, e a função inverte o resto e coloca o primeiro caractere no fim.

Quando a recursão não para

O erro clássico é a função sem caso base. Ela chama a si mesma sem nunca parar, e a pilha cresce até o Python desistir:

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

contagem(3)

3
2
1
0
-1
...
-48
Traceback (most recent call last):
  File "main.py", line 5, in <module>
  File "main.py", line 3, in contagem
  File "main.py", line 3, in contagem
...
RuntimeError: maximum recursion depth exceeded

Os pontos ... indicam linhas repetidas que foram cortadas para caber no artigo: na saída real, são cerca de 50 linhas de números e outras tantas de File "main.py", line 3, in contagem. O que importa é a última linha, RuntimeError: maximum recursion depth exceeded. O Python do computador usa o nome RecursionError, que é um tipo de RuntimeError, e a mensagem completa maximum recursion depth exceeded.

Há três formas comuns de errar a recursão. A primeira, a que se viu, é esquecer o caso base. A segunda é escrever o caso base, mas não chegar a ele:

def f(n):
    if n == 0:
        return 0
    return f(n + 1)

print(f(5))

Traceback (most recent call last):
  File "main.py", line 6, in <module>
  File "main.py", line 4, in f
  File "main.py", line 4, in f
...
RuntimeError: maximum recursion depth exceeded

O n + 1 afasta o argumento do 0, em vez de aproximar. O mesmo ocorre com soma_ate(2.5): a sequência 2.5, 1.5, 0.5, -0.5 nunca é igual a 0, e o caso base não é atingido. Quando o caso base é uma igualdade, vale perguntar se o argumento pode pular por cima dele. Escrever n <= 0 no lugar de n == 0 protege dessa classe de erro.

A terceira é esquecer o return no passo recursivo:

def soma(n):
    if n == 0:
        return 0
    n + soma(n - 1)

print(soma(3))

Traceback (most recent call last):
  File "main.py", line 6, in <module>
  File "main.py", line 4, in soma
  File "main.py", line 4, in soma
TypeError: unsupported types for __add__: 'int', 'NoneType'

A chamada soma(n - 1) devolve None quando o return falta, e a soma n + None falha. É o mesmo tropeço do artigo sobre return, agora dentro de uma recursão. O Python do computador escreve unsupported operand type(s) for +: 'int' and 'NoneType'.

O limite de recursão

Nenhuma plataforma deixa a pilha crescer sem fim. O Python do computador tem um limite configurado, que por padrão é de cerca de mil chamadas. O MicroPython da ESP32 tem um limite muito menor, que depende da memória disponível, porque cada chamada gasta memória do aparelho. O simulador do projeto foi calibrado com uma DevKit V1 para reproduzir esse limite. Dá para medi-lo com uma função que conta quantas chamadas aguenta:

profundidade = 0
def descer():
    global profundidade
    profundidade += 1
    descer()

try:
    descer()
except RuntimeError as e:
    print("parou em", profundidade, "chamadas")
    print(e)

A saída é parou em 53 chamadas e maximum recursion depth exceeded. O try e o except, que a série ainda vai detalhar, capturam o erro para o programa poder contar e continuar, em vez de parar com o traceback. No Python do computador, o mesmo programa conta perto de mil chamadas. Nesse limite aparecem dois efeitos práticos no simulador:

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

for n in (10, 20, 30, 40, 45, 50, 60):
    try:
        print(n, fatorial(n))
    except RuntimeError as e:
        print(n, "erro", e)

A saída mostra os fatoriais de 10 a 50 (com números enormes: o de 20 já é 2432902008176640000, e o de 50 tem 65 dígitos) e termina em 60 erro maximum recursion depth exceeded. Medindo, o fatorial aguenta até 52 e falha em 53, e o soma_ate aguenta até 51 e falha em 52. A diferença vem do tamanho de cada quadro: funções com mais variáveis locais gastam mais por chamada e chegam ao limite antes.

Dois cuidados valem aqui. O primeiro é que o número exato muda com a função e com a versão do MicroPython, então os valores acima são do simulador e servem como ordem de grandeza: algumas dezenas de chamadas, e não centenas. Quem precisa de um número firme deve medir na própria placa, com o programa da função descer. O segundo é que o limite afeta quem usa recursão para repetir tarefas longas: percorrer mil leituras com uma função recursiva estoura a pilha numa ESP32, e um laço resolve sem problema.

Fibonacci: a recursão que repete trabalho

A sequência de Fibonacci, em que cada número é a soma dos dois anteriores, é a recursão favorita dos livros, e também o melhor exemplo de seu custo:

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

for i in range(10):
    print(fib(i), end=" ")
print()

chamadas = 0
def fib2(n):
    global chamadas
    chamadas += 1
    if n < 2:
        return n
    return fib2(n - 1) + fib2(n - 2)

for n in (5, 10, 15):
    chamadas = 0
    r = fib2(n)
    print(n, r, chamadas)

A saída é a sequência 0 1 1 2 3 5 8 13 21 34 e as três linhas 5 5 15, 10 55 177 e 15 610 1973. A segunda função conta quantas chamadas foram feitas, com um global como no artigo sobre escopo. Para calcular fib(15), o programa faz 1973 chamadas, quase 2 mil, para uma sequência de apenas 15 valores. A árvore da figura mostra por quê: fib(3) é calculado duas vezes e fib(2) três vezes, cada um do zero, e o desperdício dobra a cada nível. A profundidade da pilha é pequena, só n níveis, e o que cresce é o tempo.

A versão com laço faz uma volta por valor:

def fib_laco(n):
    a = 0
    b = 1
    for i in range(n):
        a, b = b, a + b
    return a

for i in range(10):
    print(fib_laco(i), end=" ")
print()
print(fib_laco(30))

A saída é a mesma sequência e 832040. O fib_laco(30) faz 30 voltas, e a versão recursiva faria mais de 2,6 milhões de chamadas e estouraria tempo e memória numa ESP32. O a, b = b, a + b é uma atribuição múltipla: os dois lados são calculados antes de qualquer atribuição.

Recursão ou laço

Tudo que se faz com recursão se faz com laço, e vice-versa. A contagem regressiva e o fatorial, por exemplo, ficam assim:

def contagem_laco(n):
    while n > 0:
        print(n)
        n = n - 1
    print("fogo!")

contagem_laco(3)

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

print(fatorial_laco(10))
print(fatorial_laco(20))

A saída é 3, 2, 1, fogo!, 3628800 e 2432902008176640000. A versão com laço não empilha nada e não tem limite de profundidade. Na ESP32, é a escolha padrão. A recursão compensa quando o problema é naturalmente recursivo e a profundidade é pequena e conhecida, como acontece ao dividir o problema pela metade a cada passo (a busca binária, por exemplo, precisa de pouco mais de dez níveis para mil elementos) ou ao percorrer uma estrutura aninhada.

Um critério prático:

• A repetição tem tamanho que depende dos dados, como ler leituras de um sensor? Use laço.
• A solução se escreve naturalmente como "resolva a versão menor e combine"? A recursão pode ser mais clara, desde que a profundidade seja pequena.
• A mesma conta se repete muitas vezes, como no Fibonacci? Laço, ou guardar resultados já calculados.
• Dúvida? Escreva o laço. Ele não falha por profundidade.

Em sala de aula: onde a recursão costuma tropeçar

Estes casos se repetem nas turmas.

Esquecer o caso base

A mais frequente. O aluno escreve só o passo, a função chama a si mesma e o programa termina em RuntimeError. A pergunta de conferência é: em que situação esta função responde sem chamar a si mesma?

O caso base que nunca chega

O f(n + 1) ou o n == 0 com n fracionário. O aluno tem um caso base, e o programa também estoura. A conferência: o argumento da chamada está mais perto do caso base do que o argumento atual?

Esquecer o return no passo

A função devolve None e a conta explode longe dali, num TypeError. Em recursão, o return precisa aparecer nos dois lugares: no caso base e no passo.

Esperar que a conta aconteça na ida

O aluno imagina que o fatorial(4) multiplica 4 por 3 e depois por 2, em sequência, para a frente. O print de entrada e saída mostra que a multiplicação só acontece na volta. Acompanhar a pilha no papel, desenhando os quadros, desfaz o engano.

Usar recursão para tudo

Depois de aprender, o aluno resolve até a soma de uma lista com recursão. Funciona com cinco elementos e estoura com cem. O laço seria mais curto e sem risco.

Fibonacci recursivo com números grandes

O programa roda bem com fib(10) e parece travado com fib(35). Não está travado, só repete uma quantidade enorme de contas. A tabela da figura mostra o crescimento.

Exercício: decimal para binário

Escreva uma função recursiva binario(n) que devolva o número n em binário, como texto. A ideia: o último dígito binário é o resto da divisão por 2, e o resto dos dígitos é o binário de n // 2. O caso base é qualquer número menor que 2, que já é um dígito.

def binario(n):
    if n < 2:
        return str(n)
    return binario(n // 2) + str(n % 2)

print(binario(0))
print(binario(10))
print(binario(255))

A saída é 0, 1010 e 11111111. O binario(10) calcula binario(5) e junta o dígito 0, que calcula binario(2) e junta 1, que calcula binario(1), o caso base, e junta 0, o que resulta em 1, 0, 1, 0. Para melhorar, refaça a função com um laço while e compare, e depois confira com a função embutida bin(10), que devolve '0b1010'. A profundidade aqui é só o número de dígitos binários, no máximo 8 para o 255, o que cabe com folga no limite do simulador.

Perguntas frequentes

O que é um caso base?

É a situação mais simples de uma função recursiva, em que ela responde sem chamar a si mesma. Sem ele, a recursão não termina.

Por que o limite de recursão é menor na ESP32?

Cada chamada guarda um quadro com variáveis locais na memória, e a ESP32 tem muito menos memória que um computador. O MicroPython limita a profundidade para não esgotar a pilha do aparelho.

Posso aumentar o limite de recursão?

No Python do computador, com sys.setrecursionlimit. No MicroPython da placa, o limite depende da memória, e a saída é reduzir a profundidade: usar um laço, ou dividir o problema pela metade a cada passo.

Toda recursão pode virar laço?

Pode. Algumas ficam mais longas, porque o laço precisa guardar numa estrutura o que a pilha guardava sozinha, mas é sempre possível.

Recursão é mais rápida que laço?

Em geral, não. Cada chamada tem um custo, e o laço costuma ser igual ou mais rápido. A vantagem da recursão é a clareza em certos problemas, e não a velocidade.

A trilha tem desafio de recursão?

Não há um desafio só de recursão. Os de funções, como Função Dobro, se resolvem sem ela, e o fatorial, o MDC e o binário deste artigo servem de prática.

Para continuar

Releia os artigos sobre return e escopo de variáveis, porque a recursão depende dos dois: cada chamada tem as próprias variáveis locais e entrega o valor por return. A trilha Lógica com Python não tem um desafio só de recursão, e os exercícios deste artigo cumprem esse papel.

O próximo artigo fecha o módulo de funções com lambda, map, filter e sorted com key: funções pequenas, escritas numa linha, e as funções embutidas que as recebem como argumento.