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

Recursivitat

Següent ►
►

La lliçó anterior va acabar amb dos deutes: la cerca binària tenia una versió «més elegant» que no podíem escriure, i el mergesort necessitava ordenar dues meitats que són, al seu torn, llistes per ordenar. Totes dues demanen el mateix, i és el que aprendràs aquí: una funció que es crida a si mateixa.

La recursivitat desconcerta la primera vegada perquè sembla un truc circular, i no ho és: és una manera diferent de descompondre problemes, complementària de la descomposició en funcions de 04-04. En comptes de partir el problema en subproblemes diferents, el parteixes en versions més petites del mateix problema fins a arribar a un cas tan simple que es resol sense pensar. En aquesta lliçó l'entendràs, la traçaràs, descobriràs per què en Python convé desconfiar-ne, i la faràs servir en els tres llocs on guanya de carrer.

Contingut

  1. La idea: caixes dins de caixes
  2. Les dues peces obligatòries
  3. La pila de crides i el RecursionError
  4. Exemples progressius amb la seva traça
  5. L'arbre de crides: factorial i Fibonacci
  6. Recursivitat davant d'iteració
  7. El cost ocult de la recursivitat ingènua
  8. Memoïtzació: recordar el que ja s'ha calculat
  9. On la recursivitat sí que guanya
  10. Cerca binària recursiva i ordenació per barreja
  11. TascaFàcil v0.14: dies d'un desglossament imbricat
  12. Errors comuns i consells
  13. Exercicis
  14. Conclusió

  1. La idea: caixes dins de caixes

Imagina't que al magatzem d'Estudi Alba et demanen comptar quants fulls hi ha, i el magatzem conté caixes, algunes de les quals contenen altres caixes. No necessites un procediment diferent per a cada nivell de profunditat. Necessites una sola regla:

Per comptar els fulls d'una caixa: si a dins només hi ha fulls, compta'ls. Si a dins hi ha altres caixes, compta els fulls de cadascuna i suma els resultats.

Fixa't en el que acabes de fer: has definit «comptar els fulls d'una caixa» en termes d'ell mateix, aplicat a una cosa més petita. I funciona perquè les caixes no són infinites: tard o d'hora arribes a una que només conté fulls i allà t'atures. El mateix passa amb les nines russes, amb les carpetes dins de carpetes del disc dur o amb la definició d'«avantpassat»: els teus pares, i els avantpassats dels teus pares. Això és tota la recursivitat: una funció recursiva es crida a si mateixa amb una versió més petita del problema, confiant que aquesta crida li retornarà la resposta correcta.

  1. Les dues peces obligatòries

Tota funció recursiva té exactament dues parts, i cap de les dues no pot faltar:

Peça Què és Què passa si falta
Cas base La situació tan simple que es resol sense recursivitat La funció no s'atura mai: RecursionError
Cas recursiu La crida a si mateixa amb un problema més petit No és recursivitat: és una funció normal 
def compte_enrere(n):
    """Imprimeix el compte enrere des de n fins a 1 i despres Ja."""
    if n == 0:                    # CAS BASE: no queda res per comptar
        print("Ja!")
        return
    print(n)                      # feina d'aquest nivell
    compte_enrere(n - 1)          # CAS RECURSIU: el mateix problema, mes petit

