Passo 1 de 7
Definir o problema menor e o caso base
Planeje a soma recursiva delimitando o domínio, definindo uma resposta imediata e escolhendo uma redução que chegue ao caso base.
Trilha de aprendizado · Nível 4 · Tutorial 7
Implemente soluções recursivas simples, acompanhe suas chamadas e garanta que cada etapa avance até um caso base explícito.
Definir o problema menor e o caso base
Planeje a soma recursiva delimitando o domínio, definindo uma resposta imediata e escolhendo uma redução que chegue ao caso base. 3 min
Transformar o plano em uma função recursiva
Implemente a soma de 1 até n com um retorno para o caso base e outro para o passo recursivo. 3 min
Acompanhar a descida das chamadas e a volta dos resultados
Rastreie uma execução curta da soma recursiva, observando estados locais, operações pendentes e retornos. 4 min
Encontrar falhas no caminho até o caso base
Inspecione sequências curtas de argumentos para diagnosticar reduções que não alcançam o caso base e corrigir a função sem esconder o defeito. 3 min
Reconhecer o limite de profundidade
Interprete RecursionError e diferencie uma falha de progresso de uma sequência recursiva correta, porém profunda demais. 2 min
Escolher entre recursão e laço
Compare duas soluções para a mesma soma e escolha a abordagem considerando clareza e profundidade esperada. 2 min
Aplicar e revisar o raciocínio recursivo
Transfira o raciocínio recursivo para o cálculo de potências, confira sua implementação e revise os critérios de uma solução que termina corretamente. 4 min
Passo 1 de 7
Planeje a soma recursiva delimitando o domínio, definindo uma resposta imediata e escolhendo uma redução que chegue ao caso base.
Na recursão direta, uma função resolve o problema chamando a si mesma para uma versão menor do mesmo problema.
Nosso exemplo será a soma dos inteiros de 1 até n. Antes de pensar no código, defina o contrato:
n é um inteiro não negativo.1 até n.Assim, para n = 4, o resultado é 1 + 2 + 3 + 4 = 10. A precondição delimita quando a solução deve funcionar; entradas negativas não pertencem ao domínio declarado.
Exemplo
Para calcular a soma até 4, separe o valor atual do restante:
S(4) = 4 + S(3)
O problema S(3) é menor, mas continua sendo a mesma tarefa: somar os inteiros de 1 até um limite.
Uma definição recursiva precisa de duas decisões:
n = 0, a soma é 0.n > 0, use n - 1.A sequência 4 → 3 → 2 → 1 → 0 chega ao caso base. Chamamos n de medida de progresso: é o valor que diminui a cada redução e permite verificar que o processo se aproxima do encerramento.
Acompanhe como o tamanho restante do problema diminui de uma etapa para a seguinte.
Cada redução subtrai uma unidade de n; em n = 0, a resposta é imediata e não há nova redução.
Qual plano descreve corretamente a soma dos inteiros de 1 até n e garante que a redução alcance o caso base?
Passo 2 de 7
Implemente a soma de 1 até n com um retorno para o caso base e outro para o passo recursivo.
A função segue o plano definido anteriormente:
n == 0, return 0 encerra a chamada antes de qualquer nova chamada.soma_ate(n - 1) resolve o problema menor.n + ... combina o valor atual com o resultado desse subproblema.Os dois caminhos usam return, pois ambos precisam entregar um resultado ao código que chamou a função.
O primeiro return resolve o caso base. O segundo reduz o argumento e compõe a resposta.
def soma_ate(n: int) -> int:
"""Retorna a soma de 1 até n.
Precondição: n é um inteiro não negativo.
"""
if n == 0:
return 0
return n + soma_ate(n - 1)
O caminho base termina sem nova chamada; o caminho recursivo reduz o problema e usa o resultado devolvido.
Copie o programa completo para seu editor e execute-o. Antes de conferir a saída, preveja o resultado de cada chamada. Observe que soma_ate(0) usa somente o caminho base, enquanto as outras chamadas também usam o caminho recursivo.
Execute este código com Python 3 no seu computador.
def soma_ate(n: int) -> int:
"""Retorna a soma de 1 até n.
Precondição: n é um inteiro não negativo.
"""
if n == 0:
return 0
return n + soma_ate(n - 1)
print(soma_ate(0))
print(soma_ate(1))
print(soma_ate(4))Exemplo
0
1
10Se o resultado for diferente, confira se há um return em cada caminho e se a nova chamada recebe n - 1.
Complete apenas o argumento da chamada recursiva:
return n + soma_ate(____)
Quais valores são devolvidos, respectivamente, por soma_ate(0) e soma_ate(3)?
Passo 3 de 7
Rastreie uma execução curta da soma recursiva, observando estados locais, operações pendentes e retornos.
Em soma_ate(3), uma chamada precisa do resultado da seguinte antes de concluir sua soma. Durante a descida:
n;Assim, soma_ate(3) aguarda 3 + soma_ate(2), enquanto soma_ate(2) aguarda 2 + soma_ate(1). A pilha de chamadas representa essas chamadas abertas que ainda não terminaram.
Para uma entrada pequena, acompanhe primeiro as chamadas e depois os retornos.
def soma_ate(n: int) -> int:
"""Retorna a soma de 1 até n.
Precondição: n é um inteiro não negativo.
"""
if n == 0:
return 0
return n + soma_ate(n - 1)
print(soma_ate(3)) # 6A descida abre as chamadas com argumentos 3 → 2 → 1 → 0. Em soma_ate(0), o caso base devolve 0 sem abrir outra chamada.
Começa então a volta, em ordem inversa:
soma_ate(1) resolve 1 + 0 e devolve 1;soma_ate(2) resolve 2 + 1 e devolve 3;soma_ate(3) resolve 3 + 3 e devolve 6.Cada retorno fornece o valor necessário para resolver uma operação que estava pendente.
Compare a abertura das chamadas com a resolução das somas.
Na descida, as operações ficam pendentes. Na volta, os resultados percorrem as chamadas em ordem inversa.
Coloque os eventos de soma_ate(3) na ordem em que acontecem.
Durante soma_ate(3), qual descrição de soma_ate(2) está correta?
Passo 4 de 7
Inspecione sequências curtas de argumentos para diagnosticar reduções que não alcançam o caso base e corrigir a função sem esconder o defeito.
Uma função recursiva precisa ter um caminho que devolva um resultado sem nova chamada. Além disso, cada chamada recursiva deve aproximar uma entrada válida do caso base.
Para diagnosticar uma falha, anote apenas os primeiros argumentos. Não execute uma cadeia que você já percebeu que não termina.
Considere o mesmo contrato: n é um inteiro não negativo e o resultado deve ser a soma de 1 até n. Inspecione as funções sem executar chamadas que não terminam.
def soma_a(n: int) -> int:
return n + soma_a(n - 1)
def soma_b(n: int) -> int:
if n == 0:
return 0
return n + soma_b(n)
def soma_c(n: int) -> int:
if n == 0:
return 0
return n + soma_c(n - 2)A sequência de argumentos revela defeitos diferentes:
soma_a(3): 3 → 2 → 1 → 0 → -1... — não existe um caso base que encerre a chamada.soma_b(3): 3 → 3 → 3... — o argumento permanece igual.soma_c(3): 3 → 1 → -1 → -3... — a redução parece diminuir, mas salta o caso base 0. Além disso, diminuir de dois em dois não representa a soma de todos os inteiros.A entrada 3 pertence ao domínio declarado. Portanto, essas falhas violam o contrato. Já chamar a implementação correta com n = -1 estaria fora do domínio documentado e seria outro problema.
Observe se há uma parada explícita e se cada redução realmente chega até ela para todas as entradas válidas.
Dica
A correção deve preservar o domínio e o resultado esperado. Trocar o caso base apenas para interromper uma redução inadequada pode esconder a falha sem calcular a soma correta. Neste problema, a redução coerente continua sendo n - 1.
Associe cada função ao defeito principal.
Toque em um item e depois no par correspondente.
Corrija apenas o passo recursivo de soma_c para calcular a soma de 1 até n. Depois, mostre a sequência de argumentos a partir de n = 3 e explique por que ela alcança o caso base.
Escreva pelo menos 30 caracteres (0/30).
Passo 5 de 7
Interprete RecursionError e diferencie uma falha de progresso de uma sequência recursiva correta, porém profunda demais.
O Python limita a profundidade das chamadas aninhadas. Quando uma execução recursiva ultrapassa o limite disponível, ela é interrompida com RecursionError.
Esse erro pode ocorrer mesmo quando existem um caso base correto e uma redução que progride até ele. Uma entrada muito grande pode exigir mais chamadas simultâneas do que o ambiente permite.
A profundidade disponível depende do ambiente e do contexto da execução. Portanto, não suponha um número universal de chamadas.
Exemplo
Uma execução pode terminar com uma mensagem semelhante a esta:
Traceback (most recent call last):
...
RecursionError: maximum recursion depth exceededA última linha identifica o tipo do erro. Isoladamente, ela informa que a profundidade máxima foi excedida, mas não revela se houve uma falha lógica ou apenas chamadas corretas em quantidade excessiva.
Para interpretar o erro, verifique alguns argumentos sucessivos:
Assim, RecursionError é um sintoma. O caminho das chamadas ajuda a identificar a causa.
Compare uma cadeia que não se aproxima do encerramento com outra que progride, mas encontra o limite antes de chegar ao caso base.
À esquerda, a medida do problema não muda. À direita, ela diminui, mas a quantidade de chamadas aninhadas ultrapassa o limite disponível.
Atenção
Aumentar o limite de profundidade não corrige uma função cujo argumento não progride até o caso base. Primeiro confirme o domínio, o caso base e a sequência de reduções. Mesmo com a lógica correta, uma solução que exige chamadas demais pode pedir outra abordagem.
A função soma_ate possui o caso base n == 0, usa n - 1 e funciona para entradas pequenas. Se uma entrada muito maior produzir RecursionError, isso prova que o caso base está ausente.
Passo 6 de 7
Compare duas soluções para a mesma soma e escolha a abordagem considerando clareza e profundidade esperada.
As duas funções abaixo calculam a soma dos inteiros de 1 até n, considerando n um inteiro não negativo. A versão recursiva expressa diretamente a definição n + soma_ate(n - 1). A versão iterativa percorre os valores e mantém o resultado parcial em um acumulador.
Cada chamada deixa uma soma pendente até que o caso base seja alcançado.
def soma_ate(n: int) -> int:
"""Retorna a soma de 1 até n.
Precondição: n é um inteiro não negativo.
"""
if n == 0:
return 0
return n + soma_ate(n - 1)O acumulador é atualizado a cada repetição e devolvido ao final.
def soma_ate_iterativa(n: int) -> int:
"""Retorna a soma de 1 até n.
Precondição: n é um inteiro não negativo.
"""
total = 0
for valor in range(1, n + 1):
total += valor
return totalNa recursão, soma_ate(3) abre chamadas para 2, 1 e 0. As operações ficam pendentes e são resolvidas durante a volta. No laço, uma única chamada atualiza total sucessivamente: 0 → 1 → 3 → 6.
A recursão pode ser mais clara quando o problema já é definido naturalmente por versões menores de si mesmo. Para esta soma linear, porém, o laço representa bem a repetição e não cria uma cadeia de chamadas aninhadas.
À esquerda, várias chamadas permanecem abertas; à direita, uma única chamada atualiza o resultado parcial.
Dica
Recursão não é automaticamente melhor nem mais rápida. Compare a clareza da solução com a profundidade esperada. Para uma soma que pode exigir muitos milhares de etapas, o laço geralmente é mais adequado porque evita uma cadeia profunda de chamadas.
Pergunte: a definição recursiva torna o raciocínio mais claro? E quantas chamadas podem ficar aninhadas? Uma entrada pequena pode tornar a versão recursiva fácil de acompanhar. Se a mesma tarefa linear puder exigir uma quantidade muito grande de etapas, a versão iterativa evita o limite de profundidade sem alterar o resultado.
Uma equipe usa a soma de 1 até n em dois contextos: uma demonstração com n pequeno e um processamento que pode receber valores muito grandes. Qual avaliação é mais adequada?
Passo 7 de 7
Transfira o raciocínio recursivo para o cálculo de potências, confira sua implementação e revise os critérios de uma solução que termina corretamente.
Crie no seu editor a função potencia(base, expoente) para calcular uma potência por multiplicações sucessivas.
O contrato será:
base é um inteiro positivo e expoente é um inteiro não negativo.base elevado a expoente.1.No passo recursivo, combine a base atual com o resultado do subproblema. Não use ** nem um laço nesta primeira implementação.
Escreva a função no espaço indicado e execute o programa completo no seu computador.
def potencia(base: int, expoente: int) -> int:
"""Retorna base elevada a expoente.
Precondições: base é um inteiro positivo e expoente é
um inteiro não negativo.
"""
# Escreva aqui o caso base e o passo recursivo.
print(potencia(2, 0)) # esperado: 1
print(potencia(5, 1)) # esperado: 5
print(potencia(3, 4)) # esperado: 81Dica
Preveja os três resultados, execute seu código e investigue qualquer diferença. Verifique principalmente se o caso base usa return e se o passo recursivo reduz o expoente.
Depois de executar sua solução, registre:
potencia(3, 2) e os valores devolvidos durante a volta.expoente - 2, mantendo apenas o caso base expoente == 0, para a entrada expoente = 3.Escreva pelo menos 180 caracteres (0/180).
Agora compare sua implementação com a referência. O expoente é a medida de progresso: ele diminui de um em um até zero. Na volta, cada chamada multiplica a base pelo resultado recebido.
Para potencia(3, 2), as chamadas recebem os expoentes 2 → 1 → 0; os retornos são 1 → 3 → 9. Se a redução fosse de duas unidades, o expoente 3 seguiria 3 → 1 → -1... e saltaria o único caso base.
Compare o caso base, o argumento da chamada recursiva e a composição do retorno.
def potencia(base: int, expoente: int) -> int:
"""Retorna base elevada a expoente.
Precondições: base é um inteiro positivo e expoente é
um inteiro não negativo.
"""
if expoente == 0:
return 1
return base * potencia(base, expoente - 1)
print(potencia(2, 0)) # 1
print(potencia(5, 1)) # 5
print(potencia(3, 4)) # 81Use este esquema para revisar qualquer solução recursiva simples: o contrato delimita as entradas, o caso base encerra uma chamada, a redução garante progresso e a composição produz a resposta durante a volta.
Uma solução recursiva precisa ser correta no caso base, avançar em todas as entradas do domínio e ter profundidade adequada.
Resumo
Antes de considerar uma solução recursiva concluída, revise estes pontos.
return.Parabéns! Você concluiu: Resolver problemas com recursão e casos base
Você concluiu “Resolver problemas com recursão e casos base”. Agora consegue identificar o contrato, o caso base, a redução, a composição dos retornos e os limites práticos de uma solução recursiva.
100 XP
Você concluiu este nível!
Agora você vai iniciar: Módulos, ambientes e dependências
Separar código em módulos e usar importações explícitasSeparar funções e constantes em arquivos reutilizáveis e acessar esses recursos por meio de importações que deixam clara a origem dos nomes.Milhares de cursos online em vídeo, ebooks e áudiobooks.
Para testar seus conhecimentos no decorrer dos cursos online
Gerado diretamente na galeria de fotos do seu celular e enviado ao seu e-mail
Baixe nosso aplicativo pelo QR Code ou pelos links abaixo:.
Leve o conhecimento no seu bolso.
Baixe o aplicativo Cursa.
São centenas de Cursos gratuitos a disposição, com Certificado de conclusão gratuito que é salvo em sua galeria de imagens do celular.
Baixe o app para ter acesso ao Certificado de conclusão de Curso Gratuitamente.
+ de 10 milhões
de alunos
Certificado grátis e
válido em todo o Brasil
60 mil exercícios
gratuitos
4,8/5 classificação
nas lojas de apps
Cursos gratuitos em
vídeo, ebooks e audiobooks