El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Recursió i Programació Dinàmica

Següent ►
►

A la lliçó anterior vam analitzar recurrències; en aquesta aprendrem a dissenyar els algorismes que les generen. La recursió —resoldre un problema en termes de versions més petites de si mateix— és una de les tècniques de disseny més potents que existeixen. Però té una patologia coneguda: quan els subproblemes es repeteixen, la recursió ingènua repeteix feina fins a tornar-se exponencial. La cura és la programació dinàmica (PD): recordar allò ja calculat, sigui sobre la marxa (memoització) o construint la solució de baix a dalt.

A Rutalia aquest tema és el pa de cada dia: la ciutat es modela com una quadrícula d'illes de cases i moltes preguntes operatives ("quin és el cost mínim per travessar la zona centre?", "de quantes maneres puc arribar al punt de lliurament?") tenen una estructura recursiva natural amb subproblemes que se solapen massivament.

Contingut

  1. Recursió ben feta: cas base, avanç i pila de crides
  2. Divideix i venceràs com a esquema general
  3. El problema: subproblemes solapats
  4. Memoització (top-down)
  5. Programació dinàmica bottom-up
  6. Reconstrucció de la solució

  1. Recursió ben feta: cas base, avanç i pila de crides

Una funció recursiva correcta necessita exactament tres ingredients:

  1. Cas(os) base: entrades tan petites que es resolen directament, sense recursió.
  2. Avanç garantit: cada crida recursiva es fa sobre una entrada estrictament més propera a un cas base.
  3. Combinació correcta: la solució del problema es construeix correctament a partir de les solucions dels subproblemes (aquí ajuda el "salt de fe recursiu": assumeix que la crida recursiva funciona i comprova que la combinació és correcta).

Exemple mínim amb Rutalia: sumar el pes total de la càrrega d'una furgoneta.

def pes_total(pesos):
    """Suma recursiva d'una llista de pesos (kg)."""
    if not pesos:                          # cas base: llista buida
        return 0.0
    return pesos[0] + pes_total(pesos[1:])  # avanç: la llista s'escurça en 1


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

