El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Recursión y Programación Dinámica

Siguiente ►
►

En la lección anterior analizamos recurrencias; en esta aprenderemos a diseñar los algoritmos que las generan. La recursión —resolver un problema en términos de versiones más pequeñas de sí mismo— es una de las técnicas de diseño más potentes que existen. Pero tiene una patología conocida: cuando los subproblemas se repiten, la recursión ingenua repite trabajo hasta volverse exponencial. La cura es la programación dinámica (PD): recordar lo ya calculado, ya sea sobre la marcha (memoización) o construyendo la solución de abajo arriba.

En Rutalia este tema es pan de cada día: la ciudad se modela como una cuadrícula de manzanas y muchas preguntas operativas ("¿cuál es el coste mínimo para cruzar la zona centro?", "¿de cuántas formas puedo llegar al punto de entrega?") tienen una estructura recursiva natural con subproblemas que se solapan masivamente.

Contenido

  1. Recursión bien hecha: caso base, avance y pila de llamadas
  2. Divide y vencerás como esquema general
  3. El problema: subproblemas solapados
  4. Memoización (top-down)
  5. Programación dinámica bottom-up
  6. Reconstrucción de la solución

  1. Recursión bien hecha: caso base, avance y pila de llamadas

Una función recursiva correcta necesita exactamente tres ingredientes:

  1. Caso(s) base: entradas tan pequeñas que se resuelven directamente, sin recursión.
  2. Avance garantizado: cada llamada recursiva se hace sobre una entrada estrictamente más cercana a un caso base.
  3. Combinación correcta: la solución del problema se construye correctamente a partir de las soluciones de los subproblemas (aquí ayuda el "salto de fe recursivo": asume que la llamada recursiva funciona y comprueba que la combinación es correcta).

Ejemplo mínimo con Rutalia: sumar el peso total de la carga de una furgoneta.

def peso_total(pesos):
    """Suma recursiva de una lista de pesos (kg)."""
    if not pesos:                          # caso base: lista vacía
        return 0.0
    return pesos[0] + peso_total(pesos[1:])  # avance: la lista se acorta en 1


print(peso_total([2.5, 1.0, 4.2]))  # 7.7

(Sí, en producción esto sería sum(pesos) o un bucle; el valor del ejemplo es ver los tres ingredientes desnudos. Nota además que pesos[1:] copia la lista: esta versión didáctica cuesta Θ(n²) en tiempo; pasar índices en lugar de sublistas la deja en Θ(n).)

La pila de llamadas

Cada llamada pendiente ocupa un marco (frame) en la pila de llamadas: parámetros, variables locales y el punto de retorno. Esto tiene dos consecuencias prácticas:

  • Coste espacial: una recursión de profundidad d usa Θ(d) de memoria de pila además de lo que reserve explícitamente. peso_total sobre n elementos tiene profundidad n → espacio Θ(n), frente al Θ(1) del bucle equivalente.
  • Límite de Python: CPython corta las recursiones a ~1000 niveles (RecursionError) para proteger la pila. Se puede ampliar con sys.setrecursionlimit, pero es un parche: si la profundidad crece con n, para el millón de pedidos de Rutalia hará falta una versión iterativa. Python tampoco optimiza la recursión de cola (a diferencia de otros lenguajes), así que no cuentes con ello.
flowchart TD
    A["peso_total([2.5, 1.0, 4.2])"] --> B["peso_total([1.0, 4.2])"]
    B --> C["peso_total([4.2])"]
    C --> D["peso_total([]) → 0.0"]
    D -.->|"devuelve 0.0"| C
    C -.->|"devuelve 4.2"| B
    B -.->|"devuelve 5.2"| A
    A -.->|"devuelve 7.7"| FIN["resultado: 7.7"]

  1. Divide y vencerás como esquema general

Divide y vencerás (DyV) es el patrón recursivo por excelencia, en tres pasos:

  1. Dividir el problema en subproblemas independientes (idealmente de tamaño n/b).
  2. Vencer: resolver cada subproblema recursivamente (caso base cuando es trivial).
  3. Combinar las soluciones parciales en la solución global.

Ejemplo en Rutalia: encontrar el pedido más pesado y el más ligero de la furgoneta de una pasada, partiendo la lista por la mitad:

