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

Tipus d'Algorismes

Següent ►
►

A la lliçó anterior vam definir què és un algorisme i en vam escriure el primer per a RutaBus. Ara farem un pas enrere per contemplar el panorama complet: els algorismes es poden classificar segons diverses dimensions —com s'estructuren, per a què serveixen, si el seu comportament és predictible i si garanteixen la solució exacta—. Conèixer aquestes classificacions és important perquè et dona un mapa mental: quan t'enfrontis a un problema nou a RutaBus (o a la teva feina), sabràs a quina "família" encaixa i quin tipus d'eina cal buscar. A més, en aquesta lliçó aprendràs en profunditat la recursivitat, un concepte transversal que reapareixerà en gairebé tots els mòduls del curs.

Contingut

  1. Les dimensions de classificació
  2. Per enfocament: iteratius vs recursius
  3. La recursivitat en detall: cas base i cas recursiu
  4. Per propòsit: cerca, ordenació, grafs i més
  5. Deterministes vs no deterministes
  6. Exactes vs heurístics/aproximats
  7. Avançament: estratègies de disseny del Mòdul 3

Les dimensions de classificació

Un mateix algorisme es pot classificar alhora segons diversos criteris independents, igual que una parada de RutaBus es pot classificar alhora per zona, per accessibilitat i per línies que hi passen. Les quatre dimensions que veurem són:

Dimensió Pregunta que respon Valors típics
Enfocament Com estructura la repetició? Iteratiu, recursiu
Propòsit Quin problema resol? Cerca, ordenació, grafs, compressió...
Determinisme Es comporta sempre igual amb la mateixa entrada? Determinista, no determinista
Exactitud Garanteix la solució òptima/correcta? Exacte, heurístic/aproximat

Per exemple, l'algorisme parada_mes_propera de la lliçó anterior és iteratiu (fa servir un bucle), de cerca (busca un mínim), determinista (amb la mateixa entrada sempre dona la mateixa sortida) i exacte (garanteix trobar la parada realment més propera).

Per enfocament: iteratius vs recursius

La primera dimensió distingeix com repeteix feina un algorisme.

  • Un algorisme iteratiu repeteix passos mitjançant bucles (for, while), mantenint l'estat en variables que es van actualitzant.
  • Un algorisme recursiu resol el problema fent que una funció es cridi a si mateixa amb una versió més petita del problema, fins a arribar a un cas tan simple que es resol directament.

Vegem el mateix problema de RutaBus resolt amb tots dos enfocaments: comptar quantes parades té una línia, representada com a llista de noms.

linia_l1 = ["Plaça Major", "Gran Via", "Hospital Central", "Estació Nord"]

# Enfocament ITERATIU: un bucle acumula el resultat en una variable
def compta_parades_iteratiu(parades):
    comptador = 0
    for _ in parades:      # per cada parada...
        comptador += 1     # ...sumem 1 a l'acumulador
    return comptador

# Enfocament RECURSIU: la funció es recolza en si mateixa
def compta_parades_recursiu(parades):
    if not parades:                                  # cas base: llista buida
        return 0
    return 1 + compta_parades_recursiu(parades[1:])  # cas recursiu

print(compta_parades_iteratiu(linia_l1))  # 4
print(compta_parades_recursiu(linia_l1))  # 4

La versió recursiva es llegeix així: "el nombre de parades d'una llista és 1 (la primera) més el nombre de parades de la resta de la llista; i una llista buida té 0 parades". És una definició del problema en termes de si mateix, però amb un problema cada cop més petit.

Criteri Iteratiu Recursiu
Mecanisme de repetició Bucles (for, while) Crides a la mateixa funció
Estat Variables actualitzades a cada volta Paràmetres de cada crida
Llegibilitat Millor en problemes lineals simples Millor en problemes amb estructura niada (arbres, divisions)
Consum de memòria Constant en general Una entrada a la pila per cada crida pendent
Risc típic Bucle infinit per una condició mal escrita RecursionError per oblidar o no assolir el cas base