En escriure una funció recursiva, fes-te sempre les tres preguntes en aquest ordre: quin és el cas més simple que sé resoldre sense pensar? (aquest és el base), com redueixo el problema cap a aquest cas? (aquesta és la crida recursiva) i què faig amb el que em retorni? (aquesta és la feina d'aquest nivell). I hi ha un requisit que va més enllà de tenir les dues peces: el cas recursiu s'ha d'acostar al base. compte_enrere(n - 1) s'acosta a zero; compte_enrere(n) no s'acosta a res i es penja igual que si no hi hagués cas base.

  1. La pila de crides i el RecursionError

A 04-01 vas veure que quan una funció en crida una altra, la primera espera que la segona acabi. Python desa cada crida pendent a la pila de crides, amb les seves variables i el punt exacte on cal tornar. La recursivitat apila crides de la mateixa funció:

graph TD
    A["compte_enrere(3) imprimeix 3"] --> B["compte_enrere(2) imprimeix 2"]
    B --> C["compte_enrere(1) imprimeix 1"]
    C --> D["compte_enrere(0) imprimeix Ja i torna"]
    D -.->|"es desapila fins al principi"| A

La pila creix fins al cas base i després es desapila en ordre invers. Això té una conseqüència pràctica de primer ordre: cada crida pendent ocupa memòria. Python limita la profunditat a unes 1.000 crides i, si se supera, avorta amb RecursionError: maximum recursion depth exceeded.

import sys
def sense_base(n):
    return sense_base(n - 1)      # no s'atura mai: RecursionError en menys d'un segon
print(sys.getrecursionlimit())    # 1000 en la majoria d'installacions
sys.setrecursionlimit(3000)       # es pot pujar... pero gairebe mai es la solucio

Aquest RecursionError és, en realitat, una bona notícia: Python t'avisa d'una fallada lògica —falta el cas base o no t'hi acostes— abans d'esgotar la memòria. Pujar el límit existeix, però és gairebé sempre la resposta equivocada: si la teva recursivitat necessita més de mil nivells, el que necessites és un bucle.

  1. Exemples progressius amb la seva traça

Factorial. El factorial de n és el producte dels enters d'1 a n, i la seva definició matemàtica ja és recursiva: n! = n × (n-1)!, amb 0! = 1.

def factorial(n):
    """Retorna el factorial de n (producte d'1 a n)."""
    if n <= 1:                    # cas base: 0! i 1! valen 1
        return 1
    return n * factorial(n - 1)   # cas recursiu

Traça de factorial(4); les primeres columnes són l'anada, apilant crides, i l'última és la tornada, quan cada nivell rep el seu resultat i el multiplica:

Nivell Crida (anada) Espera… Rep Retorna
1 factorial(4) factorial(3) 6 4 * 6 = 24
2 factorial(3) factorial(2) 2 3 * 2 = 6
3 factorial(2) factorial(1) 1 2 * 1 = 2
4 factorial(1) ningú: cas base — 1

Llegeix la taula de baix a dalt a l'última columna i veuràs com es construeix el resultat: 1, 2, 6, 24. Res no es calcula a l'anada; tota la feina real passa en tornar. El mateix esquema serveix sobre col·leccions: la suma d'una llista és el seu primer element més la suma de la resta, i una cadena invertida és la resta invertida més el seu primer caràcter.

def suma(valors):
    """Retorna la suma dels nombres de la llista."""
    if not valors:                            # cas base: llista buida
        return 0
    return valors[0] + suma(valors[1:])       # primer + suma de la resta

def invertir(text):
    """Retorna el text del reves."""
    if len(text) <= 1:                        # cas base: 0 o 1 caracter
        return text
    return invertir(text[1:]) + text[0]       # la resta invertida + el primer

valors[1:] és el tall de 05-01: «tots menys el primer». Cada crida rep una col·lecció un element més curta, així que s'acosta al cas base. Amb [3, 5, 2] surt 3 + (5 + (2 + 0)), és a dir, 10; i amb "Alba", invertir("lba") + "A" → ("ab" + "l") + "A" → "ablA". En producció escriuries sum(valors) i text[::-1]; això és per veure la mecànica.

  1. L'arbre de crides: factorial i Fibonacci

El factorial genera una cadena de crides: cada nivell en crida una de sola. Fibonacci —cada nombre és la suma dels dos anteriors, començant per 0 i 1— genera un arbre, perquè cada nivell crida dues vegades:

def fibonacci(n):
    """Retorna l'n-esim nombre de Fibonacci (versio ingenua)."""
    if n < 2:                     # casos base: fib(0)=0, fib(1)=1
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)
graph TD
    A["fib(5)"] --> B["fib(4)"]
    A --> C["fib(3) *"]
    B --> D["fib(3) *"]
    B --> E["fib(2) **"]
    D --> F["fib(2) **"]
    D --> G["fib(1)"]
    C --> H["fib(2) **"]
    C --> I["fib(1)"]

Mira els nodes marcats: fib(3) es calcula dues vegades i fib(2) tres vegades, amb tot el seu subarbre repetit cada vegada. I això només amb n = 5. La diferència entre les dues formes és total: el factorial fa n crides, Fibonacci en fa aproximadament el doble per cada unitat que puja n. Aquesta explosió és l'assumpte de la secció 7.

  1. Recursivitat davant d'iteració

