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

Recursivitat

Següent ►
►

Queda una manera de resoldre problemes amb funcions que encara no has fet servir a propòsit, i és la més desconcertant de totes: una funció que es crida a si mateixa. Ja te l'has trobat dues vegades —l'expressió de funció amb nom de 03-02 existia en part per a això, i el RangeError: Maximum call stack size exceeded de 03-05 va aparèixer per una crida que no s'aturava mai—. En aquesta lliçó hi posaràs mètode. I no és un exercici acadèmic: Nómada Tasques té un problema que els bucles resolen malament i la recursió resol de manera natural, perquè la Marta vol que una tasca es pugui descompondre en subtasques, i aquestes subtasques en unes altres, sense límit de profunditat.

Contingut

  1. Què és una funció recursiva
  2. Cas base i cas recursiu
  3. La pila de crides d'una recursió
  4. Escalfament 1: factorial
  5. Escalfament 2: Fibonacci i el seu cost ocult
  6. El cas real: subtasques imbricades
  7. Recórrer l'arbre: sumar hores
  8. Recórrer l'arbre: aplanar, comptar i cercar
  9. Recursió davant d'iteració
  10. Recursió de cua i per què JavaScript no l'optimitza
  11. Memoïtzació aplicada a Fibonacci
  12. Quan NO fer servir recursió
  13. Errors Habituals i Consells
  14. Exercicis
  15. Conclusió

  1. Què és una funció recursiva

Una funció recursiva és aquella que, dins del seu cos, es crida a si mateixa amb un problema més petit, fins a arribar a un cas tan simple que es pot resoldre directament.

function compteEnrere(n) {
  if (n <= 0) {                      // cas base: es resol sense recursió
    console.log('Fet!');
    return;
  }
  console.log(`Queden ${n} tasques per revisar…`);
  compteEnrere(n - 1);               // cas recursiu: el mateix problema, més petit
}

compteEnrere(3);
// Queden 3 tasques per revisar…
// Queden 2 tasques per revisar…
// Queden 1 tasques per revisar…
// Fet!

La idea que hi ha al darrere és una manera de pensar, no un truc de sintaxi:

Per resoldre un problema gran, suposa que ja saps resoldre el mateix problema una mica més petit, i combina aquest resultat amb el que et toca fer aquí.

Això s'anomena salt de fe recursiu, i és la part que més costa. Quan escrius compteEnrere(n - 1) no has d'imaginar totes les crides encadenades: només has de confiar que aquella crida fa bé la seva feina.

  1. Cas base i cas recursiu

Tota funció recursiva correcta té exactament dues parts:

Part Què fa Què passa si falta o està malament
Cas base Resol el problema mínim sense tornar-se a cridar Recursió infinita → RangeError
Cas recursiu Es crida a si mateixa amb un problema més petit La funció no progressa mai o no resol res

I dues condicions que cal verificar sempre:

  1. El cas base s'assoleix. No n'hi ha prou que existeixi: l'argument s'hi ha d'acostar a cada crida.
  2. El problema es redueix de debò. Cridar-se amb el mateix argument, o amb un de més gran, és un bucle infinit amb més passos.
// ✗ Cas base inabastable amb decimals
function malCompte(n) {
  if (n === 0) return 'fi';
  return malCompte(n - 1);
}
// malCompte(3.5) → 2.5, 1.5, 0.5, -0.5, -1.5… mai no és exactament 0

// ✓ Cas base robust
function bonCompte(n) {
  if (n <= 0) return 'fi';
  return bonCompte(n - 1);
}
flowchart TD
    A["Crida amb n"] --> B{"Cas base?"}
    B -->|sí| C["Retornar el resultat directe"]
    B -->|no| D["Fer la part que toca aquí"]
    D --> E["Cridar-se amb un problema menor"]
    E --> F["Combinar el resultat i retornar"]

  1. La pila de crides d'una recursió

Aquí es reprèn la pila de Hoisting i el Context d'Execució. Cada crida recursiva apila un context nou que no s'allibera fins que la crida interior acaba.

function sumarFinsA(n) {
  if (n <= 0) return 0;
  return n + sumarFinsA(n - 1);
}

