Recursión o iteración, cómo elegir

Casi toda recursión se puede escribir con un ciclo, y todo ciclo se puede simular con recursión. Entonces la pregunta útil no es cuál puede resolver el problema, sino dónde queda guardado el trabajo pendiente y quién controla cuánto puede crecer.

El mismo proceso, dos formas

Estas dos funciones calculan lo mismo:

def factorial_recursive(n):
    return 1 if n <= 1 else n * factorial_recursive(n - 1)

def factorial_iterative(n):
    result = 1
    for value in range(2, n + 1):
        result *= value
    return result

Las dos hacen $O(n)$ multiplicaciones. La diferencia está en el estado: la versión recursiva lo reparte entre $n$ marcos de la pila, cada uno con su n y una multiplicación pendiente; la iterativa lo concentra en dos variables, result y value.

Qué paga cada una

Eso no vuelve “mala” a la recursión. Muestra que dos programas con la misma complejidad temporal pueden tener perfiles de memoria muy distintos. Para procesos lineales largos, un ciclo suele ser la representación más directa y más segura.

Cuando los datos son recursivos

En árboles, grafos y estructuras anidadas la cosa cambia: la recursión sigue la forma de los datos. Un recorrido en profundidad visita un nodo y repite lo mismo con cada hijo, y el código lo dice casi literal:

def depth_first(node, visited):
    visited.append(node)
    for child in tree[node]:
        depth_first(child, visited)
    return visited

Un ciclo, en cambio, tiene que guardar por su cuenta qué nodos faltan. No elimina la pila: la convierte en una estructura explícita. Eso agrega código, pero también permite inspeccionarla, limitarla, pausarla o guardarla.

La pila, a la vista

Esta es la misma búsqueda en profundidad sin recursión. pending hace el papel que antes tenía la pila de llamadas.

Profundidad que no controlás

Si la profundidad está acotada y es chica, como un árbol balanceado o un menú de tres niveles, la recursión es clara y segura. Si viene de usuarios, archivos o cadenas de dependencias sin límite conocido, una pila explícita evita depender del máximo del runtime.

La estructura explícita sigue ocupando memoria proporcional a lo pendiente, pero vive en el heap, que es mucho más grande que la pila, y cuando se agota se puede manejar el error en vez de caer.

Convertir cualquier recursión

El DFS de arriba fue fácil de convertir porque el trabajo se hace antes de bajar a los hijos. Cuando hay trabajo después de la llamada recursiva, la pila explícita tiene que recordar también en qué punto quedó cada nodo, que es exactamente lo que guarda la dirección de retorno de un marco.

def postorder(root):
    pending = [(root, False)]
    order = []
    while pending:
        node, expanded = pending.pop()
        if expanded:
            order.append(node)
        else:
            pending.append((node, True))
            pending.extend((child, False) for child in reversed(tree[node]))
    return order

Cómo elegir

No decidas por cantidad de líneas. Compará espacio pico, límites del entorno y facilidad para probar. La versión más corta puede esconder justo el riesgo que importa en producción.

Cierre