Recursión: caso base y caso recursivo
Un método que se llama a sí mismo
- Recursión: cuando un método se llama a sí mismo para resolver una parte más pequeña del mismo problema.
- En el examen AP CSA, generalmente rastreias la recursión (sigues las llamadas a mano). Escribir métodos recursivos pequeños te ayuda a rastrearlos mejor.
- Todo método recursivo necesita dos partes: un caso base y un caso recursivo.
Caso base y caso recursivo
- Caso base: la entrada más simple, donde devuelves una respuesta sin llamarte a ti mismo. Esto detiene la recursión.
- Caso recursivo: llamas al mismo método con una entrada más pequeña y luego construyes la respuesta.
- Sin un caso base, el método se llamará infinitamente y provocará un error (desbordamiento de pila).
Ejemplo: factorial
factorial(n)significan * (n-1) * ... * 1. Por ejemplo,factorial(4) = 24.- Caso base:
factorial(1)es1. - Caso recursivo:
factorial(n)esn * 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
}
}
Cómo se descomponen las llamadas
- Cada llamada espera a que la llamada más pequeña termine. Luego multiplica y devuelve el resultado.
- Rastrea
factorial(3). Las llamadas bajan hacia abajo, y luego las respuestas regresan hacia arriba.
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
Ejemplo: suma hasta n
sumTo(n)suma1 + 2 + ... + n. Por ejemplo,sumTo(4) = 10.- Caso base:
sumTo(0)es0(no hay nada que sumar). - Caso recursivo:
sumTo(n)esn + 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
}
}
Recursión sobre un array
- También podemos hacer recursión usando un índice que avanza hacia el final.
- Caso base: cuando el índice está pasado el último lugar, retorna
0. - Caso recursivo: suma
a[i]a la suma del resto,arraySum(a, i + 1).
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 sumar todo el array, empiezas en el índice
0:arraySum(a, 0). - Cada llamada maneja un solo valor y confía en la siguiente llamada para el resto.
Errores comunes
- La recursión necesita un caso base, o lanzará StackOverflowError.
- Cada llamada debe acercarse al caso base.
Ahora tú prueban
- Cada tarea te dará un esqueleto de método con un TODO. Escribe tanto el caso base como el caso recursivo.
- Una Harness oculta llamará a tu método con varios valores y verificará el resultado.
- Use Verificar respuesta para compilar su código con las pruebas proporcionadas y ver los resultados. Mantenga las interfaces de clase y método mostradas en el inicializador.
Recursión: caso base + caso recursivo
Las llamadas se dividen hasta un caso base, luego las respuestas regresan hacia arriba.
Dificultad 4/5 · 280 monedas + un pequeño bono en el primer intento de hoy
Completa factorial(int n) para que devuelva n * (n-1) * ... * 1 usando recursión. Usa un caso base para n <= 1. El verificador prueba varios valores.
Haz clic en Ejecutar para ver la salida aquí.
Dificultad 4/5 · 280 monedas + un pequeño bono en el primer intento de hoy
Completa sumTo(int n) para que devuelva 1 + 2 + ... + n usando recursión. Usa un caso base para n <= 0. El verificador prueba varios valores.
Haz clic en Ejecutar para ver la salida aquí.
Dificultad 4/5 · 280 monedas + un pequeño bono en el primer intento de hoy
Completa arraySum(int[] a, int i) para que devuelva la suma de a[i] hasta el final, usando recursión. Caso base: cuando i está más allá del último lugar, devuelve 0. El verificador prueba varios arrays.
Haz clic en Ejecutar para ver la salida aquí.