De la recursión a la iteración en Python: recursión de cola

Problema

El árbol viene de fuera

En la lección «La pila de llamadas por dentro» el recorrido del catálogo falló en dos sitios: la cadena de la importación tenía 100 000 niveles de profundidad, y otra importación cerró un ciclo. Una pila grande no es una solución. sys.setrecursionlimit solo traslada el límite: la siguiente importación puede ser más profunda, y la pila real del proceso se agota sin mensaje.

El árbol viene de fuera: de un proveedor, de una API, de una base de datos. No puedes prometer lo profundo que es. Necesitas un recorrido cuya memoria no dependa de la pila de llamadas.

La idea

Recursión de cola

Empieza con una tarea más sencilla. Sobre un producto la tienda muestra el nivel de su categoría. El nivel se cuenta subiendo por los padres hasta llegar a la raíz:

def level_of(category, level):
    if category.parent is None:
        return level
    return level_of(category.parent, level + 1)

Aquí la llamada recursiva es lo último que hace el la función: su resultado se devuelve directamente, sin + 1 y sin bucle después. Una llamada así es una llamada de cola (tail call), y la recursión es recursión de cola. Después el marco no tiene nada más que recordar. Un lenguaje que lo sepa puede reutilizar el marco en lugar de añadir uno nuevo: la pila no crece.

Pero:

Java no lo hace. La JVM conserva cada marco.
El compilador de C# no lo hace. El compilador JIT a veces lo hace en código optimizado, pero no está prometido: en nuestra prueba con .NET 10 en Release la pila aun así se desbordó.
Python no lo hace a propósito: Guido van Rossum está en contra, porque el traceback perdería marcos.
JavaScript debe hacerlo según el estándar (ES2015, en modo estricto). En la práctica solo lo hace Safari. V8 (Chrome, Node) y Firefox no.

Por eso la recursión de cola falla también con la cadena de la importación:

last = chain(100_000)
while last.children:
    last = last.children[0]
try:
    print("Recursión: nivel " + str(level_of(last, 0)))
except RecursionError as e:
    print(f"Recursión: RecursionError: {e}")
print("Bucle: nivel " + str(level_of_loop(last)))

Recursión: RecursionError: maximum recursion depth exceeded
Bucle: nivel 99999

La idea

La llamada de cola se convierte en while

La recursión de cola se convierte en un bucle de forma mecánica, con tres reglas:

los parámetros pasan a ser variables: category y level;
la llamada pasa a ser una asignación: en lugar de llamarte con los valores nuevos, los pones en las variables y empiezas de nuevo;
el caso base pasa a ser la condición final del bucle: «sin padre» detiene el while.

def level_of_loop(category):
    level = 0
    while category.parent is not None:
        category = category.parent
        level += 1
    return level

Esta es la línea de abajo de la salida de arriba: el bucle llega al nivel 99 999 con un marco. La recursión y el bucle dan el mismo número de pasos, uno por nivel. La única diferencia es dónde está la memoria.

La idea

El recorrido no es una llamada de cola

count_products de la lección anterior no es recursión de cola. Después de cada llamada hay trabajo: total += y el siguiente hijo del bucle. Por eso hacen falta los marcos. ¿Qué guardaban en realidad? Las categorías a las que aún no ha llegado.

Eso lo puede guardar un bucle por sí mismo, en su propia pila: una lista de las categorías que aún faltan. Tomas la de arriba, sumas sus productos y pones sus hijos encima. La suma es una variable, porque sumar no depende del orden.

def count_products(root):
    total = 0
    stack = [root]
    while stack:
        category = stack.pop()
        total += category.products
        stack.extend(category.children)
    return total


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

Productos: 20

Una lista es una pila: append y extend ponen al final, pop() toma del final. Cómo funcionan por dentro está en la lección «Pila, cola y lista enlazada».

Míralo

Tu propia pila, paso a paso

def count_products(root):
    total = 0
    stack = [root]
    while stack:
        category = stack.pop()
        total += category.products
        stack.extend(category.children)
    return total

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

Paso a paso, en palabras