Cap enfocament no és "millor" en abstracte: tot algorisme recursiu es pot reescriure de manera iterativa i viceversa. La recursió brilla quan el problema és naturalment autosimilar (explorar totes les combinacions de transbordaments, recórrer estructures jeràrquiques); la iteració sol ser preferible per a recorreguts lineals senzills.

La recursivitat en detall: cas base i cas recursiu

Tota funció recursiva ben construïda té exactament dos ingredients:

  1. Cas base: la situació tan simple que es resol sense recursió. És la condició de parada. Sense ell (o si mai no s'hi arriba), la funció es cridaria a si mateixa indefinidament.
  2. Cas recursiu: la funció es crida a si mateixa amb una entrada estrictament més petita o més propera al cas base, i combina aquest resultat parcial amb una mica de feina pròpia.
flowchart TD
    A[Crida amb el problema P] --> B{P és el<br/>cas base?}
    B -- Sí --> C[/Retornar solució directa/]
    B -- No --> D[Reduir P a un problema menor P']
    D --> E[Crida recursiva amb P']
    E --> F[Combinar el resultat de P'<br/>amb la feina pròpia]
    F --> G[/Retornar resultat/]

Apliquem-ho a un problema real de RutaBus: la línia L2 té les seves parades i volem saber quantes parades queden fins al final del trajecte des de la parada on és l'usuari.

linia_l2 = ["Estació Nord", "Avinguda del Port", "Plaça Major",
            "Universitat", "Terminal Sud"]

def parades_restants(linia, parada_actual):
    """Compta les parades que queden DESPRÉS de parada_actual.

    Cas base:      la parada actual és la primera de la llista restant
                   -> en queden len - 1... resolt comptant recursivament.
    """
    # Cas base: la parada actual és la primera de la llista
    if linia[0] == parada_actual:
        return len(linia) - 1
    # Cas recursiu: descartem la primera parada i cerquem a la resta
    return parades_restants(linia[1:], parada_actual)

print(parades_restants(linia_l2, "Plaça Major"))  # 2 (Universitat i Terminal Sud)

Seguim la traça de l'execució per entendre què passa per dins:

parades_restants(["Estació Nord", "Avinguda del Port", "Plaça Major", "Universitat", "Terminal Sud"], "Plaça Major")
  → "Estació Nord" ≠ "Plaça Major" → crida recursiva amb la llista sense la primera
  parades_restants(["Avinguda del Port", "Plaça Major", "Universitat", "Terminal Sud"], "Plaça Major")
    → "Avinguda del Port" ≠ "Plaça Major" → crida recursiva
    parades_restants(["Plaça Major", "Universitat", "Terminal Sud"], "Plaça Major")
      → CAS BASE: retorna len - 1 = 2
    ← 2
  ← 2
← 2

Cada crida pendent queda "en espera" a la pila de crides fins que la crida interior retorna el seu resultat. Això explica el cost en memòria de la recursió: amb una línia de 1.000 parades hi podria haver fins a 1.000 crides apilades (Python, per defecte, talla al voltant de les 1.000 amb RecursionError).

Observa també un defecte deliberat de l'exemple: si parada_actual no és a la línia, la llista acabarà buida i linia[0] llançarà IndexError. Un cas base addicional ho arregla:

def parades_restants_robust(linia, parada_actual):
    if not linia:                       # cas base 2: parada no trobada
        return None
    if linia[0] == parada_actual:       # cas base 1: parada trobada
        return len(linia) - 1
    return parades_restants_robust(linia[1:], parada_actual)

Regla d'or: enumera primer els casos base (tots), després escriu el cas recursiu, i comprova que cada crida recursiva acosta l'entrada a algun cas base.

Per propòsit: cerca, ordenació, grafs i més

La segona dimensió classifica els algorismes segons el tipus de problema que resolen. És la classificació més pràctica en el dia a dia, perquè els problemes reals "s'assemblen" a alguna d'aquestes famílies:

Família Què resol Exemple a RutaBus On s'aprofundeix
Cerca Localitzar un element (o el millor) en una col·lecció Trobar la parada "Plaça Major" al llistat; cerca binària Mòdul 4 (04-01)
Ordenació Disposar elements segons un criteri Ordenar els propers autobusos per hora d'arribada Mòdul 4 (04-02 a 04-04)
Grafs Treballar amb xarxes de nodes i connexions Calcular la ruta més ràpida entre dues parades de la xarxa Mòdul 4 (04-05, 04-06)
Compressió Reduir la mida de les dades preservant la informació Comprimir l'històric de posicions GPS dels autobusos (fora de l'abast del curs)
Criptografia Protegir informació Xifrar les credencials dels usuaris de l'app (fora de l'abast del curs)
Optimització numèrica Minimitzar/maximitzar una funció Ajustar freqüències de pas per minimitzar esperes Es toca als Mòduls 3 i 5

Un petit exemple de cadascuna de les dues famílies més freqüents, en versió senzilla (les versions eficients arriben al Mòdul 4):

# CERCA (lineal): a quina posició de la línia és una parada?
def cerca_parada(linia, nom):
    for i, parada in enumerate(linia):
        if parada == nom:
            return i          # trobada: en retornem l'índex
    return -1                 # no trobada

# ORDENACIÓ (delegada a Python): propers busos per hora d'arribada
arribades = [("L3", "10:42"), ("L1", "10:35"), ("L2", "10:39")]
per_hora = sorted(arribades, key=lambda bus: bus[1])
print(per_hora)  # [('L1', '10:35'), ('L2', '10:39'), ('L3', '10:42')]

A cerca_parada, enumerate ens dona alhora l'índex i i el valor parada; retornem l'índex tan bon punt hi ha coincidència (no cal continuar mirant). A l'ordenació fem servir el sorted de Python amb una funció key que indica el criteri (l'hora, posició 1 de cada tupla) — al Mòdul 4 obrirem aquesta "caixa negra" i construirem els nostres propis algorismes d'ordenació.

Deterministes vs no deterministes

Un algorisme és determinista si, davant la mateixa entrada, executa sempre exactament els mateixos passos i produeix sempre la mateixa sortida. Tots els que hem escrit fins ara ho són, i és la propietat desitjable per defecte: fa el programari predictible i fàcil de provar.

Un algorisme no determinista (a la pràctica, aleatoritzat) incorpora decisions a l'atzar, de manera que dues execucions amb la mateixa entrada poden diferir en els passos intermedis o fins i tot en la sortida. Lluny de ser un defecte, l'aleatorietat de vegades és una eina valuosa:

import random

def parada_per_enquesta(parades):
    """RutaBus vol enquestar usuaris en una parada triada a l'atzar
    cada dia, perquè la mostra no estigui esbiaixada cap a una zona."""
    return random.choice(parades)

# Dues execucions amb la MATEIXA entrada poden donar resultats diferents:
print(parada_per_enquesta(["Plaça Major", "Estació Nord", "Terminal Sud"]))
Aspecte Determinista No determinista (aleatoritzat)
Mateixa entrada → Mateixa sortida sempre Sortida (o camí) potencialment diferent
Proves / depuració Senzilles i reproduïbles Requereixen fixar la llavor (random.seed)
Usos típics La immensa majoria del programari Mostreig, simulació, evitar pitjors casos patològics

Un apunt que reprendrem: alguns algorismes famosos fan servir l'aleatorietat per millorar el seu comportament típic — per exemple, Quick Sort (Mòdul 4) sol triar el seu "pivot" a l'atzar. La sortida continua sent correcta i la mateixa; el que varia és el camí.

Exactes vs heurístics/aproximats

L'última dimensió respon a: l'algorisme garanteix la millor solució possible?

  • Un algorisme exacte garanteix la solució correcta o òptima. parada_mes_propera és exacte: la parada retornada és realment la més propera.
  • Un algorisme heurístic o aproximat renuncia a aquesta garantia a canvi de rapidesa o simplicitat: dona una solució raonablement bona gairebé sempre, però pot equivocar-se o quedar lluny de l'òptim.

Per què renunciar a l'exactitud? Perquè hi ha problemes on trobar l'òptim exacte és inassumiblement costós. Exemple clàssic adaptat a RutaBus: un supervisor ha de visitar 20 parades en un sol recorregut, minimitzant la distància total (el famós "problema del viatjant"). El nombre de recorreguts possibles és astronòmic, així que una heurística raonable és: "des de cada parada, ves sempre a la més propera no visitada".

def recorregut_supervisor(parades, inici):
    """Heurística del 'veí més proper': recorregut curt, no necessàriament òptim."""
    pendents = [p for p in parades if p["nom"] != inici["nom"]]
    recorregut = [inici]
    actual = inici
    while pendents:
        # Triem la parada pendent més propera a l'actual
        seguent = min(
            pendents,
            key=lambda p: distancia(actual["x"], actual["y"], p["x"], p["y"])
        )
        recorregut.append(seguent)
        pendents.remove(seguent)
        actual = seguent
    return recorregut

Aquesta heurística produeix recorreguts bons a la pràctica, però es pot demostrar que de vegades retorna recorreguts clarament pitjors que l'òptim. Aquest és el tracte: velocitat a canvi de garanties.

Aspecte Exacte Heurístic/aproximat
Garantia sobre la solució Òptima/correcta sempre "Bona", sense garantia (o amb fita d'error)
Cost computacional Pot ser prohibitiu en problemes durs Habitualment baix
Quan triar-lo Sempre que el cost sigui assumible Problemes intractables o amb límit de temps estricte

Matís de vocabulari: se sol anomenar aproximat el que ofereix una garantia matemàtica de proximitat a l'òptim (p. ex., "com a màxim el doble de l'òptim") i heurístic el que no n'ofereix cap, només bon comportament empíric.

Avançament: estratègies de disseny del Mòdul 3

A més de les dimensions anteriors, els algorismes se solen agrupar per l'estratègia de disseny amb què es construeixen. Aquí només les anomenem — cadascuna té la seva pròpia lliçó al Mòdul 3:

  • Divideix i venceràs (03-01): partir el problema en subproblemes més petits, resoldre'ls i combinar-ne les solucions.
  • Greedy (voraços) (03-02): construir la solució prenent a cada pas la decisió localment millor — l'heurística del supervisor que acabem de veure és d'esperit greedy.
  • Programació dinàmica (03-03): resoldre subproblemes que es repeteixen desant-ne els resultats per no recalcular-los.
  • Backtracking (03-04): explorar sistemàticament totes les opcions, reculant quan un camí no porta a cap solució.

Errors Comuns i Consells

  • Oblidar el cas base (o algun d'ells) en una funció recursiva. El símptoma en Python és RecursionError: maximum recursion depth exceeded. Consell: escriu els casos base abans que el cas recursiu, i pregunta't "quines entrades NO haurien de provocar una altra crida?".
  • Crida recursiva que no redueix el problema. parades_restants(linia, parada_actual) cridant-se amb la mateixa llista no acaba mai. Verifica que cada crida recursiva passa una entrada estrictament més propera al cas base.
  • Fer servir recursió per a recorreguts lineals llargs en Python. Amb llistes de milers d'elements exhauriràs la pila. Per a recorreguts simples, prefereix la iteració; reserva la recursió per a problemes amb estructura ramificada.
  • Creure que "no determinista" vol dir "incorrecte". Un algorisme aleatoritzat ben dissenyat és tan legítim com un de determinista; només exigeix disciplina extra en les proves (fixar random.seed(42) per reproduir-les).
  • Fer servir una heurística quan el problema admet solució exacta barata. Abans d'acceptar solucions "aproximades", comprova si existeix un algorisme exacte eficient per al teu problema (moltes vegades existeix i és al Mòdul 4).
  • Classificar el problema massa tard. Consell professional: abans de programar, pregunta "això és cerca, ordenació, grafs...?". Identificar la família et porta directe a solucions conegudes en lloc de reinventar-les.

Exercicis

Exercici 1

Classifica la funció recorregut_supervisor d'aquesta lliçó segons les quatre dimensions (enfocament, propòsit, determinisme, exactitud) i justifica cada resposta en una frase.

Exercici 2

Escriu una funció recursiva hi_ha_parada_recursiva(linia, nom) que retorni True si la parada nom és a la llista linia i False en cas contrari. Identifica explícitament en comentaris el cas base (o casos base) i el cas recursiu. Després, escriu la versió iterativa i compara: quina et sembla més clara per a aquest problema?

Exercici 3

La funció recursiva següent pretén sumar els minuts d'espera d'una llista, però té dos errors. Troba'ls i corregeix-los:

def suma_esperes(esperes):
    if len(esperes) == 1:
        return esperes[0]
    return esperes[0] + suma_esperes(esperes)

Solucions

Solució 1:

  • Enfocament: iteratiu — repeteix mitjançant un bucle while, sense cridar-se a si mateixa.
  • Propòsit: optimització (busca un recorregut curt), recolzant-se en operacions de cerca del mínim.
  • Determinisme: determinista — amb les mateixes parades i el mateix inici produeix sempre el mateix recorregut (el min de Python resol els empats sempre igual: guanya el primer).
  • Exactitud: heurístic — no garanteix el recorregut de distància mínima, només un de raonablement curt.

Solució 2:

# Versió recursiva
def hi_ha_parada_recursiva(linia, nom):
    if not linia:                 # CAS BASE 1: llista buida -> no hi és
        return False
    if linia[0] == nom:           # CAS BASE 2: la primera coincideix -> hi és
        return True
    # CAS RECURSIU: cercar a la resta de la llista (problema més petit)
    return hi_ha_parada_recursiva(linia[1:], nom)

# Versió iterativa
def hi_ha_parada_iterativa(linia, nom):
    for parada in linia:
        if parada == nom:
            return True
    return False

Per a un recorregut lineal com aquest, la versió iterativa sol considerar-se més clara i a més no consumeix pila. La recursiva és un bon exercici, però en producció (i en Python) la iterativa és l'elecció natural. Fixa't que calen dos casos base: un d'èxit i un altre de fracàs.

Solució 3:

Errors:

  1. La crida recursiva no redueix el problema: suma_esperes(esperes) es crida amb la mateixa llista, provocant recursió infinita. Ha de ser suma_esperes(esperes[1:]).
  2. Falta el cas base de llista buida: amb esperes = [], la condició len(esperes) == 1 és falsa i esperes[0] llança IndexError. El més net és que el cas base sigui la llista buida (i així, a més, el cas len == 1 queda cobert pel cas recursiu).
def suma_esperes(esperes):
    if not esperes:                          # cas base: llista buida suma 0
        return 0
    return esperes[0] + suma_esperes(esperes[1:])  # cas recursiu: redueix la llista

print(suma_esperes([5, 3, 8]))  # 16
print(suma_esperes([]))         # 0

Conclusió

En aquesta lliçó hem construït un mapa dels tipus d'algorismes segons quatre dimensions independents: per enfocament (iteratius davant de recursius, amb la recursivitat explicada a fons mitjançant cas base i cas recursiu), per propòsit (cerca, ordenació, grafs, compressió...), per determinisme (predictibles davant d'aleatoritzats) i per exactitud (exactes davant d'heurístics/aproximats). També hem entrevist les quatre grans estratègies de disseny que desenvoluparem al Mòdul 3. Amb aquest mapa ja sabem quines famílies d'algorismes existeixen; la pregunta natural següent és com comparar dos algorismes de la mateixa família que resolen el mateix problema. Per a això necessitem un llenguatge comú i independent de la màquina: la notació asimptòtica, protagonista de la propera lliçó.

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