Introducirte al mundo de la programación inevitablemente conducirá a desafiarte cada día más. Y con los desafíos, llegan también las preguntas. Por lo cual si programas, no importa tu nivel, con toda seguridad ya has conocido (o acabarás recorriendo) el sitio stackoverflow, un famoso foro de preguntas y respuestas donde la comunidad de los diferentes lenguajes de programación se ayuda mutuamente a resolver problemas y consultas de todo tipo. Lo que probablemente no sepas, es que el nombre de dicho sitio hace referencia a un famoso tipo de error: stack overflow puede traducirse como "desbordamiento de pila". Pero, ¿qué es la pila, y por qué se desbordaría? Explorar esta pregunta nos va a permitir conocer en mayor profundidad cómo se utiliza la memoria (hablaremos particularmente de Python, pero no es la excepción). Y también, es un tema que resulta muy interesante conocer para abordar problemas donde intervenga la recursividad (tema sobre el que hablamos en nuestros anteriores artículos).
Un error de desbordamiento de pila es un error de memoria que se produce cuando se "apilan" demasiados bloques de código, tal que la memoria del equipo no tiene ya donde ubicarlos. Concretamente, cada uno de esos bloques de código se conocen como "frames", y cada uno de ellos se crea cuando se ejecuta un método o función. Dicho frame existirá mientras la función se ejecute, y una vez resuelto y retornado un resultado, el mismo saldrá, liberando dicho espacio de memoria. La pila o stack es una estructura de memoria, donde dichos frames se acumulan hasta resolverse.
Sin embargo, no es tan sencillo. La pila tiene una estructura de entrada y salida de información conocido como LIFO (Last In - First Out), que quiere decir "último en entrar, primero en salir", o en otras palabras: la última función de la pila deberá resolverse para poder proceder con las demás. Tanto la inserción de nuevos frames como su eliminación ocurren por el mismo extremo:
Entonces:- Cuando un método de Python se ejecuta, se agrega un frame al stack
- Este frame maneja el conjunto de variables e información que existe dentro del método
- Cuando el método se resuelte, el frame se elimina del stack
- La creación de un nuevo frame implicará que este debe resolverse antes de poder liberar los anteriores que aún existen en el stack
¿En qué tipos de situaciones esto es importante? Principalmente, en los casos que tenemos funciones que invocan otras funciones. Ya sea porque lo hagan en el contexto de un mismo módulo (funciones diferentes), porque utilicen recursos de otras librerías, o que se invoquen a sí mismas: cada vez que una función invoque a otra, agregará un bloque a la pila, bloque que deberá resolverse para liberar el espacio, y continuar con la resolución del bloque que lo invocó en primer lugar.
Si una función invocó a otra, se espera que para que esta primera función pueda continuar su ejecución, pueda contar con el resultado de la función invocada, no pudiendo proseguir su ejecución con una incógnita.
El caso de las funciones recursivas (o funciones que se llaman a sí mismas) es paradigmático en este sentido, y algo con lo que tener mucho cuidado, ya que por un lado tendremos:
- Una permanente invocación de funciones (agregado de frames)
- Una acumulación en el stack, ya que las funciones no solo se invocan a gran velocidad, sino que también dependerán del resultado de subsecuentes invocaciones para poder liberarse
Por lo cual en esencia toda función recursiva consistirá en el agregado de varios bloques al stack, que deberán resolverse del último al primero para entregar resultados al nivel superior y que finalmente pueda llegar a un resultado final. Sin el caso base (el límite de la recursión), los frames simplemente se apilarán sin resolverse, llegando a este error de memoria "stack overflow" de inmediato. De igual manera, abordar mediante la recursividad un problema que requerirá una gran cantidad de invocaciones para resolverse, también correrá el riesgo de dejarnos sin memoria, aún si su lógica es correcta.
Como conclusión: el desbordamiento de pila (stack overflow) es un error que tendremos que tener presente en el diseño de una solución algorítmica, sobre todo en el contexto de una función recursiva, ya que acumular tareas pendientes (funciones sin resultado), acabará por agotar nuestros recursos de memoria.