La pila es una lista en la memoria de objetos (el heap), no la pila de llamadas. Primero entra la raíz.
pop toma el de arriba: Tienda. Sus hijos entran encima: Electrónica, luego Hogar.
Sigue Hogar, no Electrónica: una pila devuelve lo último que entró. total = 4, y entra Cocina.
Cocina no tiene hijos: no entra nada. total = 10.
Solo ahora Electrónica: total = 12. Entran Teléfonos y Portátiles.
Portátiles (15), luego Teléfonos (20).
La pila está vacía: el bucle se detiene y devuelve 20. En ella nunca hubo más de 2 categorías. El orden, sin embargo, es Tienda, Hogar, Cocina, Electrónica, Portátiles, Teléfonos: no el de la recursión.

Tu pila propia es un objeto corriente en la memoria de objetos (el heap). Crece según haga falta y está limitada por toda la memoria, no por 1 MB. Y los números del árbol muestran que el orden es distinto.

Pruébalo

Predice el orden

El mismo recorrido, pero imprime el nombre de cada categoría en cuanto la toma de la pila:

def print_order(root):
    stack = [root]
    while stack:
        category = stack.pop()
        print(category.name)
        stack.extend(category.children)


print_order(shop)

Respuesta

Tienda
Electrónica
Hogar
Teléfonos
Portátiles
Cocina

Tienda
Hogar
Cocina
Electrónica
Portátiles
Teléfonos

Tienda
Electrónica
Teléfonos
Portátiles
Hogar
Cocina

La idea

El orden de la recursión: los hijos al revés

Para la suma el orden no importa. Para el menú sí: «Hogar» no debe ir antes que «Electrónica». La recursión visita primero al padre, luego a los hijos de izquierda a derecha (pre-orden). Con una pila propia sale el mismo orden si metes los hijos al revés: el último hijo entra primero y sale último.

El menú también necesita sangría. Con recursión el nivel sería un parámetro, es decir, estaría en el marco. Ahora no hay marco, así que la pila guarda pares: la categoría y su nivel. Lo que guardaba el marco, ahora lo guarda tu pila.

def print_menu(root):
    stack = [(root, 0)]
    while stack:
        category, level = stack.pop()
        print("  " * level + category.name)
        for child in reversed(category.children):
            stack.append((child, level + 1))


print_menu(shop)

Tienda
  Electrónica
    Teléfonos
    Portátiles
  Hogar
    Cocina

La pila guarda tuplas (category, level). reversed() lee la lista desde atrás, sin copiarla.

Míralo

El árbol profundo pasa

La cadena de la importación, 100 000 niveles, con el recorrido de la lección:

deep = chain(100_000)
print(f"Profundidad 100000: {count_products(deep)} productos")

Profundidad 100000: 100000 productos

En los cuatro lenguajes, sin un hilo con una pila grande y sin tocar ningún límite.

Aquí no hay Bench, a propósito. La recursión y el bucle hacen el mismo número de operaciones: una por categoría, O(n). Las curvas serían iguales. La diferencia está en la memoria: la recursión guarda hasta profundidad marcos en la pila pequeña, el bucle guarda las categorías que esperan en el heap. En un árbol ancho tu pila propia puede hacerse grande (todos los hermanos que esperan), pero su espacio es toda la memoria.

La idea

Un ciclo necesita memoria de lo visto

Tu pila propia no te salva de un ciclo. Si «Hogar» está en «Cocina» y «Cocina» está en «Hogar», las dos se turnan en la pila para siempre. La pila ni siquiera crece, así que nada se desborda y nada se lanza: la página simplemente se cuelga. Eso es peor que el error.

La solución es un conjunto de las categorías ya vistas. Antes de recorrer una categoría, compruebas si ya está en el conjunto:

def count_products(root):
    total = 0
    seen = set()
    stack = [root]
    while stack:
        category = stack.pop()
        if category in seen:
            print("Omito " + category.name + ": ya se visitó")
            continue
        seen.add(category)
        total += category.products
        stack.extend(category.children)
    return total


kitchen.add(home)
print("Productos: " + str(count_products(shop)))

Omito Hogar: ya se visitó
Productos: 20

