La pila de llamadas por dentro

Código en:JavaC#PythonJavaScript

En resumen: La pila de llamadas guarda un marco por cada llamada que no ha terminado; cuando la recursión es demasiado profunda se agota con RangeError: Maximum call stack size exceeded.

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»:

function countProducts(category) {
  let total = category.products;
  for (const child of category.children) {
    total += countProducts(child);
  }
  return total;
}

const phones = new Category("Teléfonos", 5);
const laptops = new Category("Portátiles", 3);
const electronics = new Category("Electrónica", 2).add(phones, laptops);
const kitchen = new Category("Cocina", 6);
const home = new Category("Hogar", 4).add(kitchen);
const shop = new Category("Tienda", 0).add(electronics, home);
console.log("Productos: " + countProducts(shop));

Salida

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 RangeError: Maximum call stack size 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 countProducts 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:

function factorial(n) {
  if (n === 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

console.log(factorial(3));  // 6

Paso a paso, en palabras

1. El programa llama a factorial(3).
2. Memoria nueva para factorial con n = 3.
3. 3 no es 1, así que la función llama a factorial(2) y espera la respuesta.
4. Lo mismo otra vez: factorial(2) llama a factorial(1). Cada llamada tiene su propio n.
5. n es 1: este es el caso base. Devuelve 1 sin volver a llamar.
6. La respuesta baja: 2 * 1 = 2.
7. Y otra vez: 3 * 2 = 6.
8. 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:

function countProducts(category) {
  let total = category.products;
  for (const child of category.children) {
    total += countProducts(child);
  }
  return total;
}

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

Paso a paso, en palabras

1. El programa llama a countProducts(shop). Por ahora en la pila solo está el marco del programa.
2. Un marco nuevo: el parámetro category = Tienda, la local total = 0 y el punto de retorno, a dónde volver cuando termine.
3. 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.
4. 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.
5. return 5: el marco se tira. Electrónica continúa desde la línea 4: total = 2 + 5 = 7.
6. Portátiles ocupa el mismo lugar en la pila y devuelve 3. total = 7 + 3 = 10.
7. Electrónica devuelve 10. El marco de Tienda despierta donde se detuvo: total = 10.
8. El siguiente hijo: Hogar, luego Cocina. Otra vez 3 marcos, en los mismos lugares.
9. Cocina devuelve 6, Hogar devuelve 4 + 6 = 10, y Tienda llega a 10 + 10 = 20.
10. 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í countProducts 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.

let depth = 0;
let deepest = 0;

function countProducts(category) {
  depth++;
  deepest = Math.max(deepest, depth);
  let total = category.products;
  for (const child of category.children) {
    total += countProducts(child);
  }
  depth--;
  return total;
}

const total = countProducts(shop);
console.log(`${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 3 marcos a la vez

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

Comprobar

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.

console.log(`Profundidad 900: ${countProducts(chain(900))} productos`);
try {
  console.log(`Profundidad 100000: ${countProducts(chain(100_000))} productos`);
} catch (e) {
  console.log(`Profundidad 100000: ${e.name}: ${e.message}`);
}

Salida

Profundidad 900: 900 productos
Profundidad 100000: RangeError: Maximum call stack size exceeded

En Node la pila es de unos 1 MB. Cuántas llamadas caben depende del marco: para countProducts son unas 10 000. Pasan 900 niveles, 100 000 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»:

withdraw(amount) {
  if (amount > this.balance) {
    throw new RangeError("No alcanza el dinero");
  }
  this.balance -= amount;
}

function payRent(account) {
  account.withdraw(800);
  console.log("El alquiler está pagado.");
}

try {
  payRent(new Account(500));
} catch (e) {
  console.log(`Rechazado: ${e.message}`);
}

Paso a paso, en palabras

1. El programa llama a payRent para una cuenta con 500 €.
2. payRent llama a withdraw(800): un marco nuevo encima.
3. 800 > 500: el método lanza una excepción.
4. El saldo no cambia: el marco se descarta sin terminar sus líneas.
5. payRent no tiene catch: «El alquiler está pagado.» no se imprime, el marco se descarta.
6. catch 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 countProducts? 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 {
  console.log("Productos: " + countProducts(shop));
} catch (e) {
  console.log(`Con el ciclo: ${e.name}: ${e.message}`);
}

Salida

Con el ciclo: RangeError: Maximum call stack size 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 null.

function find(category, name) {
  if (category.name === name) {
    return category;
  }
  for (const child of category.children) {
    const found = find(child, name);
    if (found !== null) {
      return found;
    }
  }
  return null;
}

for (const name of ["Cocina", "Jardín"]) {
  const found = find(shop, name);
  if (found === null) {
    console.log(name + ": no existe esa categoría");
  } else {
    console.log(`${name}: ${found.products} productos`);
  }
}

Salida

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?

function find(category, name) {
  if (category.name === name) {
    return category;
  }
  for (const child of category.children) {
    const found = find(child, name);
    if (found !== null) {
      return found;
    }
  }
  return ;
}

Comprobar

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 RangeError. ¿Qué línea está mal?

Elige la línea con el error.

1function months(debt, payment) {2 if (debt === 0) {3 return 0;4 }5 return 1 + months(debt - payment, payment);6}

Comprobar

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 null si no está. Los dos casos base son como en find. Lee el nombre e imprime el camino.

Entrada

Cocina

Salida

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 Node la pila es de unos 1 MB y se cambia con node --stack-size=…. Un valor mayor que el que el sistema operativo da al proceso no ayuda: el proceso se cae sin RangeError. En el navegador el tamaño es distinto en cada navegador.

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

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

Comprobar

Empezar la lección de nuevo

Lecciones relacionadas

• Se basa en: Funciones flecha · Async, await e hilos · Big-O: cómo crece el trabajo · Complejidad en espacio
• Continúa en: De la recursión al bucle · Exponenciación rápida · Árbol binario de búsqueda · DFS: islas y ciclos
• Ejercicios sobre el tema: Recursión