Recursión frente a iteración: profundidad de pila, límites y cuándo conviene convertir

Qué es

Una función recursiva resuelve un problema llamándose a sí misma sobre instancias más pequeñas; cada llamada sin terminar ocupa un marco en la pila de llamadas. La pila es finita. Python impone un límite de recursión, legible con sys.getrecursionlimit(), que la documentación describe como una forma de evitar que una recursión infinita desborde la pila de C y haga fallar al intérprete; superarlo lanza RecursionError. El código nativo está acotado por el tamaño de pila del hilo (el límite del hilo principal es RLIMIT_STACK en getrlimit(2)); desbordarlo produce un fallo de segmentación, no una excepción. La iteración mantiene el estado en variables o en una pila o cola explícita en el heap, cuyo tamaño está limitado por la memoria y no por una pila fija.

Por qué importa

Una recursión cuya profundidad sigue la entrada es una superficie de denegación de servicio: un JSON profundamente anidado, un árbol de directorios con miles de niveles, una estructura enlazada larga o un analizador de paréntesis anidados pueden hacerse fallar con una entrada construida a propósito. No conviene asumir la eliminación de llamadas de cola a menos que la especificación del lenguaje lo prometa; la mayoría de los lenguajes habituales no lo hacen, de modo que un «bucle tail-recursivo» sigue consumiendo un marco por iteración.

Cómo aplicarlo

• Reservar la recursión para problemas cuya profundidad está acotada por la estructura y no por el tamaño de la entrada: árboles equilibrados, árboles de sintaxis de un analizador con tamaño limitado, divide y vencerás sobre mitades (la profundidad es logarítmica).
• Convertir a iteración cuando la profundidad sea lineal respecto a la entrada: recorrer un árbol con una pila explícita (en profundidad) o una cola (en anchura); sustituir la recursión lineal por un bucle con acumulador.
• Donde se mantenga la recursión, pasar un parámetro de profundidad y fallar limpiamente en un máximo documentado antes de alcanzar el límite del runtime, con un error que indique el límite.
• Tratar elevar el límite de recursión como un remedio provisional: cambia un RecursionError por un posible desbordamiento de la pila de C, y el tamaño de pila de otros hilos se establece de forma separada al del hilo principal.
• Memoizar las funciones recursivas con subproblemas superpuestos (véase programación dinámica); la memoización reduce el trabajo, no la profundidad.

Trampas

Convertir a iteración cambia el orden de visita a menos que los hijos se apilen en orden inverso. La recursión mutua oculta la profundidad repartida entre varias funciones. Las cadenas profundas de generadores delegados (yield from) se recorren en cada reanudación; conviene tratar su profundidad como profundidad de recursión. Las excepciones que desenrollan una pila profunda son lentas y producen trazas enormes. Los __eq__, __repr__ o serializadores recursivos sobre datos cíclicos nunca terminan; hay que llevar el control de los objetos ya visitados.

El límite de profundidad también se aplica a la forma iterativa

Sustituir la recursión por una pila explícita no acota la profundidad; simplemente traslada el límite de la pila de llamadas al heap, donde el fallo es la terminación por falta de memoria de todo el proceso en lugar de un RecursionError capturable. Para el anidamiento controlado por la entrada (JSON, paréntesis, árboles de directorios), conviene mantener una profundidad máxima documentada en ambas formas: comprobar el parámetro de profundidad de recursión en la versión recursiva, y comprobar la longitud de la pila explícita en la versión iterativa, fallando con un error que indique el límite. Los analizadores suelen incorporar ese límite (por ejemplo, serde_json rechaza por defecto los documentos anidados a más de 128 niveles). Con un límite establecido, la elección entre recursión e iteración es una cuestión de claridad y de coste de marco del runtime, no de seguridad.