Nivel 1 · Anatomia de un metodo recursivo

Un metodo que se llama a si mismo

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.

Las tres reglas

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.

El salto de fe, en concreto

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);
}

Ejecuta y observa

Cambia los parametros, dale a Reproducir, y usa las flechas para avanzar paso a paso. La pila crece hacia arriba: el marco de arriba es el que se esta ejecutando ahora mismo.

Errores que vas a cometer

Lee el codigo, decide que esta mal, y despues abre la correccion.

Falta el caso base

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);
}

El problema no encoge

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);
}

Comprueba lo que entendiste

Necesitas el 70% para dar el nivel por visto. Responde sin devolverte a la teoria: si fallas, la explicacion te dice exactamente donde estaba el hueco.