Recursividad en Java

Un método recursivo es un método que se llama a sí mismo. Suena a trampa, pero es una forma muy natural de resolver problemas que contienen una versión más pequeña de sí mismos: el factorial de 5 depende del factorial de 4, una carpeta contiene otras carpetas, un menú tiene submenús. En esta lección aprenderás a escribir métodos recursivos que terminan, a entender qué ocurre en memoria con cada llamada y a decidir cuándo conviene la recursión y cuándo un bucle de toda la vida.

Necesitas manejar bien los métodos.

La idea: un problema dentro de otro

Piensa en una cola de personas en la puerta de un concierto. Quieres saber en qué posición estás, pero solo ves a la persona de delante. Le preguntas: “¿Qué posición tienes tú?”. Ella hace la misma pregunta a la de delante, y así sucesivamente, hasta llegar a la primera, que responde “la 1” sin preguntar a nadie. Cada persona suma 1 a la respuesta que recibe y la pasa hacia atrás.

Ese razonamiento tiene las dos piezas de toda recursión:

• Caso base: la situación tan sencilla que se responde directamente, sin volver a llamar. La primera persona de la cola sabe que es la 1.
• Caso recursivo: la situación en la que el método se llama a sí mismo con un problema más pequeño y usa el resultado. “Mi posición es la de delante más 1”.

Si falta el caso base, o si el caso recursivo no acerca el problema a él, las llamadas no terminan nunca.

Tu primer método recursivo

Una cuenta atrás para un lanzamiento:

public class Lanzamiento {

    static void cuentaAtras(int n) {
        if (n == 0) {                        // caso base
            System.out.println("¡Despegue!");
            return;
        }
        System.out.println(n);
        cuentaAtras(n - 1);                  // caso recursivo, con n más pequeño
    }

    public static void main(String[] args) {
        cuentaAtras(3);
    }
}

3
2
1
¡Despegue!

cuentaAtras(3) imprime 3 y llama a cuentaAtras(2), que imprime 2 y llama a cuentaAtras(1), que imprime 1 y llama a cuentaAtras(0). Esta última entra en el caso base y ya no llama a nadie. Cada llamada recibe un n una unidad menor, así que siempre se llega a 0.

Consejo: escribe siempre el caso base lo primero dentro del método. Así se lee de un vistazo cuándo termina la recursión.

Factorial: devolver un valor

El factorial de un número (se escribe 5!) es el producto de todos los enteros desde 1 hasta él: 5! = 5 · 4 · 3 · 2 · 1 = 120. Fíjate en que 5! = 5 · 4!, y 4! = 4 · 3!. Es decir, el factorial se define usando otro factorial más pequeño. Por convenio, 0! = 1 y 1! = 1.

static long factorial(int n) {
    if (n <= 1) {
        return 1;                    // caso base: 0! y 1! valen 1
    }
    return n * factorial(n - 1);     // caso recursivo
}

System.out.println(factorial(5));  // 120
System.out.println(factorial(0));  // 1
System.out.println(factorial(20)); // 2432902008176640000

Devuelve long porque el factorial crece muy deprisa. Aun así, factorial(21) ya no cabe en un long y da un resultado absurdo (-4249290049419214848) por desbordamiento, como viste en variables. Para números más grandes se usa BigInteger.

Cómo se resuelve paso a paso

Al llamar a factorial(4) ocurre esto:

factorial(4) = 4 * factorial(3)
                   factorial(3) = 3 * factorial(2)
                                      factorial(2) = 2 * factorial(1)
                                                         factorial(1) = 1   <- caso base
                                      factorial(2) = 2 * 1 = 2
                   factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24

Primero las llamadas bajan hasta el caso base y ninguna multiplicación se puede hacer todavía: cada una espera el resultado de la siguiente. Después los resultados suben y cada llamada termina su cuenta.

La pila de llamadas

¿Dónde esperan esas llamadas a medio terminar? En la pila de llamadas (call stack), una zona de memoria que la JVM usa para los métodos en curso. Cada vez que llamas a un método, se apila un marco con sus parámetros y variables locales. Cuando el método termina, su marco se retira y la ejecución vuelve al que lo llamó.

Así se ve la pila en el momento en que factorial(4) llega al caso base:

| factorial(1)   n = 1  |  <- cima: se está ejecutando
| factorial(2)   n = 2  |  esperando
| factorial(3)   n = 3  |  esperando
| factorial(4)   n = 4  |  esperando
| main                  |

Cada marco tiene su propia variable n. No se pisan entre sí, aunque todas se llamen igual: son variables locales de llamadas distintas.

StackOverflowError: cuando la pila se llena