console.log(sumarFinsA(4));   // 10
sequenceDiagram
    participant G as global
    participant A as sumarFinsA(4)
    participant B as sumarFinsA(3)
    participant C as sumarFinsA(2)
    participant D as sumarFinsA(1)
    participant E as sumarFinsA(0)

    G->>A: crida
    A->>B: 4 + ?
    B->>C: 3 + ?
    C->>D: 2 + ?
    D->>E: 1 + ?
    E-->>D: 0 (cas base)
    D-->>C: 1 + 0 = 1
    C-->>B: 2 + 1 = 3
    B-->>A: 3 + 3 = 6
    A-->>G: 4 + 6 = 10

Dues observacions essencials:

  • La fase de "baixada" apila crides sense calcular res definitiu: cadascuna queda esperant el resultat de la següent.
  • La fase de "pujada" és on es produeixen els càlculs, de dins cap enfora.

Per això una recursió de profunditat 50 000 peta la pila, com vas comprovar a l'exercici final de 03-05: les 50 000 sumes estan totes pendents alhora.

  1. Escalfament 1: factorial

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

function factorial(n) {
  if (n < 0) throw new RangeError('El factorial no està definit per a negatius.');
  if (n <= 1) return 1;              // cas base: 0! = 1 i 1! = 1
  return n * factorial(n - 1);       // cas recursiu
}

console.log(factorial(0));   // 1
console.log(factorial(5));   // 120
console.log(factorial(6));   // 720

Traça de factorial(5):

Crida Retorna Resultat
factorial(5) 5 * factorial(4) 5 * 24 = 120
factorial(4) 4 * factorial(3) 4 * 6 = 24
factorial(3) 3 * factorial(2) 3 * 2 = 6
factorial(2) 2 * factorial(1) 2 * 1 = 2
factorial(1) 1 (cas base) 1

Fixa't en el throw per al cas negatiu: és la fallada primerenca de Gestió d'Errors. Sense ell, factorial(-1) baixaria fins a -Infinity apilant contextos i acabaria en RangeError, un error que no explica res.

  1. Escalfament 2: Fibonacci i el seu cost ocult

La successió de Fibonacci comença 0, 1, 1, 2, 3, 5, 8, 13…, on cada terme és la suma dels dos anteriors.

function fibonacci(n) {
  if (n < 0) throw new RangeError('n ha de ser 0 o més gran.');
  if (n === 0) return 0;             // cas base 1
  if (n === 1) return 1;             // cas base 2
  return fibonacci(n - 1) + fibonacci(n - 2);   // DUES crides recursives
}

console.log(fibonacci(10));   // 55

Elegant i correcta. I desastrosa en rendiment, perquè cada crida en genera dues, i moltes repeteixen feina ja feta:

flowchart 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)"]

fib(3) es calcula dues vegades i fib(2) tres vegades, i amb una n més gran la duplicació explota. El nombre de crides creix exponencialment:

let crides = 0;
function fibonacciComptat(n) {
  crides++;
  if (n <= 1) return n;
  return fibonacciComptat(n - 1) + fibonacciComptat(n - 2);
}

crides = 0; fibonacciComptat(10); console.log(crides);   // 177
crides = 0; fibonacciComptat(20); console.log(crides);   // 21891
crides = 0; fibonacciComptat(30); console.log(crides);   // 2692537
crides = 0; fibonacciComptat(35); console.log(crides);   // 29860703

De 10 a 35, les crides passen de 177 a gairebé 30 milions. A l'apartat 11 ho arreglaràs amb memoïtzació, i la millora serà espectacular. Reté la dada que fibonacci(35) triga uns quants segons: la compararàs.

  1. El cas real: subtasques imbricades

Fins ara Nómada Tasques ha treballat amb una llista plana. Però la Marta ha demanat una cosa raonable: que una tasca gran es pugui descompondre en subtasques, i que aquestes subtasques es puguin descompondre al seu torn. Així queda la tasca 1 del backlog desglossada:

flowchart TD
    A["1 · Redissenyar la sala polivalent"] --> B["11 · Mesurar i aixecar el plànol<br/>3 h"]
    A --> C["12 · Triar el mobiliari"]
    A --> D["13 · Pintar i muntar<br/>5 h"]
    C --> E["121 · Demanar pressupostos<br/>2 h"]
    C --> F["122 · Visitar dos proveïdors<br/>2 h"]

Aquesta estructura és un arbre, i en JavaScript es representa amb objectes que contenen arrays d'objectes:

'use strict';

