Caso real

Desbordamiento de pila

La pila de llamadas tiene un tamaño fijo (unos megabytes). Una función recursiva que recorre una lista enlazada de un millón de nodos, una llamada por nodo, apila un millón de registros y agota ese espacio: el programa termina con un desbordamiento de pila. Por eso muchas bibliotecas recorren sus estructuras con un bucle, o con una pila propia sobre un array dinámico, que crece en la memoria general.

Lo que importa no es cuántos nodos tiene la estructura, sino cuántas llamadas están abiertas a la vez, porque un registro se desapila al terminar su llamada. Piensa en una función que recorre un árbol de carpetas y se llama una vez por carpeta: su pila de llamadas aguanta 10 000 registros. ¿Qué forma de árbol la hace fallar?