Introdução à Programação · 1.º ano (indicativo)
Como escrever uma função recursiva?
Resposta curta
Uma função recursiva é uma função que se chama a si própria com um problema mais pequeno. Para a escrever, defina primeiro o caso base (a situação mais simples, que se resolve sem chamar a função) e depois o passo recursivo (reduz o problema e usa a própria função). Sem caso base, a recursão nunca pára.
Quando se aplica
A recursão é natural quando o problema se repete com a mesma forma numa versão menor: o fatorial de n depende do fatorial de n − 1, a soma de 1 a n depende da soma de 1 a n − 1, e um texto depende do mesmo texto sem a primeira letra. Também é muito usada em estruturas com «caixas dentro de caixas», como pastas dentro de pastas.
Pré-requisitos
Saber escrever funções com def e return, usar condições if/else e perceber a diferença entre parâmetro e argumento. Ajuda ter noção de que cada chamada guarda os seus próprios valores locais, até receber a resposta da chamada seguinte.
Quando preferir um ciclo
Tudo o que se faz com recursão pode fazer-se com ciclos, e muitas vezes o ciclo é mais rápido e gasta menos memória. A recursão vale pela clareza quando a definição do problema já é recursiva.
Método passo a passo
- Descreva o problema e identifique o «tamanho» (um número n, o comprimento de um texto, o tamanho de uma lista).
- Encontre o caso base: o tamanho mais pequeno em que a resposta é imediata (n = 0, texto vazio, lista vazia).
- Escreva o passo recursivo: exprima a resposta para o tamanho n em função da resposta para um tamanho menor (n − 1, texto sem a primeira letra, etc.).
- Garanta que cada chamada se aproxima do caso base. Se o argumento não diminuir, nunca chega ao fim.
- Escreva o código: primeiro
ifcom o caso base ereturn; depois oreturncom a chamada recursiva. - Faça um teste de mesa com um valor pequeno, expandindo as chamadas e depois resolvendo-as de trás para a frente.
Esquema geral
def f(n): se n for o caso base: return resposta direta senão: return combinar(n, f(n menor))
Exemplos resolvidos
Exemplo 1 — Fatorial
Enunciado: Escreva fatorial(n) recursiva e calcule fatorial(4).
Resolução:
- Definição: n! = n × (n − 1)!, com 0! = 1.
- Caso base:
if n == 0: return 1. - Passo recursivo:
return n * fatorial(n - 1). - Expansão: fatorial(4) = 4 × fatorial(3) = 4 × (3 × fatorial(2)) = 4 × 3 × (2 × fatorial(1)) = 4 × 3 × 2 × (1 × fatorial(0)).
- fatorial(0) = 1, e resolve-se para trás: 1 × 1 = 1; 2 × 1 = 2; 3 × 2 = 6; 4 × 6 = 24.
Resposta: 24. Verificação: 4 × 3 × 2 × 1 = 24.
Exemplo 2 — Soma de 1 até n
Enunciado: Escreva soma(n) recursiva que devolva 1 + 2 + … + n. Calcule soma(4).
Resolução:
- Caso base:
if n == 0: return 0(a soma de nenhum termo é zero). - Passo recursivo:
return n + soma(n - 1). - Expansão: soma(4) = 4 + soma(3) = 4 + 3 + soma(2) = 4 + 3 + 2 + soma(1) = 4 + 3 + 2 + 1 + soma(0).
- Com soma(0) = 0 obtém-se 1, 3, 6 e 10 ao subir.
Resposta: 10. Verificação: 4 × 5 ÷ 2 = 10.
Exemplo 3 — Potência
Enunciado: Escreva potencia(base, exp) recursiva, com exp inteiro não negativo, e calcule potencia(2, 5).
Resolução:
- Ideia: be = b × b(e−1), e b0 = 1.
- Caso base:
if exp == 0: return 1. - Passo recursivo:
return base * potencia(base, exp - 1). - Expansão: 2 × potencia(2,4) = 2 × 2 × potencia(2,3) = … = 2 × 2 × 2 × 2 × 2 × potencia(2,0).
- Com potencia(2,0) = 1: 2, 4, 8, 16, 32.
Resposta: 32. Verificação: 25 = 32.
Exemplo 4 — Nível de exame: Fibonacci
Enunciado: Escreva fib(n) recursiva, com fib(0) = 0 e fib(1) = 1 e cada termo seguinte igual à soma dos dois anteriores. Calcule fib(5) e diga quantas chamadas são feitas.
Resolução:
- Dois casos base:
if n < 2: return n. - Passo recursivo:
return fib(n - 1) + fib(n - 2). - Sequência: fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5.
- Chamadas: se C(n) é o número de chamadas, C(0) = C(1) = 1 e C(n) = 1 + C(n−1) + C(n−2). Então C(2) = 3, C(3) = 5, C(4) = 9, C(5) = 15.
Resposta: fib(5) = 5, com 15 chamadas. Verificação: 3 + 2 = 5. O número de chamadas cresce muito depressa, por isso para n grande esta versão é lenta; um ciclo resolve melhor.
Erros frequentes
- Esquecer o caso base: a função chama-se sem fim e o Python acaba por dar
RecursionError. Escreva primeiro oifdo caso base. - Chamada que não se aproxima do caso base:
fatorial(n)a chamarfatorial(n)(oun + 1) nunca termina. O argumento tem de diminuir. - **Esquecer o
returnna chamada recursiva:** escreverfatorial(n - 1)semreturnperde o valor e a função devolveNone. - Caso base errado: em
soma, usar 1 em vez de 0 como valor da soma vazia dá um resultado desviado de uma unidade. - Usar recursão onde um ciclo bastava, em listas muito grandes: pode esgotar o limite de chamadas.
- Não testar com valores pequenos: teste 0, 1 e 2 antes de valores maiores.
Exercícios propostos
1Exercício 1
Escreva soma_digitos(n) recursiva que devolva a soma dos algarismos de um inteiro positivo. Calcule soma_digitos(345).
Ver dica
n % 10 é o último algarismo e n // 10 é o número sem ele.
Ver solução
Caso base: if n < 10: return n. Passo: return n % 10 + soma_digitos(n // 10). Para 345: 5 + soma_digitos(34) = 5 + (4 + soma_digitos(3)) = 5 + 4 + 3 = 12.
2Exercício 2
Calcule à mão potencia(3, 4) com a função do Exemplo 3, indicando cada passo.
Ver solução
potencia(3,4) = 3 × potencia(3,3) = 3 × 3 × potencia(3,2) = 3 × 3 × 3 × potencia(3,1) = 3 × 3 × 3 × 3 × potencia(3,0). Com potencia(3,0) = 1: 3, 9, 27, 81. Resultado: 81, pois 34 = 81.
3Exercício 3
Escreva inverter(texto) recursiva. Mostre as chamadas para "abc".
Ver dica
Inverter um texto é inverter o resto e pôr a primeira letra no fim. O resto é texto[1:].
Ver solução
Caso base: if len(texto) <= 1: return texto. Passo: return inverter(texto[1:]) + texto[0]. Para "abc": inverter("bc") + "a" = (inverter("c") + "b") + "a" = ("c" + "b") + "a" = "cba".
4Exercício 4
O código def contagem(n): com print(n) e contagem(n - 1) não tem caso base. O que acontece com contagem(3)? Corrija para parar em 1.
Ver solução
Mostra 3, 2, 1, 0, -1, -2… sem parar, até o Python lançar RecursionError por exceder o limite de chamadas. Correção: if n < 1: return no início. Com esse caso base, contagem(3) mostra 3, 2, 1 e termina.
5Exercício 5
Escreva mdc(a, b) recursiva pelo algoritmo de Euclides (caso base: b = 0, devolve a; passo: mdc(b, a % b)) e calcule mdc(48, 18).
Ver dica
Registe os pares (a, b) em cada chamada.
Ver solução
mdc(48,18): 48 % 18 = 12, logo mdc(18,12). 18 % 12 = 6, logo mdc(12,6). 12 % 6 = 0, logo mdc(6,0). Como b = 0, devolve 6. Resultado: 6. Verificação: 48 = 6 × 8 e 18 = 6 × 3, e 8 e 3 não têm divisor comum.
Perguntas frequentes
Quando se usa este método?
Quando o problema é definido em termos de si próprio numa versão menor: fatoriais, somas acumuladas, potências, percorrer pastas, divisão de listas ao meio. Se a solução natural for «repete N vezes», um ciclo basta.
Existe um método mais rápido?
Na maior parte dos casos, sim: um ciclo (iteração) usa menos memória e evita o limite de chamadas. No Fibonacci, por exemplo, um ciclo com duas variáveis é muito mais rápido que a versão recursiva simples. A recursão compensa pela clareza.
Que erros são mais comuns?
Falta do caso base, chamada que não reduz o problema e esquecer o return na chamada recursiva. Verifique sempre estas três coisas antes de executar.
O que é o RecursionError?
É o aviso do Python de que as chamadas encadeadas excederam o limite permitido. Quase sempre indica um caso base em falta ou mal escrito; confirme o limite exato na documentação da sua versão.
Resumo
- Recursão é uma função que se chama a si própria com um problema menor.
- Todo o algoritmo recursivo precisa de um caso base e de um passo que se aproxime dele.
- Faça o teste de mesa expandindo as chamadas e resolvendo de trás para a frente.
- Esquecer o
returnna chamada recursiva faz a função devolverNone. - Em muitos problemas, um ciclo é mais eficiente; a recursão ganha em clareza.
Onde aprofundar
- Manual e programa da disciplina de Programação da sua instituição (confirme a edição em vigor).
- Documentação oficial do Python, tutorial da linguagem, secção sobre definição de funções.
- CS50 da Universidade de Harvard, como referência pedagógica, na parte dedicada à recursão (confirme a versão atual).
Continue a estudar
Como escrever uma função passo a passo?
Para escrever uma função: 1) diga em frase o que ela faz, 2) escolha o nome e os parâmetros (entradas), 3) escreva o corpo, 4) devolva o resultado com return, 5) teste…
4 exemplos5 exercícios com solução✓ Estudado
Como instalar o Python no computador?
Descarregue o instalador no site oficial python.org, execute-o e, no Windows, marque a opção Add python.exe to PATH antes de instalar. Depois abra o terminal e escreva…
4 exemplos5 exercícios com solução✓ Estudado
Como declarar e usar variáveis?
Uma variável é um nome que guarda um valor na memória. Em Python declara-se atribuindo com o sinal =, por exemplo idade = 17: não é preciso indicar o tipo. Depois…
4 exemplos5 exercícios com solução✓ Estudado
Como escrever um programa para somar números até zero?
Em Python, use um acumulador total = 0, leia o primeiro número e repita com while n != 0: somando n ao total e lendo o número seguinte dentro do ciclo. O zero funciona…
4 exemplos5 exercícios com solução✓ Estudado