// Nota: aquí no hi ha més remei que fer servir objectes imbricats. Els objectes s'estudien
// a fons al Mòdul 4; de moment n'hi ha prou amb llegir propietats amb el punt.
const tascaRedisseny = {
  id: 1,
  titol: 'Redissenyar la sala polivalent',
  responsable: 'Iván',
  estat: 'en-curs',
  horesEstimades: 0,          // 0 = les hores són a les subtasques
  subtasques: [
    {
      id: 11, titol: 'Mesurar i aixecar el plànol', responsable: 'Iván',
      estat: 'feta', horesEstimades: 3, subtasques: []
    },
    {
      id: 12, titol: 'Triar el mobiliari', responsable: 'Marta',
      estat: 'en-curs', horesEstimades: 0,
      subtasques: [
        { id: 121, titol: 'Demanar pressupostos', responsable: 'Marta',
          estat: 'feta', horesEstimades: 2, subtasques: [] },
        { id: 122, titol: 'Visitar dos proveïdors', responsable: 'Marta',
          estat: 'pendent', horesEstimades: 2, subtasques: [] }
      ]
    },
    {
      id: 13, titol: 'Pintar i muntar', responsable: 'Iván',
      estat: 'pendent', horesEstimades: 5, subtasques: []
    }
  ]
};

Per què un bucle no n'hi ha prou, aquí? Perquè no saps quants nivells hi ha. Amb un for recorres el primer nivell; amb dos d'imbricats, el segon; amb tres, el tercer. Però si demà l'Iván hi afegeix una sub-sub-subtasca, el codi deixa de funcionar. La recursió, en canvi, no ho necessita saber: cada nivell es tracta exactament igual que l'anterior.

Aquest és el senyal que delata un problema recursiu: l'estructura de la dada es conté a si mateixa. Una tasca conté tasques, una carpeta conté carpetes, un comentari conté respostes que són comentaris.

  1. Recórrer l'arbre: sumar hores

El primer càlcul que necessita la Marta: quantes hores suma una tasca comptant totes les seves subtasques, a qualsevol profunditat.

/**
 * Suma les hores d'una tasca i de totes les seves subtasques, recursivament.
 * @param {Object} tasca  node amb horesEstimades i subtasques
 * @returns {number} total d'hores del subarbre
 */
function sumarHoresTotals(tasca) {
  let total = tasca.horesEstimades;                 // el que toca en aquest node

  for (const subtasca of tasca.subtasques) {        // cas recursiu
    total += sumarHoresTotals(subtasca);
  }

  return total;                                     // cas base implícit: sense subtasques, el bucle no hi entra
}

console.log(sumarHoresTotals(tascaRedisseny));   // 12

Val la pena analitzar per què funciona:

  • El cas base és implícit. Si subtasques és [], el for no dóna cap volta i la funció retorna només tasca.horesEstimades. No cal un if explícit, encara que escriure'l tampoc no estaria malament.
  • Cada node fa el mateix: aporta les seves hores i demana als seus fills que aportin les seves.
  • El resultat, 12 h, coincideix amb les hores que la tasca 1 tenia al backlog pla del Mòdul 2 (3 + 2 + 2 + 5 = 12). La descomposició no ha canviat el total.

I una variant que filtra: hores obertes (no acabades) del subarbre.

function sumarHoresObertes(tasca) {
  let total = tasca.estat !== 'feta' ? tasca.horesEstimades : 0;

  for (const subtasca of tasca.subtasques) {
    total += sumarHoresObertes(subtasca);
  }

  return total;
}

console.log(sumarHoresObertes(tascaRedisseny));   // 7

Comprovació manual: queden obertes «Visitar dos proveïdors» (2 h) i «Pintar i muntar» (5 h). Total, 7 h. Les de «Mesurar i aixecar el plànol» (3 h) i «Demanar pressupostos» (2 h) estan fetes.

  1. Recórrer l'arbre: aplanar, comptar i cercar

Amb el mateix esquema es resolen totes les operacions sobre l'arbre. Només canvia què es fa a cada node.

8.1 Aplanar l'arbre a una llista

/**
 * Retorna un array pla amb totes les tasques del subarbre,
 * afegint a cadascuna el seu nivell de profunditat.
 */
function aplanarTasques(tasca, nivell = 0) {
  const resultat = [{ id: tasca.id, titol: tasca.titol, nivell: nivell,
                      hores: tasca.horesEstimades, estat: tasca.estat }];

  for (const subtasca of tasca.subtasques) {
    const filles = aplanarTasques(subtasca, nivell + 1);
    for (const f of filles) resultat.push(f);
  }

  return resultat;
}

