Y la verdad incomoda: Java no optimiza la recursion de cola.
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
}
}
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.
Sube n de a uno y mira como crece el arbol. Cuando llegues a 10, activa la memoizacion y compara el contador de llamadas.
Lee el codigo, decide que esta mal, y despues abre la correccion.
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];
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.