Tot el que es pot escriure amb recursivitat es pot escriure amb un bucle, i a l'inrevés. L'elecció és de claredat i cost, no de possibilitat.

Recursivitat Iteració (bucle)
Llegibilitat Excel·lent si el problema és naturalment recursiu Excel·lent en recorreguts lineals
Memòria Una entrada a la pila per crida pendent Constant: unes poques variables
Velocitat en Python Més lenta: cada crida té el seu cost Més ràpida
Límit de mida ~1.000 nivells Cap de pràctic

El factorial iteratiu cap en quatre línies —resultat = 1, un for i in range(2, n + 1) que fa resultat *= i, i un return— i és més ràpid que el recursiu. La regla pràctica en Python és senzilla i convé prendre-se-la seriosament: val més iterar, tret que el problema sigui naturalment recursiu. I ho és quan les seves dades tenen forma d'arbre —carpetes dins de carpetes, diccionaris dins de diccionaris, subtasques dins de tasques— o quan l'algorisme divideix el problema en trossos que es resolen igual, com el mergesort. Per recórrer, comptar o acumular, el bucle guanya sempre. Altres llenguatges (Scheme, Haskell, Erlang) optimitzen cert tipus de recursivitat perquè no consumeixi pila, amb una tècnica anomenada tail call optimization; Python no ho fa, deliberadament, i aquesta és una raó més per desconfiar aquí de la recursivitat profunda.

  1. El cost ocult de la recursivitat ingènua

El fibonacci de la secció 5 és correcte i és un desastre. Mesurem-lo amb time.perf_counter(), com a 06-02, envoltant la crida entre dues lectures del rellotge i restant-les:

import time
for n in (30, 35, 40):
    inici = time.perf_counter()
    print(f"fib({n}) = {fibonacci(n):<8} en {time.perf_counter() - inici:.3f}s")
n Crides realitzades Temps aproximat
30 ≈ 2.700.000 ≈ 0,35 s
35 ≈ 30.000.000 ≈ 4 s
40 ≈ 330.000.000 ≈ 45 s

Cada cinc unitats de n el temps es multiplica per deu, i fib(50) trigaria més d'una hora a calcular un nombre que cap en una línia. El motiu és a l'arbre de la secció 5: l'algorisme recalcula un cop i un altre el que ja havia calculat; per a fib(35) calcula fib(10) desenes de milers de vegades obtenint sempre el mateix. Compte, doncs: el problema no és la recursivitat, és la feina repetida, i la solució no és treure la recursivitat sinó deixar de repetir.

  1. Memoïtzació: recordar el que ja s'ha calculat

Memoïtzar és desar el resultat de cada càlcul en un diccionari per no repetir-lo. És l'intercanvi temps-memòria de 06-01 en la seva forma més pura: gastem memòria per no gastar temps.

def fibonacci_memo(n, memoria=None):
    """Retorna l'n-esim nombre de Fibonacci sense repetir calculs."""
    if memoria is None:
        memoria = {}                      # veure l'avis de 04-02 sobre {} per defecte
    if n < 2:
        return n
    if n in memoria:                      # ja el vam calcular abans: el retornem
        return memoria[n]
    memoria[n] = fibonacci_memo(n - 1, memoria) + fibonacci_memo(n - 2, memoria)
    return memoria[n]

El diccionari és l'estructura perfecta per a això pel que vas aprendre a 06-01: consultar n in memoria és pràcticament instantani gràcies a la taula hash. I fixa't en el memoria=None: no facis servir mai un diccionari o una llista buits com a valor per defecte d'un paràmetre, perquè Python els crea una sola vegada en definir la funció i es compartirien entre totes les crides. L'efecte és espectacular: fibonacci_memo(35) passa de 4 segons a menys d'una deumil·lèsima, perquè cada fib(k) es calcula una sola vegada i l'arbre es converteix en una cadena. Python porta això fet en un decorador de la biblioteca estàndard:

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_rapid(n):
    """Fibonacci amb memoitzacio automatica."""
    return n if n < 2 else fibonacci_rapid(n - 1) + fibonacci_rapid(n - 2)

print(fibonacci_rapid(200))           # instantani, i amb 42 xifres