(Sí, en producció això seria sum(pesos) o un bucle; el valor de l'exemple és veure els tres ingredients despullats. Nota, a més, que pesos[1:] copia la llista: aquesta versió didàctica costa Θ(n²) en temps; passar índexs en lloc de subllistes la deixa en Θ(n).)

La pila de crides

Cada crida pendent ocupa un marc (frame) a la pila de crides: paràmetres, variables locals i el punt de retorn. Això té dues conseqüències pràctiques:

  • Cost espacial: una recursió de profunditat d fa servir Θ(d) de memòria de pila a més del que reservi explícitament. pes_total sobre n elements té profunditat n → espai Θ(n), davant del Θ(1) del bucle equivalent.
  • Límit de Python: CPython talla les recursions a ~1000 nivells (RecursionError) per protegir la pila. Es pot ampliar amb sys.setrecursionlimit, però és un pedaç: si la profunditat creix amb n, per al milió de comandes de Rutalia caldrà una versió iterativa. Python tampoc no optimitza la recursió de cua (a diferència d'altres llenguatges), així que no hi comptis.
flowchart TD
    A["pes_total([2.5, 1.0, 4.2])"] --> B["pes_total([1.0, 4.2])"]
    B --> C["pes_total([4.2])"]
    C --> D["pes_total([]) → 0.0"]
    D -.->|"retorna 0.0"| C
    C -.->|"retorna 4.2"| B
    B -.->|"retorna 5.2"| A
    A -.->|"retorna 7.7"| FI["resultat: 7.7"]

  1. Divideix i venceràs com a esquema general

Divideix i venceràs (DiV) és el patró recursiu per excel·lència, en tres passos:

  1. Dividir el problema en subproblemes independents (idealment de mida n/b).
  2. Vèncer: resoldre cada subproblema recursivament (cas base quan és trivial).
  3. Combinar les solucions parcials en la solució global.

Exemple a Rutalia: trobar la comanda més pesant i la més lleugera de la furgoneta d'una sola passada, partint la llista per la meitat:

def min_max_pes(pesos, i, j):
    """Retorna (mínim, màxim) de pesos[i..j], per divideix i venceràs."""
    if i == j:                       # cas base: un element
        return pesos[i], pesos[i]
    m = (i + j) // 2                 # dividir
    min1, max1 = min_max_pes(pesos, i, m)      # vèncer (meitat esquerra)
    min2, max2 = min_max_pes(pesos, m + 1, j)  # vèncer (meitat dreta)
    return min(min1, min2), max(max1, max2)    # combinar


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

La seva recurrència és T(n) = 2T(n/2) + c, que pel teorema mestre de la lliçó 01-02 (cas 1) dona Θ(n). La profunditat de recursió és Θ(log n), així que la pila no és cap problema.

DiV funciona de meravella quan els subproblemes són independents (no comparteixen feina). Els grans algorismes d'ordenació i cerca que estudiarem al mòdul 4 (mergesort, quicksort, cerca binària) són DiV pur. El problema arriba quan els subproblemes no són independents.

  1. El problema: subproblemes solapats

L'exemple canònic és la successió de Fibonacci: F(0)=0, F(1)=1, F(n)=F(n−1)+F(n−2). La traducció directa a codi:

def fib(n):
    if n < 2:                       # casos base
        return n
    return fib(n - 1) + fib(n - 2)  # dues crides recursives

És correcta… i desastrosa. fib(50) triga minuts. Per què? Dibuixem l'arbre de crides:

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) es calcula 2 vegades, fib(2) tres vegades… i el nombre de repeticions creix exponencialment: T(n) = T(n−1) + T(n−2) + c, que creix com la mateixa Fibonacci → Θ(φⁿ) amb φ ≈ 1,618. Només hi ha n+1 subproblemes diferents, però l'arbre té de l'ordre de 2ⁿ nodes: estem resolent els mateixos subproblemes una vegada i una altra. Això és el solapament de subproblemes.

Quan un problema té (a) subproblemes solapats i (b) subestructura òptima (la solució òptima es compon de solucions òptimes dels subproblemes), és candidat a programació dinàmica. Hi ha dues estratègies.

  1. Memoització (top-down)

Memoització: mantenir la recursió tal qual, però guardar cada resultat la primera vegada que es calcula i reutilitzar-lo després. És la via de menor esforç des d'una recursió ja escrita.

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n < 2:
        return n
    if n not in memo:                  # ja ho hem calculat?
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

Cadascun dels n+1 subproblemes es calcula una sola vegada, amb feina constant fora de les crides: temps Θ(n), espai Θ(n) (memo + pila). D'exponencial a lineal guardant un diccionari.

Python porta la memoització de sèrie:

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)

Ara el problema de Rutalia. La zona centre és una quadrícula d'illes de cases; el repartidor hi entra per la cantonada nord-oest (0, 0) i ha d'arribar al punt de lliurament a la cantonada sud-est (F−1, C−1), movent-se només cap al sud o cap a l'est (carrers de sentit únic). Cada cel·la té un cost de travessar-la (minuts segons el trànsit, dades fictícies). Volem el cost mínim del trajecte.

Definició recursiva: sigui mc(f, c) el cost mínim per arribar a la cel·la (f, c). A (f, c) només s'hi arriba des de dalt o des de l'esquerra, així que:

  • mc(0, 0) = cost[0][0] (cas base)
  • mc(f, c) = cost[f][c] + min(mc(f−1, c), mc(f, c−1)), tractant les vores (primera fila/columna) amb un sol predecessor.

Aquesta equació —la relació de recurrència del problema— exhibeix la subestructura òptima: el millor camí fins a (f, c) acaba en el millor camí fins a una de les seves dues predecessores. I els subproblemes se solapen: a mc(2, 2) s'hi arriba preguntant per mc(1, 2) i mc(2, 1), i totes dues pregunten per mc(1, 1).

from functools import lru_cache

# Minuts per illa de cases (dades fictícies): 4 files x 5 columnes
COST = [
    [3, 2, 4, 1, 5],
    [1, 9, 3, 2, 2],
    [4, 1, 2, 8, 1],
    [2, 3, 1, 2, 3],
]

