Recursion · Recursão
| English | Português |
|---|---|
| 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 |
A method that calls itself
- Recursion 递归 is when a method calls itself to solve a smaller version of the same problem.
- Every recursion needs two parts: a base case 基准情形 and a recursive case 递归情形.
- The base case stops the recursion — a small input the method answers directly.
- The recursive case calls the method again on a smaller input.
Um método que chama a si mesmo
- Recursão 递归 é quando um método se chama para resolver uma versão menor do mesmo problema.
- Toda recursão precisa de 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.
The base case
- Without a base case, a method calls itself forever — a
StackOverflowError. - The base case handles the smallest input without another call.
- Example:
factorial(0)returns1directly — no more calls. - Always check: does every path eventually reach the base case?
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?
The recursive case
- The recursive case does a little work, then calls itself on a smaller input.
factorial(n)returnsn * factorial(n - 1)— the input shrinks by one each call.- Each call waits for the smaller call to return before finishing.
- The calls stack up, hit the base case, then unwind 回退 back to the top.
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 se empilham, atingem o caso base e então desempilham 回退 back para o topo.
How the calls stack
factorial(3)→3 * factorial(2)→3 * (2 * factorial(1))→3 * (2 * (1 * factorial(0))).factorial(0)returns1; then the stack unwinds:1, 1, 2, 6.- Each call keeps its own copy of the parameters until it returns.
- Tracing a recursion means following the calls down, then the returns up.
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.
Every recursion needs a base case that stops it — and each recursive call must move TOWARD that base case (a smaller input). Miss the base case, or call on the same or a larger input, and the method recurses forever until a StackOverflowError. Trace by following calls down to the base case, then the returns back up.
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 by recursion:
- Base case:
if (n == 0) return 0; - Recursive case:
return n + sum(n - 1); sum(3)→3 + sum(2)→3 + (2 + sum(1))→ … →6.
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.
Recursion is a method calling itself on a smaller input. It needs a base case (stops directly, no more calls) and a recursive case (does a little work, then recurses on a smaller input). Calls stack down to the base case, then unwind back up. Miss the base case and you get a StackOverflowError.
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 · factorial(3) desenrola do caso base para cima
fact(0) returns 1 (base case); each parent multiplies: 1, 1, 2, 6. · fact(0) retorna 1 (caso base); cada pai multiplica: 1, 1, 2, 6.
A recursive method is one that... · Um método recursivo é aquele que...
Recursion = a method calling itself. · Recursão = um método chamando a si mesmo.
The base case is... · O caso base é...
The base case stops the recursion. · O caso base para a recursão.
A recursion with no reachable base case causes... · Uma recursão sem caso base alcançável causa...
It recurses forever until the stack overflows. · Ela recursa infinitamente até a pilha transbordar.
The recursive case must call itself on... · O caso recursivo deve chamar a si mesmo em...
Each call must shrink toward the base case. · Cada chamada deve encolher em direção ao caso base.
If factorial(0)=1 and factorial(n)=nfactorial(n-1), what is factorial(3)? · Se factorial(0)=1 e factorial(n)=nfactorial(n-1), qual é factorial(3)?
3 * 2 * 1 * 1 = 6.
Each recursive call keeps its own copy of its parameters until it returns. · Cada chamada recursiva mantém sua própria cópia de seus parâmetros até retornar.
Calls stack independently, then unwind. · Chamas empilham independentemente, depois desenrolam.