La pila de llamadas y la recursión en Python

Problema

El catálogo que tumba la página

El menú de una tienda en línea es un árbol: categorías, subcategorías dentro de ellas, unos cuantos productos en cada una. Junto al nombre dice cuántos productos hay, subcategorías incluidas: «Electrónica (10)». Un función recursivo los cuenta, como en la lección «Recursión»:

def count_products(category):
    total = category.products
    for child in category.children:
        total += count_products(child)
    return total


phones = Category("Teléfonos", 5)
laptops = Category("Portátiles", 3)
electronics = Category("Electrónica", 2).add(phones, laptops)
kitchen = Category("Cocina", 6)
home = Category("Hogar", 4).add(kitchen)
shop = Category("Tienda", 0).add(electronics, home)
print("Productos: " + str(count_products(shop)))

Productos: 20

Funciona durante meses. Entonces llegan dos importaciones nuevas de proveedores. La primera pone cada categoría nueva dentro de la anterior: la cadena tiene 100 000 niveles de profundidad. La segunda, por error, pone «Hogar» dentro de su propia subcategoría «Cocina». En los dos casos la página falla con RecursionError: maximum recursion depth exceeded.

El código es el mismo, y es correcto. ¿Qué se agotó?

La idea

Lo que cuesta una llamada

Cada llamada recibe su propia memoria en la pila. Se llama marco (stack frame) y guarda tres cosas:

los parámetros: aquí category, la categoría que cuenta esta llamada;
las variables locales: total y child, hasta dónde ha llegado el bucle;
el punto de retorno: qué línea del que llama continúa cuando esta llamada termina.

El marco vive hasta que la llamada vuelve. Entonces se tira y su lugar se reutiliza. El número de marcos vivos a la vez es la profundidad de la recursión. No es el número de llamadas: el recorrido llama a count_products 6 veces, pero hay como máximo 3 marcos a la vez.

En la lección de recursión ya viste la pila de marcos del factorial. Cada llamada tiene su propio n y espera la respuesta de la que está encima:

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


print(factorial(3))  # 6

Paso a paso, en palabras

El programa llama a factorial(3).
Memoria nueva para factorial con n = 3.
3 no es 1, así que la función llama a factorial(2) y espera la respuesta.
Lo mismo otra vez: factorial(2) llama a factorial(1). Cada llamada tiene su propio n.
n es 1: este es el caso base. Devuelve 1 sin volver a llamar.
La respuesta baja: 2 * 1 = 2.
Y otra vez: 3 * 2 = 6.
factorial(3) devuelve 6 y el programa lo imprime.

Míralo

Los marcos del recorrido

Ahora lo mismo con el árbol de la tienda. Mira las ranuras de cada marco y la línea en la que espera el marco de abajo:

def count_products(category):
    total = category.products
    for child in category.children:
        total += count_products(child)
    return total

print("Productos: " + str(count_products(shop)))

Paso a paso, en palabras

El programa llama a count_products(shop). Por ahora en la pila solo está el marco del programa.
Un marco nuevo: el parámetro category = Tienda, la local total = 0 y el punto de retorno, a dónde volver cuando termine.
El bucle llega a child = Electrónica y se llama a sí mismo. El marco de Tienda se detiene en la línea 4 y espera; el marco nuevo recuerda esa línea.
Teléfonos no tiene subcategorías: el bucle no se ejecuta. Es el caso base. Hay 3 marcos del recorrido vivos a la vez: la profundidad es 3.
return 5: el marco se tira. Electrónica continúa desde la línea 4: total = 2 + 5 = 7.
Portátiles ocupa el mismo lugar en la pila y devuelve 3. total = 7 + 3 = 10.
Electrónica devuelve 10. El marco de Tienda despierta donde se detuvo: total = 10.
El siguiente hijo: Hogar, luego Cocina. Otra vez 3 marcos, en los mismos lugares.
Cocina devuelve 6, Hogar devuelve 4 + 6 = 10, y Tienda llega a 10 + 10 = 20.
20 productos. 6 llamadas, pero nunca más de 3 marcos del recorrido a la vez: la pila crece con la profundidad del árbol, no con el número de categorías.

Cuando «Teléfonos» vuelve, su marco desaparece, y «Portátiles» ocupa el mismo lugar. La memoria del recorrido crece con el camino más largo del árbol, no con el número de categorías. Para una cadena de 100 000 categorías el camino más largo es 100 000.

Pruébalo

¿Cuántos marcos a la vez?