def min_max_peso(pesos, i, j):
    """Devuelve (mínimo, máximo) de pesos[i..j], por divide y vencerás."""
    if i == j:                       # caso base: un elemento
        return pesos[i], pesos[i]
    m = (i + j) // 2                 # dividir
    min1, max1 = min_max_peso(pesos, i, m)      # vencer (mitad izquierda)
    min2, max2 = min_max_peso(pesos, m + 1, j)  # vencer (mitad derecha)
    return min(min1, min2), max(max1, max2)     # combinar


pesos = [2.5, 7.1, 0.8, 4.2, 3.3]
print(min_max_peso(pesos, 0, len(pesos) - 1))   # (0.8, 7.1)

Su recurrencia es T(n) = 2T(n/2) + c, que por el teorema maestro de la lección 01-02 (caso 1) da Θ(n). La profundidad de recursión es Θ(log n), así que la pila no es problema.

DyV funciona de maravilla cuando los subproblemas son independientes (no comparten trabajo). Los grandes algoritmos de ordenación y búsqueda que estudiaremos en el módulo 4 (mergesort, quicksort, búsqueda binaria) son DyV puro. El problema llega cuando los subproblemas no son independientes.

  1. El problema: subproblemas solapados

El ejemplo canónico es la sucesión de Fibonacci: F(0)=0, F(1)=1, F(n)=F(n−1)+F(n−2). La traducción directa a código:

def fib(n):
    if n < 2:                       # casos base
        return n
    return fib(n - 1) + fib(n - 2)  # dos llamadas recursivas

Es correcta… y desastrosa. fib(50) tarda minutos. ¿Por qué? Dibujemos el árbol de llamadas:

flowchart TD
    A["fib(5)"] --> B["fib(4)"]
    A --> C["fib(3)"]
    B --> D["fib(3)"]
    B --> E["fib(2)"]
    C --> F["fib(2)"]
    C --> G["fib(1)"]
    D --> H["fib(2)"]
    D --> I["fib(1)"]

fib(3) se calcula 2 veces, fib(2) tres veces… y el número de repeticiones crece exponencialmente: T(n) = T(n−1) + T(n−2) + c, que crece como la propia Fibonacci → Θ(φⁿ) con φ ≈ 1,618. Solo hay n+1 subproblemas distintos, pero el árbol tiene del orden de 2ⁿ nodos: estamos resolviendo los mismos subproblemas una y otra vez. Esto es el solapamiento de subproblemas.

Cuando un problema tiene (a) subproblemas solapados y (b) subestructura óptima (la solución óptima se compone de soluciones óptimas de los subproblemas), es candidato a programación dinámica. Hay dos estrategias.

  1. Memoización (top-down)

Memoización: mantener la recursión tal cual, pero guardar cada resultado la primera vez que se calcula y reutilizarlo después. Es la vía de menor esfuerzo desde una recursión ya escrita.

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n < 2:
        return n
    if n not in memo:                  # ¿ya lo calculamos?
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

Cada uno de los n+1 subproblemas se calcula una sola vez, con trabajo constante fuera de las llamadas: tiempo Θ(n), espacio Θ(n) (memo + pila). De exponencial a lineal guardando un diccionario.

Python trae la memoización de serie:

from functools import lru_cache

@lru_cache(maxsize=None)     # o @cache en Python 3.9+
def fib_cached(n):
    if n < 2:
        return n
    return fib_cached(n - 1) + fib_cached(n - 2)

Ahora el problema de Rutalia. La zona centro es una cuadrícula de manzanas; el repartidor entra por la esquina noroeste (0, 0) y debe llegar al punto de entrega en la esquina sureste (F−1, C−1), moviéndose solo hacia el sur o hacia el este (calles de sentido único). Cada celda tiene un coste de atravesarla (minutos según tráfico, datos ficticios). Queremos el coste mínimo del trayecto.

Definición recursiva: sea mc(f, c) el coste mínimo para llegar a la celda (f, c). A (f, c) solo se llega desde arriba o desde la izquierda, así que:

  • mc(0, 0) = coste[0][0] (caso base)
  • mc(f, c) = coste[f][c] + min(mc(f−1, c), mc(f, c−1)), tratando los bordes (primera fila/columna) con un solo predecesor.

Esta ecuación —la relación de recurrencia del problema— exhibe la subestructura óptima: el mejor camino hasta (f, c) termina en el mejor camino hasta una de sus dos predecesoras. Y los subproblemas se solapan: a mc(2, 2) se llega preguntando por mc(1, 2) y mc(2, 1), y ambas preguntan por mc(1, 1).

from functools import lru_cache