const planes = aplanarTasques(tascaRedisseny);

for (const t of planes) {
  const sagnia = '  '.repeat(t.nivell);
  const marca = t.estat === 'feta' ? '✓' : '○';
  console.log(`${sagnia}${marca} [${t.id}] ${t.titol}${t.hores > 0 ? ` — ${t.hores} h` : ''}`);
}

Sortida:

○ [1] Redissenyar la sala polivalent
  ✓ [11] Mesurar i aixecar el plànol — 3 h
  ○ [12] Triar el mobiliari
    ✓ [121] Demanar pressupostos — 2 h
    ○ [122] Visitar dos proveïdors — 2 h
  ○ [13] Pintar i muntar — 5 h

El paràmetre nivell = 0 amb valor per defecte (03-03) és un patró habitual en recursió: qui la crida des de fora l'omet, i la mateixa funció el va incrementant cap endins.

8.2 Comptar tasques i mesurar la profunditat

function comptarTasques(tasca) {
  let total = 1;                                   // ella mateixa
  for (const sub of tasca.subtasques) total += comptarTasques(sub);
  return total;
}

function profunditatMaxima(tasca) {
  if (tasca.subtasques.length === 0) return 1;     // cas base explícit

  let maxima = 0;
  for (const sub of tasca.subtasques) {
    const p = profunditatMaxima(sub);
    if (p > maxima) maxima = p;
  }
  return 1 + maxima;
}

console.log(comptarTasques(tascaRedisseny));      // 6
console.log(profunditatMaxima(tascaRedisseny));   // 3

8.3 Cercar una tasca per identificador

/**
 * Cerca una tasca per id a tot el subarbre.
 * @returns {Object|null} la tasca trobada, o null
 */
function cercarPerId(tasca, id) {
  if (tasca.id === id) return tasca;               // cas base 1: trobada

  for (const sub of tasca.subtasques) {
    const trobada = cercarPerId(sub, id);
    if (trobada !== null) return trobada;          // talla tan bon punt la troba
  }

  return null;                                     // cas base 2: no és en aquesta branca
}

const t = cercarPerId(tascaRedisseny, 122);
console.log(t.titol);                              // Visitar dos proveïdors
console.log(cercarPerId(tascaRedisseny, 999));     // null

L'if (trobada !== null) return trobada; és important: sense ell, la funció continuaria explorant branques inútils després d'haver trobat el resultat. És l'equivalent recursiu del break de break, continue i Bucles Imbricats.

  1. Recursió davant d'iteració

Tot el que es pot fer amb recursió es pot fer amb bucles, i a l'inrevés. La pregunta és quina convé en cada cas.

Criteri Recursió Iteració (bucles)
Llegibilitat amb dades imbricades Molt alta: el codi imita l'estructura Baixa: cal gestionar una pila a mà
Llegibilitat amb dades planes Pitjor: hi afegeix soroll Alta
Memòria Una entrada de pila per crida Constant
Risc de desbordament Real a partir de ~10 000 nivells Cap
Velocitat Una mica menor (cost de cada crida) Una mica major
Depuració Més difícil: la pila s'omple de marcs iguals Senzilla
Estat Implícit, als paràmetres Explícit, en variables

Compara les dues versions de la mateixa feina, aplanar l'arbre. La recursiva ja l'has vista. La iterativa necessita gestionar la seva pròpia pila:

function aplanarIteratiu(arrel) {
  const resultat = [];
  const pendents = [{ tasca: arrel, nivell: 0 }];   // pila explícita

  while (pendents.length > 0) {
    const actual = pendents.pop();

    resultat.push({ id: actual.tasca.id, titol: actual.tasca.titol, nivell: actual.nivell });

    // S'apilen en ordre invers perquè surtin en l'ordre natural
    for (let i = actual.tasca.subtasques.length - 1; i >= 0; i--) {
      pendents.push({ tasca: actual.tasca.subtasques[i], nivell: actual.nivell + 1 });
    }
  }

  return resultat;
}

console.log(aplanarIteratiu(tascaRedisseny).length);   // 6

Funciona, no pot desbordar la pila del motor i és més ràpida. Però fixa't en el que ha costat: una pila manual, un bucle invers poc evident i un objecte auxiliar per portar el nivell. Aquesta és l'elecció real: claredat davant de control.

