Pense Recursivamente: Base e Recursão
Divida um problema em cópias menores.
Pense Recursivamente: Base e Recursão é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 1 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que significa recursão
Recursão é uma função que resolve um problema chamando a si mesma para uma parte menor, até que essa parte seja pequena o suficiente para ser respondida diretamente. 🌀
Confie na cópia menor
A ideia principal é o salto de fé: suponha que a chamada recursiva já funcione para a entrada menor e, então, construa sua resposta com base nela.
Toda recursão precisa de um caso base
O caso base é a menor entrada que você responde sem fazer outra chamada recursiva. Sem ele, a função chama a si mesma para sempre e falha.
O caso recursivo
O caso recursivo reduz o problema e chama a si mesmo para a versão menor. Cada chamada precisa se aproximar do caso base.
Fatorial como primeiro exemplo
Aqui, fatorial mostra as duas partes: um caso-base em zero e uma chamada recursiva com n menos um.
def fact(n):
if n == 0:
return 1
return n * fact(n - 1)Como funciona a pilha de chamadas
Cada chamada aguarda na pilha de chamadas até que sua chamada interna retorne. A chamada mais profunda termina primeiro; depois, os resultados retornam até o início.
Observe a profundidade da recursão
Por padrão, o Python limita a profundidade da recursão a aproximadamente 1000. Recursões profundas em competições exigem sys.setrecursionlimit para evitar um erro em tempo de execução.
import sys
sys.setrecursionlimit(300000)Avance a cada chamada
Uma recursão correta sempre reduz a entrada em direção ao caso-base. Se em algum momento passar novamente pelo mesmo tamanho, entrará em um loop infinito. ⚠️
Some uma lista recursivamente
Esta soma recursiva remove o primeiro elemento e então confia na chamada para adicionar o restante da lista.
def total(a):
if not a:
return 0
return a[0] + total(a[1:])As árvores de recursão mostram a ramificação
Quando uma função faz mais de uma chamada, o trabalho forma uma árvore de recursão. O tamanho dela informa o custo total.
O trabalho repetido pode ser lento
O Fibonacci ingênuo recalcula os mesmos valores repetidamente, resultando em tempo exponencial. Memorizar essas respostas resolve o problema instantaneamente.
Verificação rápida
O que acontece se uma função recursiva não tiver um caso-base?
Recapitulação: duas partes, uma ideia
Você aprendeu que a recursão precisa de um caso-base para parar e de um caso recursivo que reduza a entrada. Confie na chamada menor, e o restante se resolverá. 🎯
Perguntas Frequentes
A aula “Pense Recursivamente: Base e Recursão” é grátis?
Sim — o texto completo de “Pense Recursivamente: Base e Recursão” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “Pense Recursivamente: Base e Recursão”?
Divida um problema em cópias menores. Você pratica Competitive Programming Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 1 de 4.
Quanto tempo leva a aula “Pense Recursivamente: Base e Recursão”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Pense Recursivamente: Base e Recursão
- Gere Todos os Subconjuntos
- Permutações e a Ideia das N-Rainhas
- Faça Poda para Sobreviver ao Limite de Tempo