4 de mayo - 10 de mayo

Recursividad y Manejo de Memoria Dinámica

Pilas, heaps, garbage collection y gramáticas formales.

Hasta esta semana, casi todos nuestros algoritmos han sido iterativos: una secuencia de instrucciones, eventualmente repetida con un while o un for, que avanza paso a paso hacia una solución. La iteración es una forma natural de pensar para la máquina —refleja directamente el ciclo fetch-decode-execute que estudiamos en la Semana 1— pero no siempre es la forma más natural de pensar para nosotros, ni la más clara para el lector del programa. Hay problemas cuya estructura es intrínsecamente recursiva: la respuesta para una entrada de tamaño n se define en términos de la respuesta para una entrada de tamaño menor. La recursividad es una técnica de diseño algorítmico en la que una función se define en términos de sí misma, aplicada a una entrada estrictamente más pequeña. Es una forma de pensar que se vuelve indispensable cuando los datos tienen estructura jerárquica (árboles, expresiones aritméticas, sistemas de archivos), cuando el problema admite la estrategia divide y vencerás (Semana 6), o cuando la definición matemática del problema es en sí misma recursiva.

El segundo tema de la semana es la memoria dinámica. En la Semana 7 vimos que los objetos de Python viven en el heap; lo que no discutimos allí fue quién los libera cuando ya no se usan. En lenguajes como C o C++ esa responsabilidad recae sobre el programador. Python —como Java, C# o Go— ofrece un garbage collector: un mecanismo automático que detecta los objetos sin referencias activas y los elimina sin intervención del programador. Comprender cómo funciona el GC de Python es importante por dos razones: explica por qué ciertas prácticas (como las referencias circulares) pueden tener consecuencias sutiles, y nos prepara para apreciar el costo y el diseño de los lenguajes que sí nos hacen liberar la memoria a mano.

Cerramos con una conexión holística que retoma directamente la naturaleza recursiva: las gramáticas formales. Los lenguajes de programación se describen mediante reglas recursivas (BNF, EBNF), y los compiladores e intérpretes que estudiamos en la Semana 6 construyen árboles de derivación aplicando esas reglas. Veremos que el código Python que escribimos es procesado por un programa —el parser de CPython— cuya tarea es esencialmente recursiva.

Los problemas de esta semana introducen la recursividad como técnica de diseño algorítmico, su análisis comparado con la iteración, los límites prácticos que impone la pila de ejecución y la aplicación natural de la recursividad al recorrido de estructuras jerárquicas. El eje temático es el patrón caso base + caso recursivo: una función se define en términos de sí misma aplicada a una entrada estrictamente más pequeña, hasta que la entrada llega al caso base que se resuelve directamente. Sobre esa base se construye la discusión de cuándo conviene la recursividad: cuando el problema admite una formulación divide-y-vencerás (Torres de Hanói, búsqueda binaria) o cuando los datos tienen estructura intrínsecamente jerárquica (archivos con directorios anidados, expresiones aritméticas, gramáticas).

Las funciones recursivas establecen su caso base como el primer bloque del cuerpo: la disciplina de poner el caso base antes que el caso recursivo no es estética, evita el RecursionError que se produce cuando un caso base mal escrito nunca se alcanza.