Padrão 1: contar com n - 1
objetivo O molde que resolve metade dos exercícios de número.
O molde é sempre o mesmo: o caso base trata o menor valor possível, e o caso recursivo combina o n atual com o resultado de n - 1.
Muda só o que você faz com o n: somar, multiplicar, contar 1, ou ignorar quando não serve.
Quando o problema diminui pela METADE em vez de um por vez, o passo vira n / 2. É o caso de testar potência de 2 e de contar quantas metades cabem até chegar em 1.
Onde todo mundo escorrega
- O caso base precisa cobrir o menor valor que o enunciado permite. Se b pode ser 0, o base é b == 0.
- Com passo n / 2, teste o n ímpar: muitas vezes ele é a resposta negativa do exercício.
Desafio
Escreva somaImpares, que devolve a soma de todos os números ímpares de 1 até n. Exemplo: somaImpares(6) é 1 + 3 + 5, ou seja, 9.
int somaImpares(int n)| chamada | saída esperada |
|---|---|
| somaImpares(5) | 9 |
| somaImpares(6) | 9 |
| somaImpares(1) | 1 |
| somaImpares(10) | 25 |
int somaImpares(int n) {
// caso base: quando nao sobrou numero nenhum
// se n for par, pule ele
// se for impar, some com o resto
}Ctrl+Enter (Cmd+Enter no Mac) roda. Esc sai do editor.
Ver a pilha de chamadas passo a passo
Mostra o que o seu código faz em cada chamada. É uma simulação didática, não substitui o botão de testar.
Dicas
Tenta sozinho primeiro. Travou de verdade, abre a primeira.