Nome:Turma:Data:
Computação · 8º ano · Recursão desplugada
Fila recursiva e fatorial
BNCC: EF08CO01 Construir soluções de problemas usando a técnica de recursão e automatizá-las com uma linguagem de programação.
Na recursão, um problema é resolvido usando o mesmo problema, só que menor. Ela sempre precisa de um caso base, a situação em que para.
1. A fila recursiva
Seis pessoas estão em fila. A última quer saber quantas pessoas há na frente dela. Cada uma só pode perguntar à pessoa da frente e responder a quem está atrás. A primeira da fila sabe que não há ninguém na frente: esse é o caso base.
| Pessoa | 6ª (última) | 5ª | 4ª | 3ª | 2ª | 1ª |
|---|---|---|---|---|---|---|
| Ida: pergunta para | 5ª | ninguém | ||||
| Volta: responde | 0 |
2. Fatorial
fatorial(n) = n × fatorial(n − 1), e fatorial(1) = 1. Complete as chamadas e depois volte calculando.
| Chamada | Vira | Resultado na volta |
|---|---|---|
| fatorial(5) | 5 × fatorial(4) | |
| fatorial(4) | ||
| fatorial(3) | ||
| fatorial(2) | ||
| fatorial(1) | caso base: 1 | 1 |
3. Escreva a sua
A função soma(n) soma todos os números de 1 até n. Complete:
soma(n):
se n = 1 então
devolva ____
senão
devolva n + soma(____)
fim
Quanto é soma(4)? Mostre as chamadas:
4. Sem caso base
O que aconteceria se a função fatorial não tivesse o caso base?