# Minutos por manzana (datos ficticios): 4 filas x 5 columnas
COSTE = [
    [3, 2, 4, 1, 5],
    [1, 9, 3, 2, 2],
    [4, 1, 2, 8, 1],
    [2, 3, 1, 2, 3],
]

def coste_minimo_td(coste):
    """Coste mínimo de (0,0) a la esquina inferior derecha. Top-down."""
    F, C = len(coste), len(coste[0])

    @lru_cache(maxsize=None)
    def mc(f, c):
        if f == 0 and c == 0:                 # caso base: origen
            return coste[0][0]
        if f < 0 or c < 0:                    # fuera de la cuadrícula
            return float("inf")               # coste infinito: nunca se elige
        return coste[f][c] + min(mc(f - 1, c), mc(f, c - 1))

    return mc(F - 1, C - 1)


print(coste_minimo_td(COSTE))   # 17

Detalles a observar:

  • El truco de devolver float("inf") fuera de la cuadrícula simplifica los bordes: min descarta esas ramas solo.
  • Hay F·C subproblemas distintos y cada uno se resuelve una vez con trabajo O(1) → tiempo Θ(F·C), espacio Θ(F·C). Sin memoización, el árbol de llamadas sería exponencial (cada celda bifurca en dos).
  • La profundidad de recursión es Θ(F+C); para cuadrículas muy grandes puede rozar el límite de Python. Motivo de más para la siguiente estrategia.

  1. Programación dinámica bottom-up

La versión bottom-up elimina la recursión: se identifica el orden en que los subproblemas se necesitan (de los pequeños a los grandes) y se rellena una tabla iterativamente.

def coste_minimo_bu(coste):
    """Coste mínimo de (0,0) a la esquina inferior derecha. Bottom-up."""
    F, C = len(coste), len(coste[0])
    tabla = [[0] * C for _ in range(F)]    # tabla[f][c] = mc(f, c)

    tabla[0][0] = coste[0][0]
    for c in range(1, C):                  # primera fila: solo se llega desde la izquierda
        tabla[0][c] = tabla[0][c - 1] + coste[0][c]
    for f in range(1, F):                  # primera columna: solo desde arriba
        tabla[f][0] = tabla[f - 1][0] + coste[f][0]

    for f in range(1, F):                  # resto: mínimo de los dos predecesores
        for c in range(1, C):
            tabla[f][c] = coste[f][c] + min(tabla[f - 1][c], tabla[f][c - 1])

    return tabla[F - 1][C - 1]


print(coste_minimo_bu(COSTE))   # 17

Mismo resultado, misma complejidad Θ(F·C), pero sin pila de llamadas ni sobrecoste de función por celda. Además, como cada fila solo consulta la anterior, el espacio puede reducirse a Θ(C) guardando una sola fila (optimización habitual cuando no hace falta reconstruir el camino).

Comparativa de las tres aproximaciones:

Enfoque Tiempo Espacio Ventajas Inconvenientes
Recursión ingenua exponencial Θ(F+C) pila inmediata desde la recurrencia inviable salvo n minúsculo
Memoización (top-down) Θ(F·C) Θ(F·C) + pila se escribe en 2 minutos desde la recurrencia; solo calcula subproblemas necesarios límite de pila; sobrecoste por llamada
PD bottom-up Θ(F·C) Θ(F·C), reducible a Θ(C) sin pila; más rápida en constantes; espacio optimizable exige pensar el orden de llenado; calcula todos los subproblemas

Receta general para plantear una PD, aplicable a casi cualquier problema:

  1. Define el subproblema con precisión ("mc(f, c) = coste mínimo para llegar a (f, c)").
  2. Escribe la recurrencia que lo relaciona con subproblemas menores, con sus casos base.
  3. Cuenta: nº de subproblemas × trabajo por subproblema = complejidad.
  4. Elige top-down (rápido de escribir) o bottom-up (rápido de ejecutar) y, si procede, optimiza el espacio.

Una variante de conteo con la misma estructura: ¿de cuántas formas distintas puede el repartidor llegar al destino? Misma cuadrícula, recurrencia formas(f, c) = formas(f−1, c) + formas(f, c−1) con formas(0, 0) = 1 (y 0 fuera de la cuadrícula). Solo cambia el caso base y que se suman caminos en lugar de tomar el mínimo. Lo dejamos como ejercicio.

  1. Reconstrucción de la solución

