De la recursión a la iteración en JavaScript: 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:

function levelOf(category, level) {
  if (category.parent === null) {
    return level;
  }
  return levelOf(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:

let last = chain(100_000);
while (last.children.length > 0) {
  last = last.children[0];
}
try {
  console.log("Recursión: nivel " + levelOf(last, 0));
} catch (e) {
  console.log(`Recursión: ${e.name}: ${e.message}`);
}
console.log("Bucle: nivel " + levelOfLoop(last));

Recursión: RangeError: Maximum call stack size 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.

function levelOfLoop(category) {
  let 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.

function countProducts(root) {
  let total = 0;
  const stack = [root];
  while (stack.length > 0) {
    const category = stack.pop();
    total += category.products;
    stack.push(...category.children);
  }
  return total;
}

console.log("Productos: " + countProducts(shop));

Productos: 20

Un arreglo es una pila: push pone 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

function countProducts(root) {
  let total = 0;
  const stack = [root];
  while (stack.length > 0) {
    const category = stack.pop();
    total += category.products;
    stack.push(...category.children);
  }
  return total;
}

console.log("Productos: " + countProducts(shop));

Paso a paso, en palabras

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

function printOrder(root) {
  const stack = [root];
  while (stack.length > 0) {
    const category = stack.pop();
    console.log(category.name);
    stack.push(...category.children);
  }
}

printOrder(shop);

Respuesta

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

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

Tienda
Electrónica
Hogar
Teléfonos
Portátiles
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.

function printMenu(root) {
  const stack = [[root, 0]];
  while (stack.length > 0) {
    const [category, level] = stack.pop();
    console.log("  ".repeat(level) + category.name);
    for (const child of category.children.toReversed()) {
      stack.push([child, level + 1]);
    }
  }
}

printMenu(shop);

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

La pila guarda arreglos [category, level]. toReversed() (desde 2023, Node 20) crea una copia invertida y deja children en paz. reverse() invertiría la propia lista.

Míralo

El árbol profundo pasa

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

const deep = chain(100_000);
console.log(`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:

function countProducts(root) {
  let total = 0;
  const seen = new Set();
  const stack = [root];
  while (stack.length > 0) {
    const category = stack.pop();
    if (seen.has(category)) {
      console.log("Omito " + category.name + ": ya se visitó");
      continue;
    }
    seen.add(category);
    total += category.products;
    stack.push(...category.children);
  }
  return total;
}

kitchen.add(home);
console.log("Productos: " + countProducts(shop));

Omito Hogar: ya se visitó
Productos: 20

Set compara los objetos por referencia: dos categorías con el mismo nombre son distintas. 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:

let total = 0;
const category = stack.pop();
while (stack.length > 0) {
const stack = [root];
}
return total;
total += category.products;
}
stack.push(...category.children);
function countProducts(root) {

Pruébalo

Completa

¿Cuándo se detiene el bucle?

function countProducts(root) {
  let total = 0;
  const stack = [root];
  while () {
    const category = stack.pop();
    total += category.products;
    stack.push(...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

JavaScript: un arreglo es una pila (push y pop al final son O(1)). shift() al principio es O(n), así que un arreglo no es una buena cola para muchos elementos.
stack.push(...children) reparte los hijos como argumentos. Con cientos de miles de hijos en una categoría esto solo ya desborda la pila: entonces usa un bucle con un push para cada hijo.

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