Recursion: base case and recursive case · Recursão: caso base e caso recursivo
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · Esta página precisa de um navegador recente (com suporte a SharedArrayBuffer). Por favor, atualize Chrome, Edge, Firefox ou Safari para a versão mais recente.
English
A method that calls itself
- Recursion is when a method calls itself to solve a smaller piece of the same problem.
- On the AP CSA exam you mostly trace recursion (follow the calls by hand). Writing small recursive methods helps you trace well.
- Every recursive method needs two parts: a base case and a recursive case.
Português
Um método que se chama a si mesmo
- Recursão é quando um método se chama para resolver uma parte menor do mesmo problema.
- Na prova AP CSA você mostly rastreia recursão (siga as chamadas à mão). Escrever métodos recursivos pequenos ajuda a traçar bem.
- Todo método recursivo precisa de duas partes: um caso base e um caso recursivo.
English
Base case and recursive case
- Base case: the simplest input, where you return an answer without calling yourself. This stops the recursion.
- Recursive case: you call the same method with a smaller input, then build the answer.
- Without a base case, the method calls forever and crashes (a stack overflow).
Português
Caso base e caso recursivo
- Caso base: a entrada mais simples, onde você retorna uma resposta sem se chamar. Isso para a recursão.
- Caso recursivo: você chama o mesmo método com uma entrada menor, depois constrói a resposta.
- Sem um caso base, o método se chama infinitamente e falha (um estouro de pilha / stack overflow).
English
Example: factorial
factorial(n)meansn * (n-1) * ... * 1. For examplefactorial(4) = 24.- Base case:
factorial(1)is1. - Recursive case:
factorial(n)isn * factorial(n - 1).
Português
Exemplo: fatorial
factorial(n)significan * (n-1) * ... * 1. Por exemplofactorial(4) = 24.- Caso base:
factorial(1)é1. - Caso recursivo:
factorial(n)én * factorial(n - 1).
public class Recursion {
public static int factorial(int n) {
if (n <= 1) { // base case
return 1;
}
return n * factorial(n - 1); // recursive case
}
}
English
How the calls unwind
- Each call waits for the smaller call to finish. Then it multiplies and returns.
- Trace
factorial(3). Calls go down, then answers come back up.
Português
Como as chamadas são desfeitas
- Cada chamada espera a chamada menor terminar. Depois multiplica e retorna.
- Trace
factorial(3). As chamadas vão para baixo, depois as respostas voltam para cima.
factorial(3) = 3 * factorial(2) <- waits
factorial(2) = 2 * factorial(1) <- waits
factorial(1) = 1 <- base case, returns 1
factorial(2) = 2 * 1 = 2 <- returns 2
factorial(3) = 3 * 2 = 6 <- returns 6
English
Example: sum to n
sumTo(n)adds1 + 2 + ... + n. For examplesumTo(4) = 10.- Base case:
sumTo(0)is0(nothing to add). - Recursive case:
sumTo(n)isn + sumTo(n - 1).
Português
Exemplo: soma até n
sumTo(n)soma1 + 2 + ... + n. Por exemplosumTo(4) = 10.- Caso base:
sumTo(0)é0(nada para adicionar). - Caso recursivo:
sumTo(n)én + sumTo(n - 1).
public class Recursion {
public static int sumTo(int n) {
if (n <= 0) { // base case
return 0;
}
return n + sumTo(n - 1); // recursive case
}
}
English
Recursion over an array
- We can also recurse with an index that moves toward the end.
- Base case: when the index is past the last spot, return
0. - Recursive case: add
a[i]to the sum of the rest,arraySum(a, i + 1).
Português
Recursão sobre um array
- Nós também podemos recursar com um índice que avança em direção ao final.
- Caso base: quando o índice está além do último lugar, retorne
0. - Caso recursivo: adicione
a[i]à soma do restante,arraySum(a, i + 1).
English
- To sum the whole array you start at index
0:arraySum(a, 0). - Each call handles one value and trusts the next call for the rest.
Português
public class Recursion {
public static int arraySum(int[] a, int i) {
if (i >= a.length) { // base case: past the end
return 0;
}
return a[i] + arraySum(a, i + 1);
}
}
- Para somar todo o array, comece no índice
0:arraySum(a, 0). - Cada chamada trata um valor e confia na próxima chamada para o resto.
English
Common mistakes
- Recursion needs a base case, or it throws StackOverflowError.
- Each call must move closer to the base case.
Português
Erros comuns
- A recursão precisa de um caso base, ou lança StackOverflowError.
- Cada chamada deve se aproximar do caso base.
English
Now you try
- Each task gives you a method skeleton with a TODO. Write the base case and the recursive case.
- A hidden Harness calls your method with several values and checks the result.
- Press Run to compile, then Check answer.
Português
Agora você tenta
- Cada tarefa fornece um esqueleto de método com um TODO. Escreva o caso base e o caso recursivo.
- Um Harness oculto chama seu método com vários valores e verifica o resultado.
- Pressione Run para compilar, depois Check answer.
Explore · Explorar
Recursion: base + recursive case · Recursão: caso base + caso recursivo
Calls split until a base case, then answers return up. · Chamadas dividem até um caso base, depois as respostas retornam para cima.
Complete factorial(int n) so it returns n * (n-1) * ... * 1 using recursion. Use a base case for n <= 1. The checker tests several values. · Complete factorial(int n) para que ele retorne n * (n-1) * ... * 1 usando recursão. Use um caso base para n <= 1. O verificador testa vários valores.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Complete sumTo(int n) so it returns 1 + 2 + ... + n using recursion. Use a base case for n <= 0. The checker tests several values. · Complete sumTo(int n) para que ele retorne 1 + 2 + ... + n usando recursão. Use um caso base para n <= 0. O verificador testa vários valores.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Complete arraySum(int[] a, int i) so it returns the sum of a[i] to the end, using recursion. Base case: when i is past the last spot, return 0. The checker tests several arrays. · Complete arraySum(int[] a, int i) para retornar a soma de a[i] até o fim, usando recursão. Caso base: quando i estiver além do último lugar, retorne 0. O verificador testa vários arrays.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.