Cuando un metodo se llama dos veces, la pila deja de ser una linea.
Hasta ahora cada metodo hacia una sola llamada recursiva: la pila crecia como una linea recta. Cuando hay dos o mas llamadas, la ejecucion se ramifica y forma un arbol de llamadas.
La pila sigue siendo una linea (solo un camino se ejecuta a la vez), pero el trabajo total ya no es proporcional a n. Puede ser exponencial.
static int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
fib(5) hace 15 llamadas. fib(30) hace 2.692.537. fib(50) haria aproximadamente 40.730.022.147, que en una maquina normal son horas.
El problema no es la recursion: es que el arbol recalcula lo mismo una y otra vez. fib(3) se calcula 3 veces dentro de fib(6). Ese desperdicio se arregla en el nivel 7.
El ejemplo clasico de recursion multiple con dos llamadas y trabajo en el medio. Mover n discos de A a C es: mover n-1 discos de A a B, mover el disco grande de A a C, y mover n-1 discos de B a C. La solucion tiene 2^n - 1 movimientos y no existe una mas corta.
static void hanoi(int n, char origen, char aux, char destino) {
if (n == 0) return;
hanoi(n - 1, origen, destino, aux);
System.out.println("Mover disco " + n + ": " + origen + " -> " + destino);
hanoi(n - 1, aux, origen, destino);
}
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.
// "fib(40) tarda el doble que fib(20)"
Cuesta unas 20.000 veces mas. El crecimiento es exponencial, no lineal. fib(n) hace aproximadamente 2^n llamadas.
// Cuenta las llamadas antes de opinar sobre el costo. // Usa el visor de arbol de esta pagina con n = 6, 8 y 10.
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.