La pila tiene un tamaño limitado. Si un método recursivo no llega nunca al caso base, sigue apilando marcos hasta que no cabe ninguno más y el programa se detiene:

static int sumarHasta(int n) {
    return n + sumarHasta(n - 1);   // falta el caso base
}

Exception in thread "main" java.lang.StackOverflowError
	at Main.sumarHasta(Main.java:3)
	at Main.sumarHasta(Main.java:3)
	at Main.sumarHasta(Main.java:3)
	...

La traza repite la misma línea cientos de veces: es la señal de una recursión infinita. La versión correcta añade el caso base:

static int sumarHasta(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sumarHasta(n - 1);
}

Cuidado: aunque el caso base exista, una recursión demasiado profunda también desborda la pila. Con la configuración por defecto, unas pocas miles de llamadas anidadas ya pueden fallar (el límite exacto depende del sistema y de cuánta memoria use cada marco). Por eso la recursión no es buena idea para recorrer, por ejemplo, un millón de elementos uno a uno.

StackOverflowError no es una excepción normal, sino un error de la JVM. No se debe capturar con try-catch para “arreglarlo”: hay que corregir el método. Verás la diferencia entre errores y excepciones en excepciones.

Fibonacci: cuando la recursión ingenua es lenta

La sucesión de Fibonacci empieza por 0 y 1, y cada número es la suma de los dos anteriores: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55… La definición es recursiva de forma natural:

static long fibonacci(int n) {
    if (n <= 1) {
        return n;                                  // fib(0) = 0, fib(1) = 1
    }
    return fibonacci(n - 1) + fibonacci(n - 2);    // dos llamadas recursivas
}

System.out.println(fibonacci(10)); // 55
System.out.println(fibonacci(30)); // 832040

Funciona, pero prueba con fibonacci(50) y tu programa se quedará pensando más de un minuto. ¿Por qué? Porque cada llamada provoca dos llamadas, y muchas repiten el mismo trabajo:

Para calcular fib(5) se calcula fib(3) dos veces y fib(2) tres veces, y el problema empeora con cada número. Si contamos las llamadas que hace el método:

n	Resultado	Llamadas a fibonacci
10	55	177
20	6765	21 891
30	832 040	2 692 537
40	102 334 155	331 160 281

Por cada 10 que sube n, el trabajo se multiplica por más de 100. Es un crecimiento exponencial.

Solución 1: memoización

La idea es sencilla: apunta cada resultado la primera vez que lo calcules y, si te lo vuelven a pedir, devuelve el apunte. A esta técnica se le llama memoización:

static long[] memo = new long[100];   // memo[n] guarda fib(n); 0 = sin calcular

static long fibMemo(int n) {
    if (n <= 1) {
        return n;
    }
    if (memo[n] != 0) {
        return memo[n];                            // ya lo teníamos
    }
    memo[n] = fibMemo(n - 1) + fibMemo(n - 2);     // lo calculamos una vez
    return memo[n];
}

System.out.println(fibMemo(50)); // 12586269025
System.out.println(fibMemo(90)); // 2880067194370816120

Ahora cada valor se calcula una sola vez, y el resultado es instantáneo. El array memo se explica en la lección de arrays; en programas más grandes se suele usar un HashMap (mapas y conjuntos).

Solución 2: versión iterativa

En Fibonacci, basta con recordar los dos últimos números. Un bucle lo resuelve sin recursión, sin array y sin riesgo de desbordar la pila:

static long fibIterativo(int n) {
    if (n == 0) {
        return 0;
    }
    long anterior = 0;
    long actual = 1;
    for (int i = 2; i <= n; i++) {
        long siguiente = anterior + actual;
        anterior = actual;
        actual = siguiente;
    }
    return actual;
}

System.out.println(fibIterativo(10)); // 55
System.out.println(fibIterativo(50)); // 12586269025

La lección: una definición recursiva puede ser la forma más clara de entender un problema, pero no siempre la mejor forma de programarlo.

Más ejemplos clásicos

Potencia

base elevado a exp es base multiplicado por base elevado a exp - 1, y cualquier número elevado a 0 vale 1:

static long potencia(long base, int exp) {
    if (exp == 0) {
        return 1;
    }
    return base * potencia(base, exp - 1);
}

System.out.println(potencia(2, 10)); // 1024
System.out.println(potencia(3, 4));  // 81

Hay un truco para hacerlo mucho más rápido: 2^10 es 2^5 · 2^5. Si el exponente es par, calculas la mitad una vez y la multiplicas por sí misma; si es impar, además multiplicas por la base:

