Ir al contenido
wannacode

La pila de llamadas por dentro

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 y el proceso muere con StackOverflowException.

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 método recursivo los cuenta, como en la lección «Recursión»:

static int CountProducts(Category category)
{
    int total = category.Products;
    foreach (Category child in category.Children)
    {
        total += CountProducts(child);
    }
    return total;
}


var phones = new Category("Teléfonos", 5);
var laptops = new Category("Portátiles", 3);
var electronics = new Category("Electrónica", 2).Add(phones, laptops);
var kitchen = new Category("Cocina", 6);
var home = new Category("Hogar", 4).Add(kitchen);
var shop = new Category("Tienda", 0).Add(electronics, home);
Console.WriteLine("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 Stack overflow., y el proceso del servidor muere.

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:

static int Factorial(int n)
{
    if (n == 1)
    {
        return 1;
    }
    return n * Factorial(n - 1);
}


Console.WriteLine(Factorial(3));  // 6
Paso a paso, en palabras
  1. Main llama a Factorial(3).
  2. Memoria nueva para Factorial con n = 3.
  3. 3 no es 1, así que el método 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 Main 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:

static int CountProducts(Category category)
{
    int total = category.Products;
    foreach (Category child in category.Children)
    {
        total += CountProducts(child);
    }
    return total;
}


Console.WriteLine("Productos: " + CountProducts(shop));
Paso a paso, en palabras
  1. Main llama a CountProducts(shop). Por ahora en la pila solo está el marco de Main.
  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 6 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 6: 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.

static int depth = 0;
static int deepest = 0;


static int CountProducts(Category category)
{
    depth++;
    deepest = Math.Max(deepest, depth);
    int total = category.Products;
    foreach (Category child in category.Children)
    {
        total += CountProducts(child);
    }
    depth--;
    return total;
}


int total = CountProducts(shop);
Console.WriteLine($"{total} productos, como máximo {deepest} marcos a la vez");
Respuesta

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.

var small = Chain(900);
Console.WriteLine($"Profundidad 900: {CountProducts(small)} productos");
var deep = Chain(100_000);
var worker = new Thread(() =>
{
    try
    {
        Console.WriteLine($"Profundidad 100000: {CountProducts(deep)} productos");
    }
    catch (InsufficientExecutionStackException e)
    {
        Console.WriteLine("Profundidad 100000: " + e.GetType().Name);
    }
}, 1024 * 1024);
worker.Start();
worker.Join();
Salida
Profundidad 900: 900 productos
Profundidad 100000: InsufficientExecutionStackException

En C# un desbordamiento real no se puede capturar: el proceso imprime Stack overflow., una lista de marcos, y se detiene, junto con todo el servidor. Ningún catch lo puede salvar. Por eso el programa de arriba no lo provoca de verdad. La primera línea de CountProducts es una protección: RuntimeHelpers.EnsureSufficientExecutionStack() lanza InsufficientExecutionStackException cuando la pila está casi llena, y esa excepción sí se puede capturar. El recorrido se ejecuta en un hilo con una pila de 1 MB (el segundo argumento de new Thread), para que se comporte igual en cualquier máquina: en Linux el hilo principal tiene 8 MB y cabrían más niveles.

static int CountProducts(Category category)
{
    RuntimeHelpers.EnsureSufficientExecutionStack();
    int total = category.Products;
    foreach (Category child in category.Children)
    {
        total += CountProducts(child);
    }
    return total;
}

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. La protección lanza InsufficientExecutionStackException, y cae como cualquier excepción: un marco sin catch se tira y la excepción sigue bajando. Así cayó la excepción al retirar dinero por los marcos en la lección «Lanzar excepciones y crear las tuyas»:

public void Withdraw(int amount)
{
    if (amount > Balance)
    {
        throw new ArgumentException("No alcanza el dinero");
    }
    Balance -= amount;
}
static void PayRent(Account account)
{
    account.Withdraw(800);
    Console.WriteLine("El alquiler está pagado.");
}


try
{
    PayRent(new Account(500));
}
catch (ArgumentException e)
{
    Console.WriteLine("Rechazado: " + e.Message);
}
Paso a paso, en palabras
  1. Main 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 Main atrapa la excepción y el programa 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. Un StackOverflowException real no cae así: el proceso se detiene en el acto.

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 método 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.WriteLine("Productos: " + CountProducts(shop));
}
catch (InsufficientExecutionStackException e)
{
    Console.WriteLine("Con el ciclo: " + e.GetType().Name);
}
Salida
Con el ciclo: InsufficientExecutionStackException

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 método devuelve la categoría sin seguir bajando;
  • más abajo no hay nada: ninguna subcategoría la contiene, y el método devuelve null.
static Category? Find(Category category, string name)
{
    if (category.Name == name)
    {
        return category;
    }
    foreach (Category child in category.Children)
    {
        Category? found = Find(child, name);
        if (found != null)
        {
            return found;
        }
    }
    return null;
}


foreach (string name in new[] { "Cocina", "Jardín" })
{
    Category? found = Find(shop, name);
    if (found == null)
    {
        Console.WriteLine(name + ": no existe esa categoría");
    }
    else
    {
        Console.WriteLine($"{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?

static Category? Find(Category category, string name)
{
    if (category.Name == name)
    {
        return category;
    }
    foreach (Category child in category.Children)
    {
        Category? found = Find(child, name);
        if (found != null)
        {
            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 mata el proceso con Stack overflow.. ¿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 método 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 .NET el hilo principal tiene unos 1 MB en Windows, y en Linux lo que da el sistema, normalmente 8 MB. new Thread(work, maxStackSize) le da a un hilo nuevo su propio tamaño. EnsureSufficientExecutionStack mira cuánto queda en la pila del hilo actual, así que la protección funciona con cualquier tamaño.

El tamaño de un marco. Cuántos marcos caben depende del marco: más parámetros y variables locales son más bytes. El compilador JIT puede hacer un marco más pequeño, así que el número de llamadas antes del desbordamiento no es un número exacto y cambia entre ejecuciones.

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»?
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?
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?
4. months(130, 50) debería devolver 3, pero desborda la pila. ¿Por qué?
5. ¿Qué mide el límite de Python, y qué mide el límite de la pila en Java, C# y JavaScript?

Creado por Ivo Gergov como parte de la campaña de Evo Tech por una educación accesible en programación ·