Recursão: caso base e caso recursivo
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.
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).
Example: power
power(b, e)meansb * b * ... * bwithecopies ofb. For examplepower(2, 3) = 8.- Base case:
power(b, 0)is1. - Recursive case:
power(b, e)isb * power(b, e - 1).
public class Main {
public static int power(int b, int e) {
if (e == 0) { // base case
return 1;
}
return b * power(b, e - 1); // recursive case: e gets smaller
}
public static void main(String[] args) {
System.out.println(power(2, 3)); // 8
System.out.println(power(5, 0)); // 1
}
}
How the calls unwind
- Each call waits for the smaller call to finish. Then it multiplies and returns.
- Trace
power(2, 3). Calls go down, then answers come back up.
power(2, 3) = 2 * power(2, 2) <- waits
power(2, 2) = 2 * power(2, 1) <- waits
power(2, 1) = 2 * power(2, 0) <- waits
power(2, 0) = 1 <- base case, returns 1
power(2, 1) = 2 * 1 = 2 <- returns 2
power(2, 2) = 2 * 2 = 4 <- returns 4
power(2, 3) = 2 * 4 = 8 <- returns 8
Example: count the digits
digits(n)counts the digits of a positive number. For exampledigits(4071) = 4.- Base case: a number below 10 has
1digit. - Recursive case:
n / 10drops the last digit, sodigits(n)is1 + digits(n / 10).
public class Main {
public static int digits(int n) {
if (n < 10) { // base case
return 1;
}
return 1 + digits(n / 10); // 4071 -> 407 -> 40 -> 4
}
public static void main(String[] args) {
System.out.println(digits(4071)); // 4
System.out.println(digits(7)); // 1
}
}
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, there is nothing left to count, so return
0. - Recursive case: look at
a[i], then letcountEven(a, i + 1)handle the rest.
public class Main {
public static int countEven(int[] a, int i) {
if (i >= a.length) { // base case: past the end
return 0;
}
int here = (a[i] % 2 == 0) ? 1 : 0;
return here + countEven(a, i + 1);
}
public static void main(String[] args) {
int[] nums = {4, 7, 10, 3, 6};
System.out.println(countEven(nums, 0)); // 3
}
}
- To cover the whole array you start at index
0:countEven(nums, 0). - Each call handles one value and trusts the next call for the rest.
Tracing a method that prints
The exam often asks what a recursive method prints. Here the print comes after the call, so the numbers come out in reverse order of the calls:
public class Main {
public static void mystery(int n) {
if (n > 0) {
mystery(n - 1);
System.out.print(n + " ");
}
}
public static void main(String[] args) {
mystery(3); // 1 2 3
System.out.println();
}
}
mystery(3) calls mystery(2), which calls mystery(1), which calls mystery(0) (does nothing). Then each call prints as it returns: 1, then 2, then 3. With the print before the call, the output would be 3 2 1.
Common mistakes
- Recursion needs a base case, or it throws StackOverflowError.
- Each call must move closer to the base case.
power(b, e + 1)never reachese == 0. - A recursive method that returns a value must
returnthe recursive call's result: writingpower(b, e - 1);alone throws the answer away.
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.
- Use Check answer to compile your code with the supplied tests and view the results. Keep the class and method interfaces shown in the starter.
Recursão: caso base + caso recursivo
Chamadas dividem até um caso base, depois as respostas retornam para cima.
Dificuldade 4/5 · Moedas 280 + pequeno bônus na primeira conclusão hoje
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.
Clique em Executar para ver a saída aqui.
Dificuldade 4/5 · Moedas 280 + pequeno bônus na primeira conclusão hoje
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.
Clique em Executar para ver a saída aqui.
Dificuldade 4/5 · Moedas 280 + pequeno bônus na primeira conclusão hoje
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.
Clique em Executar para ver a saída aqui.