Caso base y caso recursivo: las dos unicas piezas.
Toda recursion son dos piezas: donde paro, y como me acerco a ese punto.
Imagina que estas en una fila larga y quieres saber cuantas personas hay delante. No las cuentas tu: le preguntas al de adelante "cuantos hay delante tuyo?", y a su respuesta le sumas uno. El primero de la fila responde "cero" sin preguntarle a nadie: ese es el caso base. Tu no necesitas ver toda la fila para responder bien.
Un metodo recursivo resuelve un problema resolviendo una version mas pequena del mismo problema. Nada mas. Y para no caer al vacio necesita saber cuando parar.
public static int factorial(int n) {
if (n <= 1) { // caso base
return 1;
}
return n * factorial(n - 1); // caso recursivo
}
Dos lineas conceptuales: donde paro, y como me acerco a ese punto.
1. Debe existir un caso base. Al menos una entrada para la cual el metodo responde sin volver a llamarse.
2. El caso recursivo debe acercarse al caso base. Si llamas factorial(n) desde factorial(n), el problema nunca encoge.
3. Confia en la llamada recursiva. Esto se llama el salto de fe: al escribir factorial(n-1) asume que ya devuelve el factorial correcto de n-1. No intentes seguir mentalmente todos los niveles, te vas a perder.
Para escribir sumaHasta(n) que suma 1+2+...+n, no pienses en la cadena completa. Piensa solo esto: "si alguien ya me diera la suma hasta n-1, que le hago?". Le sumas n. Y ya esta. Esa frase es literalmente el codigo.
public static int sumaHasta(int n) {
if (n == 0) return 0;
return n + sumaHasta(n - 1);
}
Aqui es donde la teoria de arriba se vuelve concreta. Cambia los parametros, dale a Reproducir, y sobre todo usa las flechas para ir paso a paso: la velocidad automatica sirve para ver la forma general, pero lo que de verdad ensena es detenerse en un retorno y entender por que vuelve ahi y no a otro lado.
No son ejemplos inventados: son los que aparecen una y otra vez en los parciales. Lee el codigo, decide tu mismo que esta mal, y solo despues abre la correccion. Si la abres de una, no aprendes nada.
public static int factorial(int n) {
return n * factorial(n - 1);
}
Nunca para. Baja a 0, a -1, a -2... hasta que la pila se llena y la JVM lanza StackOverflowError.
public static int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
public static int sumaHasta(int n) {
if (n == 0) return 0;
return n + sumaHasta(n);
}
Hay caso base, pero la llamada usa el mismo n. El caso base jamas se alcanza.
public static int sumaHasta(int n) {
if (n == 0) return 0;
return n + sumaHasta(n - 1);
}
Responde sin devolverte a leer. Si fallas no pasa nada: la explicacion te dice exactamente donde estaba el hueco, y ese es el momento en que de verdad se aprende. Con el 70% el nivel queda aprobado.