Recursão
Introduzido| English | Significado |
|---|---|
| Recursion/rɪˈkɜːʃn/ | Recursão |
| base case/beɪs keɪs/ | caso base |
| recursive case/rɪˈkɜːsɪv keɪs/ | caso recursivo |
| unwind/ʌnˈwaɪnd/ | desenrolar |
Um método que chama a si mesmo
- Recursão ocorre quando um método chama a si mesmo para resolver uma versão menor do mesmo problema.
- Toda recursão exige duas partes: um caso base e um caso recursivo.
- O caso base interrompe a recursão — uma entrada pequena que o método responde diretamente.
- O caso recursivo chama o método novamente em uma entrada menor.
O caso base
- Sem um caso base, um método chama a si mesmo para sempre — um
StackOverflowError. - O caso base lida com a entrada menor sem outra chamada.
- Exemplo:
factorial(0)retorna1diretamente — sem mais chamadas. - Sempre verifique: cada caminho eventualmente chega ao caso base?

Merge sort chama a si mesmo em cada metade, depois funde as metades ordenadas
O caso recursivo
- O caso recursivo faz um pouco de trabalho e depois chama a si mesmo com uma entrada menor.
factorial(n)retornan * factorial(n - 1)— a entrada diminui em um a cada chamada.- Cada chamada aguarda a chamada menor retornar antes de terminar.
- As chamadas empilham, atingem o caso base e então retrocedem até o topo.
Como as chamadas se empilham
factorial(3)→3 * factorial(2)→3 * (2 * factorial(1))→3 * (2 * (1 * factorial(0))).factorial(0)retorna1; então a pilha desempilha:1, 1, 2, 6.- Cada chamada mantém sua própria cópia dos parâmetros até que retorne.
- Rastrear uma recursão significa seguir as chamadas para baixo, e depois os retornos para cima.
Toda recursão precisa de um caso base que a interrompa — e cada chamada recursiva deve avançar EM DIREÇÃO a esse caso base (uma entrada menor). Perder o caso base ou chamar com a mesma entrada ou uma maior fará com que o método recorra indefinidamente até ocorrer um StackOverflowError. Faça o rastreamento seguindo as chamadas até o caso base e, em seguida, os retornos de volta para cima.
sum(n) = 1 + 2 + … + n por recursão:
- Caso base:
if (n == 0) return 0; - Caso recursivo:
return n + sum(n - 1); sum(3)→3 + sum(2)→3 + (2 + sum(1))→ … →6.
Recursão é um método chamando a si mesmo com uma entrada menor. Ela precisa de um caso base (interrompe diretamente, sem mais chamadas) e de um caso recursivo (faz um pouco de trabalho e depois recorre com uma entrada menor). As chamadas se empilham até o caso base e depois desempilham de volta para cima. Perder o caso base resulta em um StackOverflowError.
factorial(3) unwinds from the base case up
fact(0) returns 1 (base case); each parent multiplies: 1, 1, 2, 6.
A recursive method is one that...
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Recursion = a method calling itself.
The base case is...
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
The base case stops the recursion.
A recursion with no reachable base case causes...
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
It recurses forever until the stack overflows.
The recursive case must call itself on...
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Each call must shrink toward the base case.
If factorial(0)=1 and factorial(n)=n*factorial(n-1), what is factorial(3)?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
3 * 2 * 1 * 1 = 6.
Each recursive call keeps its own copy of its parameters until it returns.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Calls stack independently, then unwind.