Regla pràctica per al dia a dia:

  • Estructura imbricada de profunditat moderada (arbres de menús, comentaris, subtasques, JSON) → recursió.
  • Llista plana, o profunditat potencialment enorme (milers de nivells, fitxers grans) → iteració.

  1. Recursió de cua i per què JavaScript no l'optimitza

Es diu que una recursió és de cua (tail recursion) quan la crida recursiva és l'última cosa que fa la funció: el seu resultat es retorna tal qual, sense operacions pendents.

// NO és de cua: en tornar, encara cal multiplicar per n
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);       // ← queda pendent la multiplicació
}

// SÍ que és de cua: la crida es retorna directament
function factorialCua(n, acumulat = 1) {
  if (n <= 1) return acumulat;
  return factorialCua(n - 1, n * acumulat);   // ← res pendent
}

console.log(factorialCua(5));   // 120

En teoria, una recursió de cua no necessita apilar contextos: com que no queda res per fer en tornar, el motor podria reutilitzar el marc actual. Això s'anomena tail call optimization (TCO) i convertiria la recursió en un bucle, amb memòria constant.

El problema és que, a la pràctica, JavaScript no l'aplica:

Motor / entorn Optimitza les crides de cua?
Especificació ES2015 Sí, l'exigeix
V8 (Chrome, Edge, Node.js) No (implementada i retirada)
SpiderMonkey (Firefox) No
JavaScriptCore (Safari) Sí, en mode estricte

Comprova-ho:

function comptarCua(n) {
  if (n <= 0) return 'fi';
  return comptarCua(n - 1);
}

try {
  console.log(comptarCua(100000));
} catch (error) {
  console.error(`${error.name}: ${error.message}`);
}
// A Node.js: RangeError: Maximum call stack size exceeded

Conclusió pràctica: escriure recursió de cua en JavaScript no et protegeix del desbordament. És un bon costum estilístic i funciona en altres llenguatges, però aquí, si la profunditat pot ser gran, la solució és un bucle.

  1. Memoïtzació aplicada a Fibonacci

Tornem al Fibonacci exponencial de l'apartat 5. El problema era recalcular el mateix una vegada i una altra, i ja tens l'eina per arreglar-ho: la memoïtzació amb closure d'Àmbit i Closures.

/**
 * Retorna una versió memoïtzada de Fibonacci.
 * La memòria cau viu al closure: privada i persistent entre crides.
 */
function crearFibonacci() {
  const cache = {};          // estat privat
  let calculs = 0;
  let encerts = 0;

  function fib(n) {
    if (n < 0) throw new RangeError('n ha de ser 0 o més gran.');
    if (n <= 1) return n;

    if (n in cache) {
      encerts++;
      return cache[n];
    }

    calculs++;
    const resultat = fib(n - 1) + fib(n - 2);
    cache[n] = resultat;
    return resultat;
  }

  fib.estadistiques = () => `${calculs} càlculs, ${encerts} encerts`;
  return fib;
}

const fibonacciRapid = crearFibonacci();

let t = Date.now();
console.log(fibonacciRapid(35), `${Date.now() - t} ms`);   // 9227465  ~0 ms
console.log(fibonacciRapid.estadistiques());               // 34 càlculs, 33 encerts

t = Date.now();
console.log(fibonacciRapid(40), `${Date.now() - t} ms`);   // 102334155  ~0 ms
console.log(fibonacciRapid(90));                           // 2880067194370816000

La comparació és demolidora:

n Crides sense memoïtzar Càlculs amb memoïtzació Temps aproximat
10 177 9 ~0 ms en tots dos
20 21 891 19 ~0 ms en tots dos
30 2 692 537 29 ~30 ms → ~0 ms
35 29 860 703 34 ~300 ms → ~0 ms
40 ~331 000 000 39 uns quants segons → ~0 ms
50 inviable 49 — → ~0 ms

Es passa de creixement exponencial a creixement lineal. El cost és la memòria de la memòria cau, que aquí és menyspreable, i la restricció de sempre: memoïtzar només funcions pures (03-03). fib(n) sempre dóna el mateix per a la mateixa n, així que és segur.

