Recursão: resolver usando o próprio problema
- 1. Aprenda
- 2. Confira
- 3. Pratique
A ideia principalRecursão é resolver um problema usando uma versão menor dele mesmo, até chegar num caso tão pequeno que a resposta é óbvia.
Para contar quantas pessoas há numa fila sem sair do lugar, você pergunta para quem está na sua frente: “quantas pessoas há na sua frente?”. Cada um faz a mesma pergunta para o da frente, até o primeiro responder “nenhuma”. Aí cada um soma 1 e passa a resposta de volta.
Toda recursão tem duas partes: o caso base (a resposta direta, que para a repetição) e o passo recursivo (chamar a mesma solução para um problema menor). Sem caso base, o programa nunca para.
fatorial(n):
se n == 1:
devolva 1 # caso base
devolva n × fatorial(n − 1) # passo recursivo
fatorial(4) = 4 × fatorial(3)
= 4 × 3 × fatorial(2)
= 4 × 3 × 2 × 1 = 24No dia a dia: Bonecas russas: para abrir todas, você abre uma e repete com a de dentro, até achar a menor, que não abre.
Palavras para lembrar
- Recursão
- uma função que chama a si mesma.
- Caso base
- a situação simples em que a recursão para.
Confira se entendeu
Agora pratique
Use o que você acabou de ler. Cada atividade conta no seu progresso: com 80% ou mais você fica proficiente em EF08CO01.
Outros assuntos do 8º ano
Habilidade EF08CO01 da BNCC: Construir soluções de problemas usando a técnica de recursão e automatizá-las com uma linguagem de programação. Professor(a): planos, slides e fichas na página da habilidade.