Y la verdad incomoda: Java no optimiza la recursion de cola.
Si tu recursion resuelve dos veces el mismo subproblema, guarda el resultado. Y ten claro que Java no optimiza la recursion de cola.
Un cajero que atiende la misma pregunta cincuenta veces al dia termina pegando la respuesta en un papel al lado del mostrador. Eso es memoizacion: no se vuelve mas inteligente, simplemente deja de repetir trabajo que ya hizo.
Si tu recursion resuelve el mismo subproblema mas de una vez, guarda el resultado la primera vez y devuelvelo desde ahi. Eso es todo. Se llama memoizacion, y convierte a Fibonacci de exponencial a lineal con tres lineas.
static Map<Integer, Long> memo = new HashMap<>();
static long fib(int n) {
if (n <= 1) return n;
if (memo.containsKey(n)) return memo.get(n); // ya lo calcule
long r = fib(n - 1) + fib(n - 2);
memo.put(n, r); // lo guardo
return r;
}
Esto es programacion dinamica top-down. La version bottom-up con un arreglo y un bucle hace lo mismo sin usar la pila.
Una llamada es de cola cuando es lo ultimo que hace el metodo, sin ninguna operacion pendiente despues. En return n * fact(n-1) queda pendiente la multiplicacion, asi que NO es de cola. En return fact(n-1, acc*n) no queda nada pendiente: si lo es.
En Scala, Kotlin o Scheme el compilador convierte eso en un bucle y el consumo de pila se vuelve constante.
// NO es de cola: falta multiplicar al volver
static long fact(int n) {
return n <= 1 ? 1 : n * fact(n - 1);
}
// SI es de cola: el acumulador lleva el resultado
static long fact(int n, long acc) {
return n <= 1 ? acc : fact(n - 1, acc * n);
}
Esto hay que decirlo claro porque muchos libros lo dan por hecho: la JVM no elimina las llamadas de cola. El segundo metodo del ejemplo tambien revienta la pila, exactamente igual que el primero.
La razon es historica y de diseno: Java necesita la pila completa para los rastros de excepcion y para el modelo de seguridad basado en el llamador. Escribir recursion de cola en Java es un buen habito de estilo y de portabilidad a otros lenguajes, pero no te salva del StackOverflowError.
Si necesitas profundidad grande de verdad, no hay atajo: pasas a iteracion.
Toda recursion se puede convertir en un bucle. Si es recursion simple, casi siempre sale un for directo. Si es multiple, tienes que llevar tu propia pila con un Deque, que es exactamente lo que hacia la JVM por ti.
// Recorrido preorden sin recursion
static void preorden(Nodo raiz) {
if (raiz == null) return;
Deque<Nodo> pila = new ArrayDeque<>();
pila.push(raiz);
while (!pila.isEmpty()) {
Nodo n = pila.pop();
visitar(n);
if (n.der != null) pila.push(n.der); // derecha primero
if (n.izq != null) pila.push(n.izq); // para que salga izquierda
}
}
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.
La pila te muestra cuanta memoria usa la recursion en un instante. El arbol te muestra cuanto trabajo hace en total, que es una cosa muy distinta y mucho mas cara.
Sube n de a uno y mira el contador. Cuando llegues a 10, marca la casilla de memoizacion.
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.
static long suma(int n, long acc) {
if (n == 0) return acc;
return suma(n - 1, acc + n); // es de cola...
}
// suma(1_000_000, 0) -> StackOverflowError
La JVM no elimina llamadas de cola. Este metodo apila un millon de marcos igual que cualquier otro.
static long suma(int n) {
long acc = 0;
for (int i = n; i > 0; i--) acc += i;
return acc;
}
// funcion de dos parametros, memo de uno solo
static Map<Integer, Integer> memo = new HashMap<>();
static int f(int i, int j) {
if (memo.containsKey(i)) return memo.get(i);
...
}
La llave debe identificar el subproblema completo. Con dos parametros que varian, la llave tiene que incluir los dos.
static Map<String, Integer> memo = new HashMap<>(); // llave: i + "," + j o mejor: int[][] memo = new int[n][m];
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.