Java 55: Recursion & the Call Stack
easy⏱ 5 mincoursejava
Caso base + caso recursivo
Toda recursión necesita un caso base que retorna sin recursar, y un caso recursivo que avanza hacia el base. factorial(0) = 1 es el base; factorial(n) = n * factorial(n-1) es el recursivo. Olvida o nunca alcances el caso base y recursas para siempre → StackOverflowError. El n y el resultado parcial de cada llamada viven en el frame de esa llamada.
int factorial(int n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case — frame waits for the result
}
// factorial(4): frames stack up 4,3,2,1 then unwind 1->2->6->24
La pila crece, luego se desenrolla
factorial(4) apila frames para 4, 3, 2, 1. Cada frame está pausado a mitad de la expresión n * factorial(n-1), esperando la llamada interna. Cuando factorial(1) llega al caso base y devuelve 1, los frames se desenrollan: 2 calcula 2*1=2, 3 calcula 3*2=6, 4 calcula 4*6=24. Las multiplicaciones diferidas ocurren al bajar por la pila — ese trabajo pendiente es por qué esto no es tail-recursivo.
Forma tail y por qué la JVM no la optimiza
Una versión tail-recursiva lleva el resultado en un acumulador, así nada queda pendiente tras la llamada recursiva: fact(n, acc) = fact(n-1, n*acc). Muchos lenguajes la convierten en un bucle (sin crecer la pila). La JVM no hace optimización de tail-call (los frames se necesitan para stack traces / seguridad), así que la recursión profunda aún arriesga overflow — convierte la recursión caliente en un bucle explícito o una pila basada en Deque.
Traza la pila de llamadas
Escribe factorial(n, depth, trace) que registre enter n antes de recursar y exit n=resultado después, construyendo una traza del orden push/pop. Ejecuta factorial(5) e imprime: el resultado 120, la profundidad máxima alcanzada (5) y la traza completa enter/exit. Luego escribe la factTail(n, acc) tail-recursiva y confirma que devuelve el mismo 120 manteniendo la profundidad plana en 1 frame pendiente lógico.
Profundidad de pila por defecto ≈ unos miles de frames
La pila de hilo por defecto de HotSpot (-Xss, ~512KB–1MB) aguanta unos miles de frames antes del StackOverflowError. Bien para profundidad de árbol o divide-y-vencerás; peligroso para recursión lineal sobre una lista grande. Cuando la profundidad de recursión sigue el tamaño de la entrada, prefiere iteración o una worklist ArrayDeque explícita.
Quiz: ¿la JVM optimiza las tail calls?
¿factTail(100000, 1) (tail-recursiva) evita el StackOverflowError en la JVM? No — la JVM no hace optimización de tail-call, así que incluso el código tail-recursivo crece la pila un frame por llamada. Para manejar entrada profunda, reescribe como un bucle explícito.