def cost_minim_td(cost):
    """Cost mínim de (0,0) a la cantonada inferior dreta. Top-down."""
    F, C = len(cost), len(cost[0])

    @lru_cache(maxsize=None)
    def mc(f, c):
        if f == 0 and c == 0:                 # cas base: origen
            return cost[0][0]
        if f < 0 or c < 0:                    # fora de la quadrícula
            return float("inf")               # cost infinit: mai no es tria
        return cost[f][c] + min(mc(f - 1, c), mc(f, c - 1))

    return mc(F - 1, C - 1)


print(cost_minim_td(COST))   # 17

Detalls per observar:

  • El truc de retornar float("inf") fora de la quadrícula simplifica les vores: min descarta aquestes branques tot sol.
  • Hi ha F·C subproblemes diferents i cadascun es resol una vegada amb feina O(1) → temps Θ(F·C), espai Θ(F·C). Sense memoització, l'arbre de crides seria exponencial (cada cel·la es bifurca en dues).
  • La profunditat de recursió és Θ(F+C); per a quadrícules molt grans pot fregar el límit de Python. Un motiu més per a l'estratègia següent.

  1. Programació dinàmica bottom-up

La versió bottom-up elimina la recursió: s'identifica l'ordre en què els subproblemes es necessiten (dels petits als grans) i s'omple una taula iterativament.

def cost_minim_bu(cost):
    """Cost mínim de (0,0) a la cantonada inferior dreta. Bottom-up."""
    F, C = len(cost), len(cost[0])
    taula = [[0] * C for _ in range(F)]    # taula[f][c] = mc(f, c)

    taula[0][0] = cost[0][0]
    for c in range(1, C):                  # primera fila: només s'hi arriba des de l'esquerra
        taula[0][c] = taula[0][c - 1] + cost[0][c]
    for f in range(1, F):                  # primera columna: només des de dalt
        taula[f][0] = taula[f - 1][0] + cost[f][0]

    for f in range(1, F):                  # resta: mínim dels dos predecessors
        for c in range(1, C):
            taula[f][c] = cost[f][c] + min(taula[f - 1][c], taula[f][c - 1])

    return taula[F - 1][C - 1]


print(cost_minim_bu(COST))   # 17

Mateix resultat, mateixa complexitat Θ(F·C), però sense pila de crides ni sobrecost de funció per cel·la. A més, com que cada fila només consulta l'anterior, l'espai es pot reduir a Θ(C) guardant una sola fila (optimització habitual quan no cal reconstruir el camí).

Comparativa de les tres aproximacions:

Enfocament Temps Espai Avantatges Inconvenients
Recursió ingènua exponencial Θ(F+C) pila immediata des de la recurrència inviable llevat de n minúscul
Memoització (top-down) Θ(F·C) Θ(F·C) + pila s'escriu en 2 minuts des de la recurrència; només calcula els subproblemes necessaris límit de pila; sobrecost per crida
PD bottom-up Θ(F·C) Θ(F·C), reduïble a Θ(C) sense pila; més ràpida en constants; espai optimitzable exigeix pensar l'ordre d'ompliment; calcula tots els subproblemes

Recepta general per plantejar una PD, aplicable a gairebé qualsevol problema:

  1. Defineix el subproblema amb precisió ("mc(f, c) = cost mínim per arribar a (f, c)").
  2. Escriu la recurrència que el relaciona amb subproblemes menors, amb els seus casos base.
  3. Compta: nre. de subproblemes × feina per subproblema = complexitat.
  4. Tria top-down (ràpid d'escriure) o bottom-up (ràpid d'executar) i, si escau, optimitza l'espai.

Una variant de recompte amb la mateixa estructura: de quantes maneres diferents pot el repartidor arribar al destí? Mateixa quadrícula, recurrència maneres(f, c) = maneres(f−1, c) + maneres(f, c−1) amb maneres(0, 0) = 1 (i 0 fora de la quadrícula). Només canvien el cas base i que els camins se sumen en lloc de prendre el mínim. Ho deixem com a exercici.

  1. Reconstrucció de la solució

Saber que el trajecte òptim costa 17 minuts està bé; el repartidor de Rutalia necessita, a més, el camí. Hi ha dues tècniques:

  • Guardar decisions: al costat de cada valor de la taula, anotar d'on venia (l'argmin).
  • Retrocedir comparant (la que farem servir): partir de la cel·la final i, a cada pas, moure's a la predecessora el valor de la qual a la taula quadra amb l'equació. No requereix memòria extra.