Aquesta línia que comença per @ és un decorador: una anotació que envolta la funció i li afegeix comportament —aquí, la memòria de resultats— sense tocar-ne el codi. No els estudiarem en aquest curs; queda't amb el fet que @lru_cache és la manera professional de memoïtzar, que fibonacci_rapid.cache_info() informa dels seus encerts, i que només funciona si els arguments són immutables (nombres, textos, tuples), perquè els fa servir com a claus d'un diccionari.

  1. On la recursivitat sí que guanya

Fins aquí la recursivitat ha quedat com una versió bonica i més lenta del bucle. Canvia del tot quan les dades tenen forma d'arbre, perquè llavors un bucle no basta: caldrien tants bucles imbricats com nivells, i no saps quants n'hi ha. Reprenem el diccionari de diccionaris de 05-04, ara amb profunditat desconeguda:

estudi = {"equip": {"Marta": {"rol": "coordinadora", "hores": 38},
                    "Luis": {"rol": "dissenyador", "hores": 35}},
          "clients": {"Sole": {"actiu": True}, "Vidal": {"actiu": False}}}

def mostrar_arbre(dada, nivell=0):
    """Imprimeix una estructura imbricada de qualsevol profunditat, amb indentacio."""
    indentacio = "    " * nivell
    if isinstance(dada, dict):                      # es un diccionari: baixem un nivell
        for clau, valor in dada.items():
            print(f"{indentacio}{clau}:")
            mostrar_arbre(valor, nivell + 1)
    else:
        print(f"{indentacio}{dada}")                # cas base: un valor simple

El cas base és «això ja no conté res a dins»; el cas recursiu és «per a cada cosa que hi ha a dins, repeteix». El paràmetre nivell no dirigeix la recursivitat, només porta el compte de la indentació: és un patró habitual, passar informació cap avall. I isinstance(x, dict) és imprescindible perquè no sabem què ens trobarem a cada nivell. El mateix esquema recorre carpetes de disc; pathlib (05-05) ja porta el recorregut recursiu amb rglob, però escriure'l ensenya l'estructura:

from pathlib import Path

def espai_usat(carpeta):
    """Retorna la mida total en bytes d'una carpeta i tot el que conte."""
    total = 0
    for ruta in carpeta.iterdir():
        if ruta.is_dir():
            total += espai_usat(ruta)           # cas recursiu: una altra carpeta
        else:
            total += ruta.stat().st_size        # cas base: un fitxer
    return total

Aquí la recursivitat no és una elecció estètica: és l'única manera raonable de fer-ho, perquè ningú no sap quants nivells de carpetes hi ha. I el cas base no és un if al principi, sinó la situació natural en què la carpeta no conté subcarpetes i el for no crida ningú.

  1. Cerca binària recursiva i ordenació per barreja

El que vam prometre a 06-01: la cerca binària és naturalment recursiva, perquè «cercar en aquest tros» és el mateix problema que «cercar en la meitat d'aquest tros».

def binaria_recursiva(valors, cercat, esquerra=0, dreta=None):
    """Retorna la posicio de cercat a la llista ORDENADA valors, o -1."""
    if dreta is None:
        dreta = len(valors) - 1
    if esquerra > dreta:                          # cas base 1: tros buit
        return -1
    mig = (esquerra + dreta) // 2
    if valors[mig] == cercat:                     # cas base 2: trobat
        return mig
    if valors[mig] < cercat:
        return binaria_recursiva(valors, cercat, mig + 1, dreta)
    return binaria_recursiva(valors, cercat, esquerra, mig - 1)

Compara-la amb la versió iterativa de 06-01 i veuràs la traducció exacta: el while s'ha convertit en la crida recursiva i la condició de sortida esquerra <= dreta en el cas base esquerra > dreta, invertida. Els paràmetres per defecte (04-02) permeten cridar-la com binaria_recursiva(codis, 170) sense passar els límits. Traçant la cerca de 170 a [102, 118, 134, 156, 170, 189, 203, 240]:

Crida esquerra dreta mig Valor Acció
1 0 7 3 156 156 < 170 → cridar amb (4, 7)
2 4 7 5 189 189 > 170 → cridar amb (4, 4)
3 4 4 4 170 return 4, que puja pels tres nivells

Quina és millor? La iterativa, en Python, perquè fa el mateix sense consumir pila; la recursiva es llegeix millor i és la que veuràs als llibres. I en producció, ni l'una ni l'altra: bisect.

Ordenació per barreja (mergesort)