Aquí count_products cuenta cuántos de sus marcos están vivos (depth) y recuerda el valor mayor (deepest). El árbol es el mismo: Tienda, Electrónica con Teléfonos y Portátiles, Hogar con Cocina.

depth = 0
deepest = 0


def count_products(category):
    global depth, deepest
    depth += 1
    deepest = max(deepest, depth)
    total = category.products
    for child in category.children:
        total += count_products(child)
    depth -= 1
    return total


total = count_products(shop)
print(f"{total} productos, como máximo {deepest} marcos a la vez")

Respuesta

20 productos, como máximo 2 marcos a la vez

20 productos, como máximo 6 marcos a la vez

20 productos, como máximo 3 marcos a la vez

La idea

Por qué se agota la pila

La pila es un bloque de memoria aparte para cada hilo, y no crece sola: en Java, C# y Node es del orden de 1 MB, y Python cuenta marcos y se detiene en 1000. Un marco es pequeño, de decenas a cien bytes, pero la cadena de la importación necesita 100 000 marcos a la vez. chain(n) construye una cadena así: n categorías, cada una dentro de la anterior, un producto cada una.

print("El límite de Python:", sys.getrecursionlimit())
print(f"Profundidad 900: {count_products(chain(900))} productos")
try:
    print(f"Profundidad 100000: {count_products(chain(100_000))} productos")
except RecursionError as e:
    print(f"Profundidad 100000: RecursionError: {e}")

El límite de Python: 1000
Profundidad 900: 900 productos
Profundidad 100000: RecursionError: maximum recursion depth exceeded

Python se detiene ya a los 1000 marcos, mucho antes de que se agote la pila real. Es una protección, no el fin de la memoria: pasan 900 niveles, 1000 no.

La memoria que necesita el recorrido es O(profundidad), como en la lección «Complejidad en espacio». En un árbol equilibrado la profundidad es pequeña. En una cadena es n.

Míralo

El error cae por cada marco

El desbordamiento ocurre en el marco de arriba del todo, 100 000 niveles más arriba. Desde ahí el error cae como cualquier excepción: un marco sin catch se tira y el error sigue bajando. Así cayó la excepción al retirar dinero por los marcos en la lección «Lanzar excepciones y crear las tuyas»:

def withdraw(self, amount):
    if amount > self.balance:
        raise ValueError("No alcanza el dinero")
    self.balance -= amount


def pay_rent(account):
    account.withdraw(800)
    print("El alquiler está pagado.")


try:
    pay_rent(Account(500))
except ValueError as e:
    print(f"Rechazado: {e}")

Paso a paso, en palabras

El programa llama a pay_rent para una cuenta con 500 €.
pay_rent llama a withdraw(800): un marco nuevo encima.
800 > 500: el método lanza una excepción con raise.
El saldo no cambia: el marco se descarta sin terminar sus líneas.
pay_rent no tiene except: «El alquiler está pagado.» no se imprime, el marco se descarta.
except en el programa atrapa la excepción y este sigue desde aquí.

Cuando el error llega a catch, los 100 000 marcos ya no están y la pila vuelve a estar vacía. Por eso el programa de arriba sigue y escribe.

La idea

El ciclo: el caso base nunca llega

¿Dónde está el caso base de count_products? No hay ningún if. El caso base es una categoría sin subcategorías: el bucle no se ejecuta ni una vez, y el la función devuelve sus propios productos.

La segunda importación puso «Hogar» dentro de su propia «Cocina». Ahora el camino Tienda → Hogar → Cocina → Hogar → Cocina → … no tiene fin. Toda categoría en él tiene una subcategoría, así que el caso base nunca llega:

kitchen.add(home)
try:
    print("Productos: " + str(count_products(shop)))
except RecursionError as e:
    print(f"Con el ciclo: RecursionError: {e}")

Con el ciclo: RecursionError: maximum recursion depth exceeded

Esto es un caso base que nunca se alcanza. Está en el código, pero la entrada nunca lleva a él. El árbol viene de fuera (una importación, una API, una base de datos), así que el recorrido tiene que sobrevivir tanto a un árbol profundo como a uno circular. Cómo, está en la siguiente lección, «De la recursión al bucle».

La idea

Dos casos base

A veces hay más de un motivo para parar. find busca una categoría por nombre y tiene dos casos base:

encontrada: el nombre coincide, y el la función devuelve la categoría sin seguir bajando;
más abajo no hay nada: ninguna subcategoría la contiene, y el la función devuelve None.

def find(category, name):
    if category.name == name:
        return category
    for child in category.children:
        found = find(child, name)
        if found is not None:
            return found
    return None