static long potenciaRapida(long base, int exp) {
    if (exp == 0) {
        return 1;
    }
    long mitad = potenciaRapida(base, exp / 2);
    if (exp % 2 == 0) {
        return mitad * mitad;
    }
    return mitad * mitad * base;
}

System.out.println(potenciaRapida(3, 5));  // 243
System.out.println(potenciaRapida(2, 62)); // 4611686018427387904

Para exp = 62, la primera versión hace 62 llamadas; esta, solo 7, porque el exponente se divide a la mitad en cada paso. En la práctica usarías Math.pow (Math y clases envoltorio), pero la idea de “partir el problema por la mitad” aparece en muchos algoritmos, como la búsqueda binaria.

Sumar los dígitos de un número

n % 10 da la última cifra y n / 10 quita esa cifra. La suma de los dígitos de 4721 es 1 más la suma de los dígitos de 472:

static int sumarDigitos(int n) {
    if (n < 10) {
        return n;                          // un solo dígito
    }
    return n % 10 + sumarDigitos(n / 10);
}

System.out.println(sumarDigitos(4721)); // 14
System.out.println(sumarDigitos(7));    // 7

Invertir una cadena

El texto invertido de "hola" es el invertido de "ola" seguido de la h:

static String invertir(String texto) {
    if (texto.length() <= 1) {
        return texto;
    }
    return invertir(texto.substring(1)) + texto.charAt(0);
}

System.out.println(invertir("hola"));      // aloh
System.out.println(invertir("DevSchool")); // loohcSveD

Este ejemplo sirve para practicar, pero no es eficiente: cada substring crea una cadena nueva. Para trabajo real, new StringBuilder(texto).reverse() hace lo mismo en una línea (lo tienes en String y StringBuilder).

Recursión frente a iteración

Todo lo que se hace con recursión se puede hacer con bucles, y al revés. Entonces, ¿cuándo usar cada uno?

	Recursión	Iteración (bucles)
Claridad	Muy clara si el problema es recursivo por naturaleza	Muy clara para recorridos lineales
Memoria	Un marco en la pila por cada llamada	Solo unas pocas variables
Límite	Puede lanzar StackOverflowError	No tiene ese límite
Velocidad	Algo más lenta (cada llamada tiene un coste)	Normalmente más rápida
Ejemplos ideales	Árboles, carpetas y subcarpetas, divide y vencerás, backtracking	Sumar, contar, buscar en listas

Una regla práctica:

• Si el problema es una secuencia (recorrer un array, sumar del 1 al 100, Fibonacci), usa un bucle (bucles).
• Si el problema tiene forma de árbol o se divide en varios subproblemas del mismo tipo (recorrer una carpeta con subcarpetas, ordenar con mergesort, resolver un laberinto), la recursión suele dar un código mucho más corto y fácil de entender.

Cómo pensar un método recursivo

1. Busca el caso más sencillo y su respuesta directa: número 0, texto de una letra.
2. Supón que el método ya funciona para un problema un poco más pequeño y usa ese resultado. No sigas mentalmente todas las llamadas.
3. Comprueba que cada llamada se acerca al caso base: n - 1, n / 10, un texto más corto.
4. Prueba primero con valores pequeños (0, 1, 2).

Errores frecuentes

• Olvidar el caso base: StackOverflowError seguro.
• Un caso base que nunca se alcanza: por ejemplo, if (n == 0) con una llamada factorial(n - 2) y un n impar. Usa condiciones como n <= 1 que cubran todos los casos.
• No acercarse al caso base: llamar con n en lugar de con n - 1.
• Olvidar el return en la llamada recursiva: escribir factorial(n - 1); sin usar el resultado no calcula nada.
• Recursión ingenua con subproblemas repetidos, como Fibonacci: usa memoización o un bucle.
• Usar recursión para recorrer secuencias enormes: un bucle es más seguro.

Resumen

Concepto	Qué es
Método recursivo	Método que se llama a sí mismo
Caso base	Condición que se resuelve sin volver a llamar; detiene la recursión
Caso recursivo	Llamada con un problema más pequeño cuyo resultado se usa
Pila de llamadas	Memoria donde se guarda un marco por cada llamada en curso
StackOverflowError	La pila se llena: recursión infinita o demasiado profunda
Memoización	Guardar resultados ya calculados para no repetir trabajo
Iteración	Resolver lo mismo con bucles; más eficiente en secuencias

Con los métodos dominados, el siguiente paso es guardar muchos datos del mismo tipo juntos: los arrays.

static void mostrar(int n) {
    if (n == 0) return;
    mostrar(n - 1);
    System.out.print(n + " ");
}

static int suma(int n) {
    return n + suma(n - 1);
}

static int misterio(int n) {
    if (n <= 0) return 0;
    return n + misterio(n - 2);
}