El que vam prometre a 06-02, i l'exemple canònic de divideix i venceràs: partir la llista per la meitat, ordenar cada meitat recursivament i fusionar les dues meitats ja ordenades.

def barrejar(esq, dre):
    """Fusiona dues llistes JA ordenades en una sola llista ordenada."""
    resultat = []
    i = j = 0
    while i < len(esq) and j < len(dre):
        if esq[i] <= dre[j]:                  # <= mante l'ESTABILITAT
            resultat.append(esq[i]); i += 1
        else:
            resultat.append(dre[j]); j += 1
    return resultat + esq[i:] + dre[j:]       # el que sobri d'una de les dues

def mergesort(valors):
    """Retorna una llista nova ordenada, per divisio i barreja."""
    if len(valors) <= 1:                      # cas base: 0 o 1 element ja esta ordenat
        return list(valors)
    mig = len(valors) // 2
    return barrejar(mergesort(valors[:mig]), mergesort(valors[mig:]))

barrejar és la peça no recursiva i la més important: recorre les dues llistes en paral·lel amb dos índexs, agafant sempre el menor dels dos fronts, en una sola passada. Aquest <= en lloc de < és el que fa estable l'algorisme: davant d'un empat agafa el de l'esquerra, que venia abans. I l'última línia afegeix el que quedi sense recórrer d'una de les dues llistes, que per construcció ja està ordenat. Traça de mergesort([3, 5, 2, 4]):

Fase Què passa
Divisió [3, 5, 2, 4] → [3, 5] i [2, 4], i aquestes → [3], [5], [2], [4]
Cas base Els quatre trossos d'un element es retornen tal qual, ja ordenats
Barreja [3] + [5] → [3, 5]; [2] + [4] → [2, 4]
Barreja final [3, 5] + [2, 4] → [2, 3, 4, 5]

La llista es parteix per la meitat fins a arribar a trossos d'un element —que estan ordenats per definició— i després es reconstrueix fusionant. Amb 1.000 elements hi ha uns 10 nivells de divisió i cada nivell costa una passada completa: unes 10.000 operacions, davant del milió de la bombolla. Aquesta és la diferència que veies a la taula de temps de 06-02, i Timsort fa servir exactament aquesta funció barrejar per unir els trams que ordena amb inserció.

  1. TascaFàcil v0.14: dies d'un desglossament imbricat

La Marta ha començat a desglossar els encàrrecs grans en subtasques, i aquestes al seu torn en subtasques més petites, sense un nombre fix de nivells, i necessita saber quants dies suma un projecte sencer. És el cas de la secció 9, i només es resol bé amb recursivitat.

# tascafacil.py - Estudi Alba / Versio 0.14: desglossament de projectes
OPCIONS = ("1", "2", "3", "4", "5", "6", "7", "8", "9", "10")
# --- Resta de constants i funcions: sense canvis respecte a la v0.13 ---

PROJECTE_SOLE = {"nom": "Identitat Forn Sole", "dies": 0, "subtasques": [
    {"nom": "Logotip", "dies": 0, "subtasques": [
        {"nom": "Esbossos", "dies": 2, "subtasques": []},
        {"nom": "Vectoritzat", "dies": 1, "subtasques": []}]},
    {"nom": "Papereria", "dies": 3, "subtasques": []},
    {"nom": "Retol del local", "dies": 4, "subtasques": []}]}

def dies_totals(tasca):
    """Suma els dies d'una tasca i de totes les seves subtasques, a qualsevol nivell."""
    total = tasca["dies"]                        # la feina propia d'aquest nivell
    for subtasca in tasca["subtasques"]:         # sense subtasques, el bucle no s'executa
        total += dies_totals(subtasca)           # cas recursiu
    return total

def mostrar_desglossament(tasca, nivell=0):
    """Imprimeix l'arbre de subtasques amb indentacio i el total de cada branca."""
    print(f"{'   ' * nivell}{tasca['nom']:<30}{dies_totals(tasca):>3}d")
    for subtasca in tasca["subtasques"]:
        mostrar_desglossament(subtasca, nivell + 1)

# A main(): l'opcio 9 crida mostrar_desglossament(PROJECTE_SOLE) i la sortida passa a la 10.