Dos avisos sobre el resultat de fibonacciRapid(90): aquest nombre supera Number.MAX_SAFE_INTEGER i per tant és aproximat. Per a enters grans cal fer servir BigInt, el tipus que vas conèixer a Variables i Tipus de Dades. I la profunditat continua sent lineal: fibonacciRapid(20000) desbordaria la pila encara que la memòria cau funcioni.

  1. Quan NO fer servir recursió

Hi ha tres situacions on la recursió és la resposta equivocada:

Situació Per què Alternativa
Recórrer una llista plana Un bucle és més clar, ràpid i segur for / for...of
Profunditat gran o desconeguda sense límit RangeError en producció, amb dades reals Iteració amb pila explícita
Càlcul simple amb acumulador La recursió hi afegeix soroll sense aportar res Bucle amb variable acumuladora 
// ✗ Recursió innecessària sobre una llista plana
function sumarHoresRec(hores, i = 0) {
  if (i >= hores.length) return 0;
  return hores[i] + sumarHoresRec(hores, i + 1);
}

// ✓ Bucle: més clar, sense risc de pila
function sumarHores(hores) {
  let total = 0;
  for (const h of hores) total += h;
  return total;
}

console.log(sumarHores([12, 6, 14, 3, 8, 5]));   // 48

I un advertiment de seguretat que importa més del que sembla: si les dades imbricades vénen de fora (una API, un fitxer que puja l'usuari), la profunditat la controla qui envia les dades. Un arbre maliciós de 100 000 nivells tombaria la teva funció recursiva. En aquests casos, o iteres, o hi poses un límit explícit:

function sumarHoresTotals(tasca, profunditat = 0) {
  if (profunditat > 50) {
    throw new RangeError('Estructura de subtasques massa profunda (màxim 50 nivells).');
  }

  let total = tasca.horesEstimades;
  for (const sub of tasca.subtasques) {
    total += sumarHoresTotals(sub, profunditat + 1);
  }
  return total;
}

Errors Habituals i Consells

1. Oblidar el cas base. És l'error número u i sempre produeix RangeError: Maximum call stack size exceeded.

2. Cas base inabastable. Fes servir <= en lloc de === quan l'argument se'l pugui saltar (decimals, restes de més d'un).

3. No reduir el problema.

function malament(tasca) {
  return sumarHoresTotals(tasca);   // ✗ mateix argument, recursió infinita
}

4. Oblidar el return davant de la crida recursiva.

function cercarMalament(tasca, id) {
  if (tasca.id === id) return tasca;
  for (const sub of tasca.subtasques) {
    cercarMalament(sub, id);   // ✗ el resultat es perd
  }
  return null;                 // sempre null
}

És una fallada silenciosa: no dóna error, simplement no troba res mai.

5. Confondre un for dins d'una recursió amb un bucle imbricat. El for recorre els fills d'aquest node; la recursió baixa de nivell. Són eixos diferents.

6. Memoïtzar una funció impura. Ja ho saps des de 03-04: la memòria cau retornaria resultats obsolets.

7. Confiar en la recursió de cua. No està optimitzada en la majoria de motors.

8. Consell: dibuixa l'arbre de crides per a tres o quatre nivells. Gairebé tots els errors de recursió es veuen a simple vista al dibuix i són invisibles llegint el codi.

9. Consell: posa un console.log amb sagnia en depurar.

function sumarAmbTraca(tasca, nivell = 0) {
  const sagnia = '  '.repeat(nivell);
  console.log(`${sagnia}→ entra a ${tasca.titol}`);

  let total = tasca.horesEstimades;
  for (const sub of tasca.subtasques) total += sumarAmbTraca(sub, nivell + 1);

  console.log(`${sagnia}← surt de ${tasca.titol} amb ${total} h`);
  return total;
}

Veure la baixada i la pujada indentades fa comprensible qualsevol recursió. A Depuració de JavaScript veuràs com fer el mateix amb punts d'interrupció i la pila en viu.

Exercicis

Exercici 1 — Operacions sobre l'arbre de subtasques

Sobre tascaRedisseny, escriu tres funcions recursives:

  • comptarPerEstat(tasca, estat): quantes tasques del subarbre són en aquest estat.
  • titolsDeResponsable(tasca, nom): array amb els títols de les tasques assignades a aquesta persona, a qualsevol profunditat.
  • estaCompleta(tasca): true si la tasca i totes les seves subtasques són en estat 'feta'.

Exercici 2 — Ruta fins a una tasca

Escriu rutaFinsA(tasca, id) que retorni un array amb els títols que van des de l'arrel fins a la tasca amb aquest identificador, o null si no existeix. Per exemple, per a l'id 121 ha de retornar ['Redissenyar la sala polivalent', 'Triar el mobiliari', 'Demanar pressupostos'].

Exercici 3 — De recursiu a iteratiu

La funció profunditatMaxima de l'apartat 8.2 és recursiva. Reescriu-la de manera iterativa fent servir una pila explícita, comprova que dóna el mateix resultat (3) i explica en quin cas concret preferiries cada versió.

Solucions

Exercici 1

function comptarPerEstat(tasca, estat) {
  let total = tasca.estat === estat ? 1 : 0;
  for (const sub of tasca.subtasques) {
    total += comptarPerEstat(sub, estat);
  }
  return total;
}

function titolsDeResponsable(tasca, nom) {
  const trobats = [];

  if (tasca.responsable === nom) trobats.push(tasca.titol);

  for (const sub of tasca.subtasques) {
    const fills = titolsDeResponsable(sub, nom);
    for (const f of fills) trobats.push(f);
  }

  return trobats;
}

function estaCompleta(tasca) {
  if (tasca.estat !== 'feta') return false;          // guarda: ella mateixa no ho està

  for (const sub of tasca.subtasques) {
    if (!estaCompleta(sub)) return false;            // talla a la primera que falli
  }

  return true;
}

console.log(comptarPerEstat(tascaRedisseny, 'feta'));       // 2
console.log(comptarPerEstat(tascaRedisseny, 'pendent'));    // 2
console.log(comptarPerEstat(tascaRedisseny, 'en-curs'));    // 2

console.log(titolsDeResponsable(tascaRedisseny, 'Marta'));
// [ 'Triar el mobiliari', 'Demanar pressupostos', 'Visitar dos proveïdors' ]

console.log(estaCompleta(tascaRedisseny));                    // false
console.log(estaCompleta(cercarPerId(tascaRedisseny, 11)));   // true

Comentari: les tres segueixen el mateix esquema —fer alguna cosa amb aquest node, després amb cada fill— i només canvia l'operació. estaCompleta incorpora a més la sortida primerenca: tan bon punt troba una subtasca incompleta deixa de mirar la resta, igual que elMeuEvery a Funcions d'Ordre Superior.

Exercici 2

function rutaFinsA(tasca, id) {
  if (tasca.id === id) return [tasca.titol];         // cas base: és aquesta

  for (const sub of tasca.subtasques) {
    const rutaFilla = rutaFinsA(sub, id);            // salt de fe
    if (rutaFilla !== null) {
      return [tasca.titol, ...rutaFilla];            // afegeix aquest nivell al davant
    }
  }

  return null;                                       // no és en aquesta branca
}

console.log(rutaFinsA(tascaRedisseny, 121));
// [ 'Redissenyar la sala polivalent', 'Triar el mobiliari', 'Demanar pressupostos' ]

console.log(rutaFinsA(tascaRedisseny, 13));
// [ 'Redissenyar la sala polivalent', 'Pintar i muntar' ]

console.log(rutaFinsA(tascaRedisseny, 999));   // null

// I per mostrar-la com una molla de pa:
const ruta = rutaFinsA(tascaRedisseny, 122);
console.log(ruta.join(' › '));
// Redissenyar la sala polivalent › Triar el mobiliari › Visitar dos proveïdors

Comentari: la clau és la línia return [tasca.titol, ...rutaFilla];. El ... és l'operador spread, que desplega els elements de rutaFilla dins de l'array nou; l'estudiaràs formalment a Desestructuració d'Objectes, Spread i Rest. Sense ell, hauries de construir l'array amb un bucle. Fixa't també que la ruta es munta a la pujada: cada nivell hi afegeix el seu títol al davant del que li retorna el nivell inferior.

Exercici 3

function profunditatMaximaIterativa(arrel) {
  let maxima = 0;
  const pendents = [{ tasca: arrel, nivell: 1 }];

  while (pendents.length > 0) {
    const actual = pendents.pop();

    if (actual.nivell > maxima) maxima = actual.nivell;

    for (const sub of actual.tasca.subtasques) {
      pendents.push({ tasca: sub, nivell: actual.nivell + 1 });
    }
  }

  return maxima;
}

console.log(profunditatMaxima(tascaRedisseny));            // 3
console.log(profunditatMaximaIterativa(tascaRedisseny));   // 3

Quan preferir cadascuna:

Versió Quan
Recursiva Arbres de subtasques creats per l'equip de Taller Nómada: profunditat de dos o tres nivells, i el codi es llegeix com la definició del problema
Iterativa Dades importades d'una API externa, on la profunditat no està sota el teu control i un arbre molt profund tombaria l'aplicació

Observa a més una diferència subtil: la recursiva calcula la profunditat a la pujada (1 + màxim dels fills), mentre que la iterativa la porta a la baixada, desant el nivell al costat de cada node pendent. És el mateix càlcul vist del revés.

Conclusió

Amb aquesta lliçó tanques el Mòdul 3. Ja saps que una funció recursiva es crida a si mateixa amb un problema més petit, que necessita sempre un cas base assolible i un cas recursiu que redueixi de debò el problema, i que cada crida apila un context que només s'allibera a la pujada: per això una recursió profunda produeix el RangeError que vas conèixer a 03-05. Has practicat amb factorial i fibonacci, i has vist de primera mà com el Fibonacci ingenu passa de 177 crides amb n = 10 a gairebé trenta milions amb n = 35, i com la memoïtzació amb closure de 03-04 el torna a trenta-quatre càlculs.

Sobretot, has vist per què existeix la recursió. Quan la Marta va demanar descompondre una tasca en subtasques, i aquestes en unes altres, els bucles van deixar de servir: no es pot escriure un for imbricat per a una profunditat que no coneixes. sumarHoresTotals, aplanarTasques, comptarTasques, profunditatMaxima, cercarPerId i rutaFinsA resolen aquest arbre amb el mateix esquema de sis línies, perquè l'estructura del codi imita l'estructura de la dada. I en coneixes els límits: la taula de recursió davant d'iteració, la recursió de cua que JavaScript no optimitza, el límit de profunditat per a dades que vénen de fora i les tres situacions en què un bucle és senzillament la resposta correcta.

Mira el que has guanyat en aquestes set lliçons. Vas començar amb blocs de codi copiats quatre vegades i acabes amb pesDePrioritat(), estaVencuda(), descriureTasca(), crearTasca(), resumirCarrega(), crearGeneradorIds(), crearMagatzemTasques(), un motor d'informes configurable i un recorregut recursiu de subtasques. Saps definir i cridar funcions, escriure-les com a valors i com a fletxes, dissenyar-ne els paràmetres i els retorns, controlar on viu cada variable, tancar estat en un closure, entendre què prepara el motor abans d'executar, passar funcions a altres funcions i fer que una funció es cridi a si mateixa. Això és, de bon tros, el salt més gran del curs fins ara.

Però fixa't en el preu que has anat pagant sense queixar-te. Tot aquest mòdul ha treballat amb variables soltes i arrays paral·lels: titols[i], responsables[i], prioritats[i], estats[i], hores[i], datesLimit[i]. Has hagut de filtrar índexs en lloc de tasques, passar vuit arguments a descriureTasca, arrossegar sis arrays a cada funció i confiar que cap no es desalineï. I tan bon punt ha aparegut una estructura de debò —l'arbre de subtasques— no hi ha hagut més remei que fer servir objectes imbricats, avisant que allò venia després. Aquest "després" és ara. Al Mòdul 4: Objectes i Arrays deixaràs de simular el model de dades i l'escriuràs de debò: cada tasca serà un objecte amb els seus nou camps, el backlog serà un array d'objectes, i totes les funcions d'aquest mòdul es reescriuran amb signatures netes com descriureTasca(tasca, avui). Comença amb Introducció als Objectes, i el primer alleujament arribarà a la primera pàgina.

◄ Anterior
◄
Següent ►
►

Curs de JavaScript: De Principiant a Avançat

Mòdul 1: Introducció a JavaScript

Mòdul 2: Estructures de Control

Mòdul 3: Funcions

Mòdul 4: Objectes i Arrays

Mòdul 5: Objectes i Funcions Avançades

Mòdul 6: El Model d'Objectes del Document (DOM)

Mòdul 7: APIs del Navegador i Temes Avançats

Mòdul 8: Proves i Depuració

Mòdul 9: Rendiment i Optimització

Mòdul 10: Frameworks i Llibreries de JavaScript

Mòdul 11: Projecte Final

El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats