Funções
Recursão: a fila do cinema no escuro
Uma função que chama ela mesma, com um problema menor.
Na vida real
Cinema escuro, você quer saber em que fileira está. Não dá pra contar. Então você pergunta pra pessoa da frente: "qual a sua fileira?". Ela também não sabe e pergunta pra da frente dela... até chegar na primeira fileira, que sabe: "sou a 1". Aí a resposta volta: cada um soma 1 e passa pra trás. Recursão é isso: ida perguntando, volta respondendo.
Código
int fatorial(int n) { if (n == 1) return 1; return n * fatorial(n - 1);}passo 1 de 12
Também dá pra usar as setas ← e → do teclado.
O que o computador está vendo
Pilha de chamadas (a de cima está rodando)
fatorial(3) (rodando agora)n = 3
Tela
Chamou
fatorial(3). Abre uma caixinha nova em cima da pilha, com n = 3.Peça por peça
| Peça | O que significa |
|---|---|
| if (n == 1) return 1; | PARA. A primeira fileira: o caso em que você já sabe a resposta. Sem ele, nunca para. |
| fatorial(n - 1) | DIMINUI. Pergunta pra pessoa da frente: o mesmo problema, um pouco menor. |
| n * ... | JUNTA. Quando a resposta volta, você faz a sua parte (aqui, multiplica). |
| return | Obrigatório na frente da chamada. Senão a resposta se perde no caminho. |
A receita de toda recursão
PARAQual o caso mais pequeno que eu já sei a resposta? Vai no if.
DIMINUIChama a mesma função com algo menor.
JUNTAFaz a sua parte com a resposta que voltou.
Qual "menor" usar? Olhe a palavra do enunciado
| Enunciado fala de | Chama com | Para quando | Pedaço atual |
|---|---|---|---|
| até n, fatorial, potência | n - 1 | n == 0 (ou 1) | n |
| dígitos, algarismos | n / 10 | n == 0 | n % 10 |
| vetor, elementos | v, n - 1 | n == 0 | v[n - 1] |
| string, palavra, letras | s + 1 | s[0] == '\0' | s[0] |
E o que devolver quando para: somar ou contar devolve 0, multiplicar devolve 1, void só dá return;.
Teste rápido: O que acontece se você esquecer o if (n == 1)?