def cami_minim(cost):
    """Retorna (cost mínim, llista de cel·les del camí òptim)."""
    F, C = len(cost), len(cost[0])
    # 1) Omplir la taula igual que a cost_minim_bu
    taula = [[0] * C for _ in range(F)]
    taula[0][0] = cost[0][0]
    for c in range(1, C):
        taula[0][c] = taula[0][c - 1] + cost[0][c]
    for f in range(1, F):
        taula[f][0] = taula[f - 1][0] + cost[f][0]
    for f in range(1, F):
        for c in range(1, C):
            taula[f][c] = cost[f][c] + min(taula[f - 1][c], taula[f][c - 1])

    # 2) Retrocedir des del destí fins a l'origen
    f, c = F - 1, C - 1
    cami = [(f, c)]
    while (f, c) != (0, 0):
        if f == 0:                                   # només podia venir de l'esquerra
            c -= 1
        elif c == 0:                                 # només podia venir de dalt
            f -= 1
        elif taula[f - 1][c] <= taula[f][c - 1]:     # venia del predecessor més barat
            f -= 1
        else:
            c -= 1
        cami.append((f, c))
    cami.reverse()                                   # d'origen a destí
    return taula[F - 1][C - 1], cami


cost, ruta = cami_minim(COST)
print(cost)   # 17
print(ruta)   # [(0, 0), (0, 1), (1, 1)... fins a (3, 4)] — una ruta òptima

La reconstrucció recorre com a molt F+C−1 cel·les → Θ(F+C), menyspreable davant de l'ompliment de la taula. Si hi ha empats, qualsevol de les opcions empatades dona un camí òptim (n'hi pot haver diversos).

Amb això tenim el cicle complet de la PD: recurrència → taula → valor òptim → solució reconstruïda. Aquest mateix patró (amb altres recurrències) resoldrà problemes d'optimització combinatòria al mòdul 2 —allà sí que veurem el problema de la motxilla— i reapareixerà als camins mínims sobre grafs generals del mòdul 3, on la ciutat deixarà de ser una quadrícula perfecta.

Errors Comuns i Consells

  • Cas base absent o inabastable. Si alguna branca de la recursió no desemboca en un cas base (per exemple, fib(n-2) amb n=1 sense preveure n<2), hi haurà RecursionError o resultats absurds. Enumera els casos base abans d'escriure la crida recursiva.
  • Recursió sense avanç. Cridar-se amb la mateixa mida de problema (o més gran) no acaba mai. Comprova que tot camí redueix l'entrada.
  • Mutables com a paràmetre per defecte. def f(n, memo={}) comparteix el diccionari entre totes les crides de tot el programa: un clàssic de Python que aquí produeix resultats correctes però contaminació d'estat en general. Fes servir memo=None + inicialització interna, o lru_cache.
  • Memoitzar funcions amb arguments no hashables. lru_cache exigeix arguments hashables: no pots passar llistes ni dicts. Solució: passar índexs/tuples i deixar les dades grans en una variable exterior (com hem fet amb COST).
  • Aplicar PD sense subestructura òptima. Si la solució òptima global no es compon d'òptims dels subproblemes (p. ex., rutes amb restriccions que acoblen decisions llunyanes), la recurrència dona resultats incorrectes per molt ben implementada que estigui. Verifica la propietat abans de programar.
  • Oblidar la pila en l'anàlisi espacial. Una memoització top-down sobre una cadena de n subproblemes fa servir Θ(n) de pila; en Python, amb n > ~1000, això és un RecursionError. Si la profunditat escala amb l'entrada, passa a bottom-up.
  • Consell: escriu sempre primer la recurrència en paper, amb els seus casos base, i valida-la a mà amb un exemple de 3×3. El 90 % dels errors de PD són recurrències mal plantejades, no bugs de codi.

Exercicis

Exercici 1: Comptar rutes del repartidor

Fent servir la mateixa quadrícula F×C (moviments només sud/est), implementa nombre_rutes(F, C) que retorni de quantes maneres diferents pot anar el repartidor de (0,0) a (F−1,C−1). Fes-ho bottom-up i indica'n la complexitat. Comprova: per a una quadrícula 3×3 hi ha 6 rutes.