Saber que el trayecto óptimo cuesta 17 minutos está bien; el repartidor de Rutalia necesita además el camino. Hay dos técnicas:

  • Guardar decisiones: junto a cada valor de la tabla, anotar de dónde vino (el argmin).
  • Retroceder comparando (la que usaremos): partir de la celda final y, en cada paso, moverse a la predecesora cuyo valor en la tabla cuadra con la ecuación. No requiere memoria extra.
def camino_minimo(coste):
    """Devuelve (coste mínimo, lista de celdas del camino óptimo)."""
    F, C = len(coste), len(coste[0])
    # 1) Rellenar la tabla igual que en coste_minimo_bu
    tabla = [[0] * C for _ in range(F)]
    tabla[0][0] = coste[0][0]
    for c in range(1, C):
        tabla[0][c] = tabla[0][c - 1] + coste[0][c]
    for f in range(1, F):
        tabla[f][0] = tabla[f - 1][0] + coste[f][0]
    for f in range(1, F):
        for c in range(1, C):
            tabla[f][c] = coste[f][c] + min(tabla[f - 1][c], tabla[f][c - 1])

    # 2) Retroceder desde el destino hasta el origen
    f, c = F - 1, C - 1
    camino = [(f, c)]
    while (f, c) != (0, 0):
        if f == 0:                                   # solo pudo venir de la izquierda
            c -= 1
        elif c == 0:                                 # solo pudo venir de arriba
            f -= 1
        elif tabla[f - 1][c] <= tabla[f][c - 1]:     # vino del predecesor más barato
            f -= 1
        else:
            c -= 1
        camino.append((f, c))
    camino.reverse()                                 # de origen a destino
    return tabla[F - 1][C - 1], camino


coste, ruta = camino_minimo(COSTE)
print(coste)   # 17
print(ruta)    # [(0, 0), (0, 1), (1, 1)... hasta (3, 4)] — una ruta óptima

La reconstrucción recorre a lo sumo F+C−1 celdas → Θ(F+C), despreciable frente al llenado de la tabla. Si hay empates, cualquiera de las opciones empatadas da un camino óptimo (puede haber varios).

Con esto tenemos el ciclo completo de la PD: recurrencia → tabla → valor óptimo → solución reconstruida. Este mismo patrón (con otras recurrencias) resolverá problemas de optimización combinatoria en el módulo 2 —allí sí veremos el problema de la mochila— y reaparecerá en los caminos mínimos sobre grafos generales del módulo 3, donde la ciudad dejará de ser una cuadrícula perfecta.

Errores Comunes y Consejos

  • Caso base ausente o inalcanzable. Si alguna rama de la recursión no desemboca en un caso base (por ejemplo, fib(n-2) con n=1 sin contemplar n<2), habrá RecursionError o resultados absurdos. Enumera los casos base antes de escribir la llamada recursiva.
  • Recursión sin avance. Llamarse con el mismo tamaño de problema (o mayor) no termina nunca. Comprueba que todo camino reduce la entrada.
  • Mutables como parámetro por defecto. def f(n, memo={}) comparte el diccionario entre todas las llamadas de todo el programa: un clásico de Python que produce resultados correctos aquí pero contaminación de estado en general. Usa memo=None + inicialización interna, o lru_cache.
  • Memoizar funciones con argumentos no hashables. lru_cache exige argumentos hashables: no puedes pasar listas o dicts. Solución: pasar índices/tuplas y dejar los datos grandes en una variable exterior (como hicimos con COSTE).
  • Aplicar PD sin subestructura óptima. Si la solución óptima global no se compone de óptimos de los subproblemas (p. ej., rutas con restricciones que acoplan decisiones lejanas), la recurrencia da resultados incorrectos por muy bien implementada que esté. Verifica la propiedad antes de programar.
  • Olvidar la pila en el análisis espacial. Una memoización top-down sobre una cadena de n subproblemas usa Θ(n) de pila; en Python, con n > ~1000, eso es un RecursionError. Si la profundidad escala con la entrada, pasa a bottom-up.
  • Consejo: escribe siempre primero la recurrencia en papel, con sus casos base, y valídala a mano con un ejemplo de 3×3. El 90 % de los errores de PD son recurrencias mal planteadas, no bugs de código.

Ejercicios

Ejercicio 1: Contar rutas del repartidor

Usando la misma cuadrícula F×C (movimientos solo sur/este), implementa numero_rutas(F, C) que devuelva de cuántas formas distintas puede el repartidor ir de (0,0) a (F−1,C−1). Hazlo bottom-up e indica su complejidad. Comprueba: para una cuadrícula 3×3 hay 6 rutas.