Un objeto sin __eq__ ni __hash__ se compara por identidad: el set guarda las propias categorías, no sus nombres. El mismo conjunto salva también la recursión: count_products con un parámetro «vistas» detiene el ciclo. Contra la profundidad, sin embargo, solo ayuda el bucle.

Pruébalo

Pon las líneas en orden

Pon en orden el recorrido con pila propia:

category = stack.pop()
while stack:
return total
def count_products(root):
stack = [root]
total = 0
total += category.products
stack.extend(category.children)

Pruébalo

Completa

¿Cuándo se detiene el bucle?

def count_products(root):
    total = 0
    stack = [root]
    while :
        category = stack.pop()
        total += category.products
        stack.extend(category.children)
    return total

Ejercicio

El nivel más profundo

Resuélvelo en tu editor.

Qué tan profundo es el catálogo. La importación cuelga su cadena bajo «Cocina». Lee cuántos niveles tiene la cadena, engánchala e imprime cuántas categorías hay en total y cuál es el nivel más profundo (Tienda está en el nivel 0). Sin recursión: una pila de pares de categoría y nivel, como en el menú.

Categorías: 100006
Nivel más profundo: 100002

Más tareas

El camino de migas sin recursión. Reescribe path de la lección anterior con un bucle subiendo por los padres. La lista se llena desde atrás.
El menú con las cantidades de productos. Imprime el menú, pero junto a cada categoría la suma con sus subcategorías. Pista: la suma del padre está lista solo después de sus hijos, así que con un bucle cada categoría entra dos veces en la pila: una «abierta» y otra «suma».

Más precisamente

La pila en cada lenguaje

Una pila se escribe distinto en cada lenguaje, y no todas las pilas son una buena elección.

Más precisamente, para curiosos

Python: una lista es una pila rápida (append y pop() al final son O(1)). Para una cola usa collections.deque: pop(0) en una lista es O(n).
Un generador con yield from hace corto el recorrido recursivo, pero debajo siguen existiendo marcos: la profundidad sigue chocando con el límite de 1000.

Trampolín. La función no se llama a sí misma, sino que devuelve «qué hay que llamar a continuación», y un bucle externo lo llama. Así la recursión de cola se ejecuta sin pila creciente incluso en lenguajes sin llamadas de cola. Funciona, pero un bucle escrito directamente es más claro.

Una cola en lugar de una pila. Si usas una cola (FIFO) en lugar de una pila, el recorrido pasa por el árbol nivel a nivel: Tienda, luego Electrónica y Hogar, luego Teléfonos, Portátiles y Cocina. Es la búsqueda en anchura (BFS). Encuentra el camino más corto en un grafo, y te la encontrarás en el módulo «Grafos».

Test

Ponte a prueba

1. ¿Cuál de estas llamadas es una llamada de cola?return 1 + months(debt - payment, payment);total += count_products(child);return level_of(category.parent, level + 1);

Una llamada de cola es una llamada tras la cual no queda nada por hacer: su resultado se devuelve directamente. Con total += y con 1 + quien llama todavía tiene trabajo, así que hace falta su marco.

2. ¿Cuál de los cuatro lenguajes convierte la recursión de cola en un bucle, de modo que la pila no crece?Solo PythonTodos, cuando la llamada es la últimaNinguno en la práctica: Java, C# y Python no lo hacen, y el estándar de JavaScript lo pide, pero V8 (Node, Chrome) no lo hace

3. ¿Por qué el recorrido con pila propia atraviesa la cadena de 100 000 niveles y la recursión no?La pila propia es un objeto en la memoria de objetos y crece según haga falta, mientras que la función tiene un único marcoLa pila propia guarda solo una categoría a la vezEl bucle hace menos operaciones

4. Los hijos de una categoría entran en tu pila propia en su orden: Teléfonos, luego Portátiles. ¿Cuál sale primero?Portátiles: una pila devuelve lo último que entróDepende del lenguajeTeléfonos: es el primero

5. ¿Qué pasa si el recorrido con pila propia encuentra un ciclo (Hogar → Cocina → Hogar) y no recuerda las categorías que ha visto?Devuelve una suma incorrecta y se detieneLanza StackOverflowErrorDa vueltas para siempre, sin error: Hogar y Cocina se turnan en la pila

De la recursión al bucle

Cookies