for name in ["Cocina", "Jardín"]:
    found = find(shop, name)
    if found is None:
        print(name + ": no existe esa categoría")
    else:
        print(f"{name}: {found.products} productos")

Cocina: 6 productos
Jardín: no existe esa categoría

En cuanto un hijo encuentra la categoría, la respuesta sube directamente por todos los marcos, sin recorrer a los demás hijos.

Pruébalo

Completa

¿Qué devuelve find cuando la categoría no está en ninguno de los subárboles?

def find(category, name):
    if category.name == name:
        return category
    for child in category.children:
        found = find(child, name)
        if found is not None:
            return found
    return

Pruébalo

Encuentra el error

La tienda vende a plazos. months(150, 50) devuelve 3 meses. months(130, 50) también debería devolver 3 (50 €, 50 € y 30 €), pero se detiene con RecursionError. ¿Qué línea está mal?

Elige la línea con el error.

Ejercicio

El camino de migas

Resuélvelo en tu editor.

El camino hasta la categoría. Sobre los productos la tienda muestra el camino hasta la categoría: «Tienda > Hogar > Cocina». Escribe un función recursivo path(category, name) que devuelva la lista de nombres desde la raíz hasta la categoría que buscas, o None si no está. Los dos casos base son como en find. Lee el nombre e imprime el camino.

Cocina

Tienda > Hogar > Cocina

Con la entrada Jardín la salida es No existe esa categoría.

Más tareas

La categoría más profunda. Escribe un depth(category) recursivo: una categoría sin hijos tiene profundidad 1; si no, es 1 + el hijo más profundo. Para el árbol de la lección es 3, para la cadena de la importación es 100 000.
Los plazos. Corrige months y ejecútalo con 130 y 50, y luego con 0 y 50. ¿Cuántos marcos abre cada llamada?

Más precisamente

Qué tan grande es la pila

La pila no es infinita, y no es igual en todas partes. Los números de abajo son valores por defecto, y se pueden cambiar.

Más precisamente, para curiosos

El tamaño. En Python el límite es un número de marcos: sys.getrecursionlimit() es 1000. sys.setrecursionlimit(100_000) sube el límite, pero no la pila real del proceso: con una recursión lo bastante profunda Python se cae sin mensaje. Para tener de verdad más espacio hace falta un hilo con una pila mayor (threading.stack_size), e incluso entonces la cadena de la importación puede ser más profunda.

El tamaño de un marco. Cuántos marcos caben depende del marco: más parámetros y variables locales son más bytes. Por eso en Node el número de llamadas antes del desbordamiento no es un número exacto, mientras que en Python sí, porque Python cuenta marcos.

El árbol y la memoria de objetos. Las propias categorías no están en la pila. Son objetos en la memoria de objetos (el heap), y un marco guarda solo una referencia a uno de ellos. Por eso 100 000 categorías caben en la memoria sin problema, mientras que 100 000 marcos a la vez no.

Volver. El punto de retorno es la dirección de la instrucción donde continúa quien llama. En el procesador es literalmente una dirección de memoria, escrita en el marco. La escena la muestra como un número de línea.

Test

Ponte a prueba

1. ¿Qué guarda el marco de la llamada para la categoría «Hogar»?Solo el resultado que va a devolverTodo el árbol de categoríasEl parámetro category, las variables locales total y child, y el lugar donde continúa el marco de abajo

2. El catálogo tiene 1000 categorías, y el camino más largo desde «Tienda» hasta la más profunda es de 4 categorías. ¿Cuántos marcos del recorrido existen a la vez, como máximo?4101000

3. «Hogar» se puso por error dentro de su propia «Cocina». ¿Por qué el recorrido desborda la pila en lugar de dar una suma incorrecta?En el camino alrededor del ciclo toda categoría tiene una subcategoría, así que el caso base (una categoría sin hijos) nunca llegaLa suma se hace mayor que intEl árbol se hace demasiado ancho

4. months(130, 50) debería devolver 3, pero desborda la pila. ¿Por qué?La deuda va 80, 30, −20, −70… y nunca es exactamente 0payment no se hace más pequeñoLa recursión es demasiado profunda para 130

El caso base es debt == 0, y 130 no es múltiplo de 50. La deuda salta sobre cero y sigue bajando. Un caso base como debt <= 0 también atrapa el salto.

5. ¿Qué mide el límite de Python, y qué mide el límite de la pila en Java, C# y JavaScript?Los dos cuentan marcosPython cuenta marcos (1000), los otros miden bytes de memoria, así que el número de llamadas depende del tamaño de un marcoLos dos miden bytes

La pila de llamadas por dentro

Cookies