Ricorsione

Spostare una torre di Hanoi di 64 dischi richiede 18446744073709551615 mosse; una funzione ricorsiva descrive la soluzione in quattro righe.

Una funzione che chiama sé stessa

Alcuni problemi contengono una copia più piccola di sé stessi. Il fattoriale di 5, scritto 5!, è 5 × 4 × 3 × 2 × 1 = 120. Guardalo di nuovo: è 5 × (4 × 3 × 2 × 1), cioè 5 × 4!. In generale n! = n × (n − 1)!, quindi per calcolare un fattoriale puoi calcolare un fattoriale più piccolo e moltiplicare. Una funzione che risolve un problema chiamando sé stessa su una versione più piccola è ricorsiva.

function factorial(n) {
  if (n <= 1) return 1;          // caso base: fermati qui
  return n * factorial(n - 1);   // caso ricorsivo: un problema più piccolo
}
console.log(factorial(5)); // 120

Ogni funzione ricorsiva ha bisogno di due parti. Il caso base è un input abbastanza piccolo da avere una risposta diretta, senza un'altra chiamata: qui, il fattoriale di 1 è 1. Il caso ricorsivo riduce il problema e chiama di nuovo la funzione. Ogni chiamata deve avvicinarsi al caso base. Se non lo fa, per esempio se per errore scrivi factorial(n + 1), le chiamate non finiscono mai.

La pila delle chiamate

Come fa il computer a tenere traccia di tutte quelle chiamate non finite? Quando factorial(5) è in esecuzione, arriva a 5 * factorial(4) e deve aspettare la risposta. Il computer mette la chiamata in attesa su una pila, una catasta in cui l'ultimo elemento messo è il primo a essere tolto. factorial(4) aspetta factorial(3), e così via fino a factorial(1), che restituisce subito 1. Poi la pila si svuota: factorial(2) restituisce 2, factorial(3) restituisce 6, factorial(4) restituisce 24 e factorial(5) restituisce 120.

La pila ha una dimensione limitata. Una ricorsione che non raggiunge mai il caso base continua ad aggiungere chiamate finché lo spazio finisce, e JavaScript si ferma con un errore; in Chrome e in Node.js il messaggio è «RangeError: Maximum call stack size exceeded». Lo stesso limite fa sì che una ricorsione molto profonda, centinaia di migliaia di livelli, sia meglio scriverla come un ciclo.

La torre di Hanoi

La torre di Hanoi è un rompicapo pubblicato dal matematico francese Édouard Lucas nel 1883. Ci sono tre pioli e una pila di dischi di dimensioni diverse sul primo piolo, con il più grande in basso. L'obiettivo è spostare tutta la pila sul terzo piolo. Puoi spostare un solo disco alla volta, solo il disco in cima a un piolo, e non puoi mai mettere un disco più grande su uno più piccolo.

Pensare passo per passo a dove va ogni disco diventa presto confuso. Pensare in modo ricorsivo rende tutto breve. Per spostare n dischi da A a C: prima togli di mezzo gli n − 1 dischi in alto, da A a B. Poi sposta il disco più grande da A a C. Poi sposta gli n − 1 dischi da B sopra di esso, in C. Spostare n − 1 dischi è lo stesso rompicapo, di una misura più piccolo, e spostare un disco è il caso base. Per 3 dischi si ottengono 7 mosse; il laboratorio mostra la pila delle chiamate in attesa a ogni mossa.

function hanoi(n, from, to, via) {
  if (n === 0) return;
  hanoi(n - 1, from, via, to);
  console.log("disk " + n + ": " + from + " -> " + to);
  hanoi(n - 1, via, to, from);
}
hanoi(3, "A", "C", "B");  // 7 mosse

Quante mosse servono con n dischi? Spostare n dischi costa due spostamenti di n − 1 dischi più una mossa: M(n) = 2M(n − 1) + 1, con M(1) = 1. Si ottiene 1, 3, 7, 15, 31, quindi M(n) = 2ⁿ − 1, e nessuna soluzione può usarne meno. Dieci dischi richiedono 1023 mosse. Sessantaquattro dischi ne richiedono 2⁶⁴ − 1 = 18446744073709551615; a una mossa al secondo sono circa 585 miliardi di anni. È la crescita O(2ⁿ) dell'unità precedente.

Ricorsione, cicli e lavoro ripetuto

Tutto ciò che si scrive con la ricorsione si può scrivere con un ciclo e una pila gestita da te, e i casi semplici come il fattoriale spesso sono più chiari come cicli. La ricorsione dà il meglio quando il problema stesso ha la forma di un albero: dividere una lista nel merge sort, esplorare cartelle dentro cartelle o cercare l'uscita di un labirinto, che è l'argomento dell'ultima unità. Una trappola è il lavoro ripetuto. I numeri di Fibonacci 0, 1, 1, 2, 3, 5, 8, … seguono fib(n) = fib(n − 1) + fib(n − 2). Scritto direttamente in forma ricorsiva, fib(10) = 55 fa 177 chiamate, fib(20) ne fa 21891 e fib(30) ne fa 2692537, perché gli stessi valori più piccoli vengono calcolati ancora e ancora. Ricordare le risposte già trovate, oppure costruire dal basso con un ciclo, elimina questo spreco.