Recursividad en Java
Nivel 5 · 50 min · 4 preguntas

Backtracking

Elegir, explorar, deshacer.

La idea en una frase

Elegir, explorar y, si no funciono, deshacer. La tercera parte es la que todo el mundo olvida.

Antes de ver codigo

Es como recorrer un laberinto con un ovillo de lana. En cada bifurcacion tomas un camino y sueltas hilo. Si llegas a un muro, te devuelves recogiendo el hilo hasta la ultima bifurcacion y tomas otra salida. Recoger el hilo es el "deshacer": si no lo recoges, terminas con el laberinto lleno de lana y sin saber por donde ya pasaste.

Probar caminos y devolverse

Backtracking es recursion con arrepentimiento. Tomas una decision, exploras a fondo lo que se abre a partir de ella, y si no funciona deshaces la decision y pruebas la siguiente.

Ese "deshacer" es la linea que todo el mundo olvida, y es la que hace que el algoritmo sea correcto.

static void explorar(Estado e) {
    if (esSolucion(e)) { registrar(e); return; }

    for (Opcion op : opciones(e)) {
        if (!esValida(op, e)) continue;

        aplicar(op, e);        // 1. ELEGIR
        explorar(e);           // 2. EXPLORAR
        deshacer(op, e);       // 3. DESHACER
    }
}

Este esqueleto resuelve N-reinas, sudoku, laberintos, permutaciones y subconjuntos. Cambia lo que pones en cada hueco.

La poda

Sin esValida() el algoritmo probaria todas las combinaciones posibles. Con esa comprobacion cortas ramas enteras antes de bajar por ellas. En N-reinas con n=8, la poda reduce el espacio de busqueda de 16 millones de posiciones a unas 15.000 exploraciones.

Podar temprano vale mas que optimizar el codigo de adentro.

Deshacer, o no deshacer

Si tu estado es mutable (un arreglo, una lista, un tablero), tienes que deshacer. Si en cada llamada creas un objeto nuevo, no hace falta, pero pagas en memoria. Java tiende a lo primero por eficiencia, y por eso el bug clasico de backtracking es una lista que sale llena de basura de otras ramas.

Ejecuta y observa

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.

Errores que vas a cometer

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.

Olvidar el deshacer

static void subconjuntos(int[] a, int i, List<Integer> actual) {
    if (i == a.length) { System.out.println(actual); return; }
    subconjuntos(a, i + 1, actual);
    actual.add(a[i]);
    subconjuntos(a, i + 1, actual);
    // falta: actual.remove(actual.size() - 1);
}

Guardar la referencia en vez de una copia

if (esSolucion()) {
    resultados.add(actual);   // guarda la MISMA lista
}

Comprueba lo que entendiste

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.