700 ms
Pila de llamadas, árbol recursivo y memoization paso a paso
Pila de llamadas, casos base y memoization
| Función | Caso base | Paso recursivo | Complejidad |
|---|---|---|---|
| Factorial(n) | n ≤ 1 → retorna 1 | n × factorial(n − 1) | O(n) tiempo, O(n) pila |
| Fibonacci(n) | n ≤ 1 → retorna n | fib(n − 1) + fib(n − 2) | O(2ⁿ) sin memo, O(n) con memo |
| Torres de Hanoi(n) | n = 1 → mover 1 disco | 2 × hanoi(n − 1) + 1 mov. | O(2ⁿ) movimientos, O(n) pila |
| MCD(a, b) | b = 0 → retorna a | mcd(b, a mod b) | O(log min(a, b)) |
| Suma de dígitos(n) | n < 10 → retorna n | (n mod 10) + suma(n div 10) | O(log₁₀ n) |
| Búsqueda binaria(arr, x) | rango vacío → −1; medio = x → índice | buscar en mitad correspondiente | O(log n) tiempo y pila |
Sistemas de archivos, árboles DOM, JSON anidados o árboles de decisión: la recursión es natural porque la propia estructura es recursiva.
Mergesort, quicksort, búsqueda binaria, FFT: dividen el problema en mitades y combinan los resultados. Modelo recursivo limpio y eficiente.
Sudoku, N reinas, generación de permutaciones, laberintos: prueba una opción, recurre, y si no funciona deshaz y prueba la siguiente.
Mochila, cambio de monedas, distancia de edición: empieza con recursión + memo (top down) y luego optimiza a iterativa (bottom up).
El caso base es la condición que detiene la recursión: cuando se cumple, la función retorna sin volver a llamarse. Sin caso base la función se llama infinitamente y acaba con un error de pila.
Regla de oro: el caso base debe alcanzarse desde cualquier entrada válida.
Cada llamada hace 2 llamadas más (fib(n − 1) y fib(n − 2)), y muchas se repiten. fib(40) realiza más de 200 millones de llamadas. Con memoization caché esos resultados y bajas a O(n).
Activa el toggle "Memoization" en el simulador y compara las cifras: la diferencia es brutal.
La iteración usa bucles (while/for) y no consume pila adicional. La recursión es más expresiva en problemas que se definen sobre sí mismos (árboles, divide y vencerás) pero gasta memoria de pila. Cualquier recursión se puede transformar a iteración con una pila explícita.
Cuando hay subproblemas que se repiten con los mismos argumentos. Si cada llamada usa argumentos distintos (caso del factorial), la memoization no aporta nada. En Fibonacci, mochila, distancia de edición → muy útil.
Cada llamada ocupa un frame en la pila de ejecución. Si la profundidad supera el límite del runtime (~10 000-20 000 frames en JavaScript), el motor lanza "Maximum call stack size exceeded". Causa típica: recursión sin caso base o entrada muy grande.
La especificación ES2015 incluye Tail Call Optimization (TCO), pero en la práctica solo Safari la implementa. V8 (Chrome, Node) y Firefox no la activan. Por eso, en JavaScript es prudente convertir recursiones profundas a iteración.
En Python pasa igual: no hay TCO. En Scheme o Haskell sí, y son recursivos por diseño.
¿Cuál es la entrada más simple posible? ¿Qué resultado retorna sin necesidad de recurrir? Sin esto, la función no termina.
Asume que la función ya funciona para una entrada más pequeña. ¿Cómo combinas ese resultado con la entrada actual? Ese es el paso recursivo.
Cada llamada debe acercarse al caso base (n disminuye, rango se reduce…). Si no, stack overflow garantizado.
Pinta el árbol de llamadas para una entrada pequeña. ¿Coincide con lo esperado? Si no, revisa caso base y paso recursivo.
Si el árbol contiene nodos con los mismos argumentos, aplica memoization (cache). Mejora drásticamente la complejidad.
Antes de pensar en el paso recursivo, escribe la condición de parada y su retorno. Evita stack overflow desde el primer día.
Cada llamada debe trabajar con un argumento estrictamente más simple. Si pasas el mismo argumento, recursión infinita.
No intentes desarrollar mentalmente toda la pila. Asume que la llamada recursiva funciona correctamente para entradas más pequeñas y usa ese resultado.
Si dibujas el árbol y ves los mismos argumentos en distintos nodos, cachea resultados. Pasas de exponencial a polinómico.
Recursiones con miles de frames son arriesgadas en JavaScript. Una pila explícita + bucle while elimina el riesgo.
Antes de ejecutar, plantea la ecuación de recurrencia: T(n) = ... Aplica el teorema maestro o expansión de árbol para estimar el coste.