Ejercicio 2: Tramos de descanso

Un repartidor de Rutalia sube una escalera de n peldaños hasta el almacén y puede subir 1 o 2 peldaños por paso. Escribe (a) la recursión ingenua para contar de cuántas formas puede subir, (b) su versión memoizada y (c) razona qué complejidad tiene cada una. ¿A qué sucesión conocida corresponde?

Ejercicio 3: Reconstrucción con decisiones guardadas

Modifica camino_minimo para que, en lugar de retroceder comparando valores, guarde durante el llenado una tabla de_donde[f][c] con "arriba" o "izquierda", y reconstruya el camino con ella. ¿Qué coste espacial añade? ¿Qué ventaja tiene esta variante?

Soluciones

Solución 1

def numero_rutas(F, C):
    tabla = [[0] * C for _ in range(F)]
    for c in range(C):
        tabla[0][c] = 1          # primera fila: una sola forma (todo este)
    for f in range(F):
        tabla[f][0] = 1          # primera columna: una sola forma (todo sur)
    for f in range(1, F):
        for c in range(1, C):
            tabla[f][c] = tabla[f - 1][c] + tabla[f][c - 1]
    return tabla[F - 1][C - 1]

print(numero_rutas(3, 3))   # 6

Tiempo Θ(F·C), espacio Θ(F·C) (reducible a Θ(C) con una sola fila). Misma tabla que el coste mínimo cambiando min por suma y los casos base: la estructura del problema es idéntica.

Solución 2

(a) Recursión ingenua — para subir n peldaños, el último paso fue de 1 (quedaban n−1) o de 2 (quedaban n−2):

def formas(n):
    if n <= 1:
        return 1        # 0 peldaños: 1 forma (no moverse); 1 peldaño: 1 forma
    return formas(n - 1) + formas(n - 2)

(b) Memoizada:

from functools import lru_cache

@lru_cache(maxsize=None)
def formas_memo(n):
    if n <= 1:
        return 1
    return formas_memo(n - 1) + formas_memo(n - 2)

(c) La ingenua es exponencial, Θ(φⁿ) — es exactamente el árbol de Fibonacci con los índices desplazados: formas(n) = F(n+1). La memoizada resuelve n+1 subproblemas una vez cada uno → Θ(n) tiempo, Θ(n) espacio. Error común: poner como caso base solo n == 0 y dejar que n == 1 llame a formas(-1).

Solución 3

    # durante el llenado del interior:
    for f in range(1, F):
        for c in range(1, C):
            if tabla[f - 1][c] <= tabla[f][c - 1]:
                tabla[f][c] = coste[f][c] + tabla[f - 1][c]
                de_donde[f][c] = "arriba"
            else:
                tabla[f][c] = coste[f][c] + tabla[f][c - 1]
                de_donde[f][c] = "izquierda"
    # reconstrucción: seguir de_donde desde (F-1, C-1) hasta (0, 0)

(Las celdas de la primera fila llevan "izquierda" y las de la primera columna "arriba".) Añade Θ(F·C) de espacio para de_donde. Ventaja: la reconstrucción es directa y no depende de re-evaluar la ecuación (útil cuando la comparación de retroceso es cara o la recurrencia tiene muchas opciones); es la técnica estándar cuando hay más de dos decisiones posibles por subproblema.

Conclusión

Hemos recorrido el arco completo del diseño recursivo: una recursión correcta exige casos base, avance garantizado y combinación válida, y consume pila proporcional a su profundidad. Divide y vencerás explota la recursión cuando los subproblemas son independientes; cuando se solapan, la recursión ingenua explota exponencialmente (Fibonacci) y la solución es recordar: memoización si partimos de la recursión (top-down), programación dinámica bottom-up si preferimos llenar la tabla sin pila y con opción de optimizar el espacio. Con la cuadrícula de Rutalia hemos visto además que el valor óptimo no basta: la reconstrucción nos devuelve la ruta concreta que el repartidor debe seguir.

En todas estas soluciones han aparecido, sin nombrarlas apenas, las estructuras que las hacen posibles: diccionarios que memoizan en O(1), tablas, listas. En la próxima lección, Estructuras de Datos Avanzadas, las estudiaremos con rigor —heaps, tablas hash, union-find y tries—, porque elegir la estructura adecuada es, tan a menudo como elegir el algoritmo, lo que separa los segundos de las horas en Rutalia.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2026. Todos los derechos reservados