Qué guarda la pila de llamadas

Cuando una función llama a otra, la primera no desaparece: queda pausada a mitad de una línea, esperando un resultado. El programa tiene que recordar sus variables y el punto exacto donde retomar. Esa memoria ordenada de trabajo pendiente es la pila de llamadas, y entenderla explica tres cosas que parecen distintas: cómo funciona la recursión, cómo se lee un stack trace y por qué un programa correcto puede morir con una entrada grande.

Qué hay en un marco

Cada invocación crea un marco (stack frame). Conceptualmente guarda tres cosas: los parámetros, las variables locales y la dirección de retorno, que es el lugar del código que llamó y donde hay que seguir cuando esta función termine.

El marco nuevo se apila arriba. Cuando la función termina, su marco sale primero. Es una estructura LIFO: el último en entrar es el primero en salir.

Este es el programa que vamos a seguir durante todo el post:

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(4))

Así se ve la pila en el momento de mayor profundidad, cuando factorial(1) está por devolver:

La pila, llamada por llamada

Seguir la pila paso a paso es la forma más segura de predecir qué hace un programa recursivo. Antes de ejecutarlo, una pregunta:

Ahora comprobalo. Avanzá de a un paso con las flechas: a la izquierda se marca la línea que se ejecuta y en gris las líneas donde quedaron pausados los marcos de abajo; a la derecha, cada marco con su n. Cambiá n para ver cómo crece la pila.

Profundidad y espacio

Lo que ocupa memoria no es la cantidad total de llamadas, sino cuántos marcos conviven al mismo tiempo. Esa cantidad máxima se llama profundidad de recursión:

La diferencia entre “llamadas totales” y “profundidad” es la que más se confunde. Mirá Fibonacci en su versión ingenua:

def fibonacci(n):
    return n if n <= 1 else fibonacci(n - 1) + fibonacci(n - 2)

fibonacci(5) hace 15 llamadas en total, y ese número crece como $O(2^n)$. Pero la segunda rama recién empieza cuando la primera ya terminó y sacó sus marcos de la pila.

Cuando no entra otro marco

La pila tiene un tamaño fijo. Si la recursión no termina, o termina pero demasiado profunda, llega un momento en que no entra otro marco y el programa aborta: es el desbordamiento de pila (stack overflow). Python se ataja antes con su propio límite de profundidad y lanza RecursionError.

La causa más común no es una entrada gigante, sino un caso base que nunca se alcanza:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

factorial(-1)

El otro caso es la recursión correcta pero profunda: recorrer recursivamente una lista enlazada de cien mil nodos necesita cien mil marcos, y CPython corta en mil por defecto. Si la profundidad depende de datos que no controlás, conviene una versión iterativa.

Leer un stack trace

Un stack trace es una foto de la pila en el momento del error. Esto es lo que imprime Python con el factorial(-1) de arriba, simplificado:

Traceback (most recent call last):
  File "factorial.py", line 6, in <module>
    factorial(-1)
  File "factorial.py", line 4, in factorial
    return n * factorial(n - 1)
  File "factorial.py", line 4, in factorial
    return n * factorial(n - 1)
  File "factorial.py", line 4, in factorial
    return n * factorial(n - 1)
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Most recent call last: Python lo imprime con la llamada más reciente abajo. Arriba está <module>, la base de la pila; cada bloque siguiente es un marco más arriba, y justo antes del mensaje de error está el marco donde se rompió. Java y Node lo imprimen al revés, con el más reciente primero. En un error normal, buscá el último marco que apunte a tu código, no a una librería.

La pila en sistemas reales

Cada lenguaje decide cuánta pila hay y qué pasa al pasarse. Los números son órdenes de magnitud, porque dependen de la plataforma y de cuánto ocupa cada marco:

Cierre