Sortida per pantalla, on cada branca mostra el seu propi total: Identitat Forn Sole 10d, i a dins Logotip 3d (amb Esbossos 2d i Vectoritzat 1d indentades a sota), Papereria 3d i Retol del local 4d. Tres observacions sobre aquest codi:

  • El cas base no és un if. Quan subtasques és buida, el for no s'executa cap vegada i la funció retorna directament tasca["dies"]. És la manera més neta d'escriure el cas base en recórrer una col·lecció: la llista buida ho és per si mateixa.
  • L'estructura de dades i l'algorisme encaixen. Cada node té la mateixa forma —nom, dies, subtasques—, sigui l'arrel o l'última fulla, i per això la mateixa funció serveix per a tots els nivells: dissenyar les dades amb aquesta uniformitat és el que fa possible la recursivitat. I així cap de les dues funcions no sap quants nivells hi ha, que és exactament el que es demanava; amb bucles imbricats caldria fixar per endavant una profunditat màxima. I compte: mostrar_desglossament recalcula el total de cada branca, repetint feina igual que Fibonacci. Amb tres nivells és irrellevant; si el desglossament creixés, tocaria memoïtzar.

Errors Comuns i Consells

Oblidar el cas base o no acostar-s'hi. Els dos símptomes són el mateix RecursionError. Comprova que existeix un if que retorna sense cridar-se i que l'argument de la crida recursiva és més a prop d'aquest cas a cada pas. I oblidar el return davant de la crida recursiva. factorial(n - 1) sense return calcula el resultat i el llença; la funció retorna None i en multiplicar salta TypeError. En una funció recursiva que retorna un valor, gairebé totes les branques porten return.

Fer servir {} o [] com a valor per defecte d'un paràmetre, típic en memoïtzar. Python crea aquest objecte una sola vegada i el comparteix entre totes les crides: els resultats d'una consulta contaminen la següent. Fes servir None i crea'l a dins. I compte amb la recursivitat sobre llistes amb talls: suma(valors[1:]) copia la llista sencera a cada crida, així que sumar 1.000 nombres copia mig milió d'elements; per a col·leccions grans, passa índexs o fes servir un bucle.

Consell: confia en la crida recursiva. L'error d'aprenentatge més comú és intentar seguir mentalment tots els nivells. No ho facis: dona per bo que factorial(n - 1) retorna el factorial correcte i limita't a comprovar el cas base i el pas. Si tots dos estan bé, la funció està bé. I si dubtes, dibuixa l'arbre: tres nivells en paper basten per veure si el problema es redueix i si hi ha feina repetida, com la de Fibonacci. És la prova d'escriptori de 01-05 aplicada a la recursivitat.

Exercicis

Exercici 1: Traçar i comptar

Traça suma([4, 1, 6]) indicant en una taula cada crida, què espera i què retorna. Després, dibuixa l'arbre de crides de fibonacci(4) i compta quantes vegades es calcula fibonacci(2). Finalment, explica què imprimeix compte_enrere(2) si intercanvies les dues últimes línies del cos de la funció.

Exercici 2: Comptar fulles i trobar el màxim