Exercici 2: Trams de descans

Un repartidor de Rutalia puja una escala de n graons fins al magatzem i pot pujar 1 o 2 graons per pas. Escriu (a) la recursió ingènua per comptar de quantes maneres pot pujar, (b) la seva versió memoitzada i (c) raona quina complexitat té cadascuna. A quina successió coneguda correspon?

Exercici 3: Reconstrucció amb decisions guardades

Modifica cami_minim perquè, en lloc de retrocedir comparant valors, guardi durant l'ompliment una taula d_on[f][c] amb "amunt" o "esquerra", i reconstrueixi el camí amb ella. Quin cost espacial afegeix? Quin avantatge té aquesta variant?

Solucions

Solució 1

def nombre_rutes(F, C):
    taula = [[0] * C for _ in range(F)]
    for c in range(C):
        taula[0][c] = 1          # primera fila: una sola manera (tot est)
    for f in range(F):
        taula[f][0] = 1          # primera columna: una sola manera (tot sud)
    for f in range(1, F):
        for c in range(1, C):
            taula[f][c] = taula[f - 1][c] + taula[f][c - 1]
    return taula[F - 1][C - 1]

print(nombre_rutes(3, 3))   # 6

Temps Θ(F·C), espai Θ(F·C) (reduïble a Θ(C) amb una sola fila). Mateixa taula que el cost mínim canviant min per la suma i els casos base: l'estructura del problema és idèntica.

Solució 2

(a) Recursió ingènua — per pujar n graons, l'últim pas va ser d'1 (en quedaven n−1) o de 2 (en quedaven n−2):

def maneres(n):
    if n <= 1:
        return 1        # 0 graons: 1 manera (no moure's); 1 graó: 1 manera
    return maneres(n - 1) + maneres(n - 2)

(b) Memoitzada:

from functools import lru_cache

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

(c) La ingènua és exponencial, Θ(φⁿ) — és exactament l'arbre de Fibonacci amb els índexs desplaçats: maneres(n) = F(n+1). La memoitzada resol n+1 subproblemes una vegada cadascun → Θ(n) temps, Θ(n) espai. Error comú: posar com a cas base només n == 0 i deixar que n == 1 cridi maneres(-1).

Solució 3

    # durant l'ompliment de l'interior:
    for f in range(1, F):
        for c in range(1, C):
            if taula[f - 1][c] <= taula[f][c - 1]:
                taula[f][c] = cost[f][c] + taula[f - 1][c]
                d_on[f][c] = "amunt"
            else:
                taula[f][c] = cost[f][c] + taula[f][c - 1]
                d_on[f][c] = "esquerra"
    # reconstrucció: seguir d_on des de (F-1, C-1) fins a (0, 0)

(Les cel·les de la primera fila porten "esquerra" i les de la primera columna, "amunt".) Afegeix Θ(F·C) d'espai per a d_on. Avantatge: la reconstrucció és directa i no depèn de reavaluar l'equació (útil quan la comparació de retrocés és cara o la recurrència té moltes opcions); és la tècnica estàndard quan hi ha més de dues decisions possibles per subproblema.

Conclusió

Hem recorregut l'arc complet del disseny recursiu: una recursió correcta exigeix casos base, avanç garantit i combinació vàlida, i consumeix pila proporcional a la seva profunditat. Divideix i venceràs explota la recursió quan els subproblemes són independents; quan se solapen, la recursió ingènua explota exponencialment (Fibonacci) i la solució és recordar: memoització si partim de la recursió (top-down), programació dinàmica bottom-up si preferim omplir la taula sense pila i amb l'opció d'optimitzar l'espai. Amb la quadrícula de Rutalia hem vist, a més, que el valor òptim no basta: la reconstrucció ens retorna la ruta concreta que el repartidor ha de seguir.

En totes aquestes solucions han aparegut, gairebé sense anomenar-les, les estructures que les fan possibles: diccionaris que memoitzen en O(1), taules, llistes. A la propera lliçó, Estructures de Dades Avançades, les estudiarem amb rigor —heaps, taules de hash, union-find i tries—, perquè triar l'estructura adequada és, tan sovint com triar l'algorisme, allò que separa els segons de les hores a Rutalia.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats