Cuando un metodo se llama dos veces, la pila deja de ser una linea.
Con dos llamadas por nivel la pila sigue siendo una linea, pero el trabajo total se vuelve un arbol.
Es la diferencia entre bajar una escalera y repartir un chisme. Bajar 20 escalones son 20 pasos. Pero si cada persona le cuenta el chisme a dos, en 20 rondas ya se entero un millon de gente. La pila mide escalones; el arbol mide chisme.
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);
}
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.
// "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.
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.