Sobre l'estructura de subtasques de l'apartat 11, escriu dues funcions recursives: comptar_fulles(tasca), que retorna quantes subtasques sense subtasques pròpies hi ha a tota la branca (les fulles de l'arbre, és a dir, la feina real); i tasca_mes_llarga(tasca), que retorna el nom de la fulla amb més dies de tota la branca.

Exercici 3: Potència ràpida

Escriu potencia(base, exponent) recursiva que calculi base ** exponent sense fer servir l'operador **, amb aquesta propietat: si l'exponent és parell, base^n = (base^(n/2))²; si és senar, base^n = base × base^(n-1). Compara quantes crides fa, amb exponent = 16, davant de la versió que resta un a l'exponent cada vegada.

Solucions

Solució 1. Traça de suma([4, 1, 6]):

Nivell Crida Espera… Rep Retorna
1 suma([4, 1, 6]) suma([1, 6]) 7 4 + 7 = 11
2 suma([1, 6]) suma([6]) 6 1 + 6 = 7
3 suma([6]) suma([]) 0 6 + 0 = 6
4 suma([]) ningú: cas base — 0

A l'arbre de fibonacci(4), fibonacci(2) es calcula dues vegades: una penjant de fib(3) i una altra directament de fib(4). I si a compte_enrere s'intercanvien el print(n) i la crida recursiva, el compte surt a l'inrevés: primer Ja! i després 1, 2. El motiu és el de la secció 4: el que va abans de la crida s'executa a l'anada i el que va després, a la tornada.

Solució 2.

def comptar_fulles(tasca):
    """Compta les subtasques sense subtasques propies de tota la branca."""
    if not tasca["subtasques"]:                  # cas base: es una fulla
        return 1
    return sum(comptar_fulles(sub) for sub in tasca["subtasques"])

def tasca_mes_llarga(tasca):
    """Retorna el nom de la fulla amb mes dies de tota la branca."""
    if not tasca["subtasques"]:
        return tasca["nom"], tasca["dies"]       # retornem parell (nom, dies)
    candidates = [tasca_mes_llarga(sub) for sub in tasca["subtasques"]]
    return max(candidates, key=lambda parell: parell[1])

print(comptar_fulles(PROJECTE_SOLE), tasca_mes_llarga(PROJECTE_SOLE)[0])  # 4 Retol del local

comptar_fulles distingeix explícitament la fulla —que val 1— de la branca, que val la suma de les seves filles. tasca_mes_llarga fa servir un truc important: retorna una tupla (nom, dies) en comptes de només el nom, perquè per comparar candidates al nivell superior calen els dies. És el «retornar diversos valors» de 04-02 al servei de la recursivitat: cada nivell retorna el que el nivell de dalt necessita per decidir.

Solució 3.

def potencia(base, exponent):
    """Calcula base elevat a exponent dividint l'exponent per dos."""
    if exponent == 0:                     # cas base
        return 1
    if exponent % 2 == 0:                 # exponent parell: una sola crida
        meitat = potencia(base, exponent // 2)
        return meitat * meitat
    return base * potencia(base, exponent - 1)    # senar: el convertim en parell

La clau és a meitat = potencia(base, exponent // 2) desada en una variable: si escrivissis potencia(...) * potencia(...) calcularies dues vegades el mateix i tornaries al problema de Fibonacci. Amb exponent 16 el repartiment és 16 → 8 → 4 → 2 → 1 → 0: cinc crides, davant de les disset de la versió que resta un cada vegada. És la mateixa idea de dividir entre dos de la cerca binària i del mergesort, aplicada a l'aritmètica; en Python, per descomptat, s'escriu base ** exponent.

Conclusió

Una funció recursiva es crida a si mateixa amb una versió més petita del mateix problema, i només funciona si té les seves dues peces: un cas base que retorna sense cridar-se i un cas recursiu que s'hi acosta. Cada crida pendent viu a la pila de crides, que Python limita a uns mil nivells abans de llançar RecursionError; pujar el límit amb sys.setrecursionlimit gairebé mai no és la solució correcta. A l'anada s'apilen les crides i a la tornada es construeix el resultat, com mostren les traces del factorial, la suma d'una llista i la inversió d'una cadena. El factorial genera una cadena de crides i Fibonacci un arbre, i aquí hi ha el parany: el Fibonacci ingenu repeteix tanta feina que fib(40) triga quaranta-cinc segons. La cura no és abandonar la recursivitat sinó deixar de repetir, amb memoïtzació —un diccionari de resultats ja calculats, o el decorador @lru_cache—, que és l'intercanvi temps-memòria en estat pur. Davant de la iteració, la recursivitat perd en memòria i velocitat i guanya en claredat quan les dades tenen forma d'arbre (estructures imbricades, carpetes de disc, desglossaments de subtasques) o quan l'algorisme divideix el problema: la cerca binària recursiva promesa a 06-01 i el mergesort promès a 06-02, la funció barrejar del qual recorre dues llistes ordenades en una sola passada i és la mateixa que fa servir Timsort. TascaFàcil arriba a la v0.14 i calcula els dies d'un projecte desglossat en subtasques a qualsevol profunditat.

Amb això tens totes les peces del mòdul, i també un munt d'afirmacions soltes que hem anat fent sense poder demostrar-les: «vint comparacions davant d'un milió», «doblar les dades quadruplica la feina», «l'arbre es converteix en una cadena», «això és un intercanvi temps-memòria». Totes descriuen el mateix —quant costa un programa segons la mida de les seves dades— i totes demanen un vocabulari precís. A Eficiència i notació Big-O el tindràs per fi, i amb ell podràs mirar qualsevol funció i dir en veu alta quant costarà abans d'executar-la.

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