De la recursión a la iteración en Java: 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. Una pila mayor solo traslada el límite: la siguiente importación puede ser más profunda.

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:

static int levelOf(Category category, int level) {
    if (category.parent == null) {
        return level;
    }
    return levelOf(category.parent, level + 1);
}

Aquí la llamada recursiva es lo último que hace el método: 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:

Category last = chain(100_000);
while (!last.children.isEmpty()) {
    last = last.children.get(0);
}
Category deepest = last;
Thread worker = new Thread(null, () -> {
    try {
        System.out.println("Recursión: nivel " + levelOf(deepest, 0));
    } catch (StackOverflowError e) {
        System.out.println("Recursión: " + e);
    }
}, "catalog", 1024 * 1024);
worker.start();
worker.join();
System.out.println("Bucle: nivel " + levelOfLoop(deepest));

Recursión: java.lang.StackOverflowError
Bucle: nivel 99999

La recursión se ejecuta en un hilo con una pila de 1 MB, para que se comporte igual en cualquier máquina.

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.

static int levelOfLoop(Category category) {
    int level = 0;
    while (category.parent != null) {
        category = category.parent;
        level++;
    }
    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

countProducts 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.

static int countProducts(Category root) {
    int total = 0;
    Deque<Category> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Category category = stack.pop();
        total += category.products;
        for (Category child : category.children) {
            stack.push(child);
        }
    }
    return total;
}

System.out.println("Productos: " + countProducts(shop));

Productos: 20

ArrayDeque es una pila y una cola en uno: push pone encima, pop toma de arriba. Cómo funcionan por dentro está en la lección «Pila, cola y lista enlazada».

Míralo

Tu propia pila, paso a paso

static int countProducts(Category root) {
    int total = 0;
    Deque<Category> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Category category = stack.pop();
        total += category.products;
        for (Category child : category.children) {
            stack.push(child);
        }
    }
    return total;
}

System.out.println("Productos: " + countProducts(shop));

Paso a paso, en palabras

La pila es un ArrayDeque 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:

static void printOrder(Category root) {
    Deque<Category> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Category category = stack.pop();
        System.out.println(category.name);
        for (Category child : category.children) {
            stack.push(child);
        }
    }
}

printOrder(shop);

Respuesta

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

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

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.

static void printMenu(Category root) {
    Deque<Entry> stack = new ArrayDeque<>();
    stack.push(new Entry(root, 0));
    while (!stack.isEmpty()) {
        Entry entry = stack.pop();
        Category category = entry.category();
        System.out.println("  ".repeat(entry.level()) + category.name);
        for (Category child : category.children.reversed()) {
            stack.push(new Entry(child, entry.level() + 1));
        }
    }
}

printMenu(shop);

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

Entry es un record con los dos campos: record Entry(Category category, int level) {}. children.reversed() (desde Java 21) es una vista que 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:

Category deep = chain(100_000);
System.out.println("Profundidad 100000: " + countProducts(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:

static int countProducts(Category root) {
    int total = 0;
    Set<Category> seen = new HashSet<>();
    Deque<Category> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Category category = stack.pop();
        if (!seen.add(category)) {
            System.out.println("Omito " + category.name + ": ya se visitó");
            continue;
        }
        total += category.products;
        for (Category child : category.children) {
            stack.push(child);
        }
    }
    return total;
}

kitchen.add(home);
System.out.println("Productos: " + countProducts(shop));

Omito Hogar: ya se visitó
Productos: 20

seen.add devuelve false si la categoría ya está dentro: una comprobación en lugar de dos. Category no sobrescribe equals ni hashCode, así que HashSet compara los propios objetos, no los nombres. El mismo conjunto salva también la recursión: countProducts 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:

Deque<Category> stack = new ArrayDeque<>();
}
return total;
for (Category child : category.children) {
Category category = stack.pop();
}
stack.push(child);
while (!stack.isEmpty()) {
int total = 0;
static int countProducts(Category root) {
}
stack.push(root);
total += category.products;

Pruébalo

Completa

¿Cuándo se detiene el bucle?

static int countProducts(Category root) {
    int total = 0;
    Deque<Category> stack = new ArrayDeque<>();
    stack.push(root);
    while () {
        Category category = stack.pop();
        total += category.products;
        for (Category child : category.children) {
            stack.push(child);
        }
    }
    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

Java: ArrayDeque es la pila recomendada. La clase antigua Stack extiende Vector: sincroniza cada operación, así que es más lenta, y get(i) da acceso también al medio de la pila.
La recursión en un hilo con una pila grande (new Thread(null, work, name, 64 * 1024 * 1024)) es un parche habitual. La solución es el bucle.

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 += countProducts(child);return levelOf(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