L'algoritmo della Torre di Hanoi

procedure hanoi(n, source, target, spare)
    if n == 0 then
        return
    hanoi(n - 1, source, spare, target)
    move disk n from source to target
    hanoi(n - 1, spare, target, source)
end procedure

Che cosa guardare

• I ruoli ruotano. La torre B è l'appoggio per la prima chiamata e l'arrivo per quella che essa lancia. Ogni livello di ricorsione rietichetta le tre torri, e quel rietichettare è tutto il trucco.
• Lo stack non diventa mai profondo. Con tre dischi non ci sono mai più di 4 chiamate in corso insieme — una per ogni numero di dischi, da 3 a 0 — anche se il programma fa 15 chiamate in tutto.
• Metà delle chiamate non fa nulla. Di quelle 15 chiamate, 8 riguardano zero dischi e tornano subito. Sono il prezzo del caso base più semplice possibile.
• La riga che sposta viene eseguita esattamente 2ⁿ − 1 volte. Sette, per tre dischi, lungo i 43 passi dell'esecuzione.

Il primo punto è il più difficile da cogliere mentre il programma gira, perché quando accade sulle torri non si muove nulla: cambiano solo i nomi sotto di esse. Qui è fermo: la prima chiamata, le due sotto di essa lungo la strada verso la mossa 1, e la chiamata che riporta indietro la pila.

1. hanoi(3, A, C, B)

   La prima chiamata: spostare tutti e 3 i dischi da A a C. Così resta B come appoggio. Origine A, arrivo C, appoggio B.

2. hanoi(2, A, B, C)

   La sua prima chiamata. Il disco 3 non può muoversi con i dischi 1 e 2 sopra, e quelli non possono andare su C, dove è diretto il disco 3. Quindi B, che un attimo fa era l'appoggio, diventa l'arrivo, e C diventa l'appoggio. Origine A, arrivo B, appoggio C.

3. hanoi(1, A, C, B)

   Un livello più sotto, di nuovo lo stesso scambio. Per liberare il disco 2, il disco 1 va su C, e B torna a essere l'appoggio. Origine A, arrivo C, appoggio B.

4. hanoi(2, B, C, A)

   Il disco 3 è passato. La seconda chiamata della radice riporta i dischi 1 e 2 da B sopra di lui, così ora B è l'origine e A, dove tutti i dischi sono partiti, è l'appoggio. Origine B, arrivo C, appoggio A.

Il secondo è più facile da mettere in dubbio che da verificare, quindi ecco l'intera esecuzione con l'altezza dello stack a ogni suo passo:

• L'esecuzione dura 43 passi e fa 15 chiamate in tutto.
• Il numero di chiamate sullo stack sale e scende fra 0 e 4, e raggiunge 4 in 8 di quei passi — ogni volta che una chiamata senza dischi da spostare comincia e torna.
• La profondità 4 è n + 1 per n = 3, e nessun passo dell'esecuzione la supera.

L'albero di ricorsione

Disegna ogni chiamata come una casella sotto la chiamata che l'ha fatta e il programma diventa un albero. Metti ogni casella sopra il numero della mossa che compie e compare qualcos'altro: leggendo le caselle da sinistra a destra si ottengono le mosse in ordine. Con tre dischi, la mossa propria della prima chiamata — il disco più grande — è la mossa 4, proprio nel mezzo, con l'intera soluzione in tre mosse per due dischi da entrambi i lati.

1. Mossa 1: la chiamata con n = 1, da A a C, sposta il disco 1.
2. Mossa 2: la chiamata con n = 2, da A a B, sposta il disco 2, tra le sue due chiamate con n = 1.
3. Mossa 3: la chiamata con n = 1, da C a B, sposta il disco 1.
4. Mossa 4: la chiamata con n = 3, da A a C, sposta il disco 3, tra le sue due chiamate con n = 2.
5. Mossa 5: la chiamata con n = 1, da B a A, sposta il disco 1.
6. Mossa 6: la chiamata con n = 2, da B a C, sposta il disco 2, tra le sue due chiamate con n = 1.
7. Mossa 7: la chiamata con n = 1, da A a C, sposta il disco 1.

Questa simmetria vale a ogni dimensione. La mossa 2ⁿ⁻¹ è sempre il disco più grande che passa, e le mosse prima e dopo sono la soluzione a (n − 1) dischi giocata due volte, con due torri che si scambiano i ruoli. È per questo che un elenco di mosse di qualsiasi lunghezza si legge a colpo d'occhio, e per questo la soluzione a cinque dischi è quella a quattro, una mossa, e di nuovo quella a quattro.

Perché è corretto

L'algoritmo non infrange mai una regola e termina sempre, e la dimostrazione è abbastanza breve da poter essere data per intero. L'affermazione, per ogni n, è:

Se gli n dischi in cima alla torre d'origine sono i dischi da 1 a n, e ogni disco altrove è più grande di n, allora hanoi(n, source, target, spare) sposta quegli n dischi sull'arrivo, in modo valido, e non tocca nient'altro.

Per n = 0 non c'è niente da spostare e non si tocca nulla.

Supponiamo che l'affermazione valga per n − 1. Allora ciascuno dei tre passi è valido:

1. La prima chiamata sposta i dischi da 1 a n − 1 sull'appoggio. Ne ha diritto: ogni altro disco, compreso il disco n, è più grande di n − 1.
2. Il disco n passa sull'arrivo. Ora non ha niente sopra, e sull'arrivo ci sono solo dischi più grandi di n.
3. La seconda chiamata sposta i dischi da 1 a n − 1 dall'appoggio all'arrivo. Valida per lo stesso motivo: il disco n, ora sotto di loro, è più grande.

Tutti gli n dischi sono sull'arrivo e nient'altro si è mosso. Per induzione l'affermazione vale per ogni n, e il rompicapo completo è il caso in cui l'origine ha tutti i dischi.

1. Assuntol'affermazione per n − 1

   L'ipotesi dice che una chiamata su n − 1 dischi li sposta dove le si dice, in modo valido, e non tocca nient'altro. Applicata qui, porta i dischi da 1 a n − 1 dall'origine all'appoggio. Ne ha diritto: ogni disco su cui potrebbe posarli — disco n compreso — è più grande di qualunque disco stia portando.

2. Dimostrato quiuna mossa valida

   Questo è l'unico passo che la dimostrazione deve sostenere da sé, ed è una sola mossa. Il disco n è libero, perché il passo precedente l'ha liberato. L'arrivo non contiene altro che dischi più grandi di n, perché tutto ciò che è più piccolo sta sull'appoggio. Quindi la mossa è valida.

3. Assuntol'affermazione per n − 1, di nuovo

   La stessa ipotesi, usata una seconda volta, riporta i dischi da 1 a n − 1 dall'appoggio all'arrivo. Valida per lo stesso motivo di prima: il disco n, ora sotto di loro, è più grande. Tutti gli n dischi sono sull'arrivo e nient'altro si è mosso — che è l'affermazione per n.

La ricorrenza, risolta come si deve

Sia T(n) il numero di mosse che l'algoritmo compie per n dischi. La funzione fa due chiamate su n − 1 dischi e una mossa propria, e non fa alcuna mossa quando non ci sono dischi:

Per risolverla, sostituisci la ricorrenza in sé stessa e cerca lo schema. Questo si chiama srotolare, o telescopare:

Individuare uno schema non è dimostrarlo, quindi confermalo per induzione. T(0) = 0 = 2⁰ − 1. E se T(n − 1) = 2ⁿ⁻¹ − 1, allora T(n) = 2(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 2 + 1 = 2ⁿ − 1. La forma chiusa è esatta per ogni n.

C'è una terza via, ed è un'immagine che hai già visto. L'albero di ricorsione qui sopra è un albero binario completo: la radice sposta n dischi, le due chiamate sotto di essa ne spostano n − 1 ciascuna, le quattro sotto quelle n − 2, e così via. La profondità k contiene quindi 2ᵏ chiamate, l'ultimo livello è la profondità n − 1, e ognuna di quelle chiamate fa esattamente una mossa. Somma i livelli e il conto esce come una serie geometrica:

Tre metodi — srotolare, induzione e l'albero — e una sola risposta. Vale la pena saperlo, perché ce n'è un quarto che viene proposto di continuo, ed è sbagliato.

La stessa aritmetica conta le chiamate. Ogni chiamata con n {">"} 0 dischi ne fa altre due, quindi ci sono C(n) = 2C(n − 1) + 1 chiamate con C(0) = 1, che si srotola in 2ⁿ⁺¹ − 1. Cioè 2ⁿ − 1 chiamate che spostano un disco, più 2ⁿ che tornano subito.

Costo in tempo e in memoria

Ogni chiamata fa una quantità costante di lavoro oltre alle sue due chiamate ricorsive, quindi il tempo di esecuzione è proporzionale al numero di chiamate: Θ(2ⁿ). Nessun algoritmo più furbo può fare meglio, perché l'output stesso è lungo 2ⁿ − 1 mosse — e 2ⁿ − 1 è un minimo dimostrato, non soltanto il migliore che qualcuno abbia trovato. La dimostrazione che non esiste soluzione più breve ha una pagina propria: perché il minimo è 2ⁿ − 1.

La memoria è un'altra storia. Le chiamate non esistono tutte insieme: una chiamata finisce prima che cominci la sorella, quindi lo stack tiene una sola chiamata per livello, da n fino a 0. Lo spazio usato è Θ(n) — sessantacinque record di attivazione per i sessantaquattro dischi della leggenda, cosa che qualsiasi computer regge senza accorgersene. A finire è il tempo: 18.446.744.073.709.551.615 mosse a un miliardo al secondo fanno comunque 584 anni.

Quel numero è quello della leggenda, e la leggenda è più giovane di quanto sembri. Un tempio dove dei sacerdoti spostano sessantaquattro dischi d'oro, e la fine del mondo quando avranno finito, compare per la prima volta a stampa nel 1884 — in un articolo che pubblicizzava un rompicapo messo in vendita a Parigi l'anno prima, sotto il nome di un professore che non esisteva. Al ritmo dei monaci, una mossa al secondo, al mondo restano 585 miliardi di anni, circa quaranta volte l'età attuale dell'universo. Il matematico dietro il rompicapo e la storia fu Édouard Lucas, che dimostrò a mano che 2¹²⁷ − 1 è primo e morì a 49 anni per l'infezione di un taglio provocato da un piatto che un cameriere aveva lasciato cadere a un banchetto.

Metti dei numeri in quelle formule e i due tipi di costo si separano. Ogni disco in più fa poco più che raddoppiare le mosse e le chiamate, e aggiunge un solo record alla massima profondità raggiunta dallo stack:

La calcolatrice delle mosse minime ricava mosse e tempo per qualsiasi numero di dischi, e l'ultima riga — la dimensione della leggenda — ha una pagina tutta sua.

Senza ricorsione

Le stesse mosse possono essere prodotte da un semplice ciclo con due regole:

• Mosse dispari: il disco più piccolo avanza di una torre lungo un circuito fisso — A → C → B per un numero dispari di dischi, A → B → C per uno pari.
• Mosse pari: fai l'unica mossa valida che non tocca il disco più piccolo. Ce n'è sempre esattamente una.

Queste due regole riproducono la soluzione ricorsiva mossa per mossa; la pagina della soluzione iterativa mostra perché, e la gioca su un tavolo.

Esiste una versione ancora più strana, che non memorizza alcuna torre: il disco, l'origine e la destinazione della mossa m si leggono tutti dalle cifre binarie di m. Quel collegamento, e il codice Gray che vi si nasconde, sono in Torre di Hanoi, binario e codice Gray.

Da una posizione che non è l'inizio

La funzione da manuale presuppone che tutti i dischi partano dalla torre d'origine. Dalle un rompicapo a metà e non ha niente da dire. Un caso in più lo risolve. Guarda il disco più grande:

• È già sulla torre che deve raggiungere? Non gli serve alcuna mossa. Risolvi i dischi più piccoli mandandoli su quella stessa torre.
• È altrove? Sposta i dischi più piccoli sulla torre che non è né quella dov'è né quella dove va, spostalo, e prosegui come prima.

Quella versione trova la soluzione più breve da qualsiasi posizione valida, ed è ciò che esegue il risolutore della Torre di Hanoi.

Mettiti alla prova

Tre domande a cui la pagina ha già risposto. Provaci prima di aprirle: se una non viene, la sezione citata insieme alla risposta è quella da rileggere.

1. Tre dischi sono sette mosse. Quante ne sono 5 dischi, e quante di quelle spostano il disco 5 stesso?

   Mostra la risposta

   31 mosse, cioè 2⁵ − 1 — ed esattamente una di esse sposta il disco più grande. Tutti i dischi tranne il più grande si muovono più di una volta, perché ciascuna delle due metà della soluzione deve spostarli. La ricorrenza, risolta come si deve.

2. hanoi(3, A, C, B) fa hanoi(2, A, B, C) come prima chiamata. Perché l'arrivo di quella chiamata è B e non C?

   Mostra la risposta

   Perché il disco 3 va su C, e può posarsi lì solo se C è vuota. Quindi i due dischi sopra di lui vanno parcheggiati altrove, e quell'altrove può essere solo B. La torre a cui una chiamata punta diventa quella che la sua prima chiamata deve tenere libera — ed è per questo che due dei tre argomenti si scambiano di posto all'ingresso. Che cosa guardare.

3. Risolvere 20 dischi fa 2.097.151 chiamate. Quante di esse sono sullo stack nello stesso istante, al massimo?

   Mostra la risposta

   21 — una per ogni numero di dischi, da 20 a 0. Una chiamata finisce prima che cominci la sorella, quindi le chiamate non esistono mai tutte insieme: il lavoro è esponenziale e la memoria è lineare. Costo in tempo e in memoria.

L'algoritmo nel tuo linguaggio

La stessa funzione in sei linguaggi, ognuno con un programma eseguibile, una spiegazione riga per riga, le torri che girano accanto e ciò che è specifico di quel linguaggio — cose che diventano importanti appena provi a contare le mosse per sessantaquattro dischi. Quelle sei pagine sono in inglese.

• Torre di Hanoi in PythonENRecursive and iterative programs, why Python's recursion limit never bites here, and integers that simply do not overflow.
• Torre di Hanoi in JavaScriptENWhy 2 ** 64 − 1 prints the wrong number, BigInt, and a generator that hands out one move at a time.
• Torre di Hanoi in JavaENWhy (1L << 64) − 1 is zero, counting with BigInteger, and the same solution driven by an explicit stack.
• Torre di Hanoi in CENUndefined shifts, uint64_t, and a loop that reads every move straight off the bits of the move number.
• Torre di Hanoi in C++ENCollecting the moves in a std::vector, the 64-disk count checked by the compiler, and three pairs of towers in a loop.
• Torre di Hanoi in C#ENTop-level statements, an iterator whose moves LINQ can query, and ulong, checked arithmetic and UInt128 for the move count.

Le parole di questa pagina

Caso base

La versione del problema a cui una funzione ricorsiva risponde direttamente, senza chiamare sé stessa. È ciò che ferma la ricorsione. Qui è n = 0: nessun disco da spostare, quindi niente da fare, e la chiamata torna. Ogni catena di chiamate, per quanto profonda, finisce su uno di questi.

Caso ricorsivo

Tutto ciò che non è il caso base: la parte della funzione che risolve una versione più piccola dello stesso problema e ne costruisce la risposta. Qui sono le tre righe che tolgono di mezzo n − 1 dischi, spostano il disco n e riportano indietro quegli n − 1.

Stack delle chiamate

L'elenco delle chiamate di funzione iniziate e non ancora concluse, la più recente per ultima. Una chiamata viene aggiunta quando comincia e tolta quando torna, quindi lo stack è il modo in cui un programma ricorda dove tornare. È ciò che disegna il pannello qui sopra, ed è memoria vera — per questo la sua profondità è il costo in spazio dell'algoritmo.

Record di attivazione

Una voce dello stack delle chiamate: gli argomenti e le variabili locali di una singola chiamata. Ogni riga dello stack nel pannello è un record, con il proprio n e la propria idea di quale torre sia origine, arrivo e appoggio. Sessantaquattro dischi richiedono sessantacinque record, che non è nulla; il problema sono le mosse.

Telescopare

Detto anche srotolare: risolvere una ricorrenza sostituendola in sé stessa finché lo schema non è evidente, e fissando poi il numero di sostituzioni in modo che resti solo il valore iniziale noto. Si chiama telescopare perché i termini di mezzo si richiudono come le sezioni di un cannocchiale.

Θsaid “theta grande”

Un tasso di crescita che è insieme limite superiore e inferiore: Θ(2ⁿ) significa che il costo cresce come 2ⁿ, non soltanto che non cresce più in fretta. O(2ⁿ) prometterebbe solo il tetto. Qui Θ è la notazione onesta, perché questo algoritmo fa davvero 2ⁿ − 1 mosse: non può essere fortunato e finire prima.

Domande frequenti

Come funziona l'algoritmo ricorsivo della Torre di Hanoi?

Per spostare n dischi da una torre d'origine a una d'arrivo, prima sposta gli n − 1 dischi in cima sulla torre d'appoggio, poi sposta il disco più grande sull'arrivo, poi sposta gli n − 1 dischi dall'appoggio all'arrivo. Ciascuno di quei due trasferimenti più piccoli è lo stesso problema con un disco in meno, quindi la funzione chiama sé stessa per farli, e una chiamata senza dischi da spostare semplicemente torna.

La Torre di Hanoi è divide et impera o programmazione dinamica?

È divide et impera. Il problema è diviso in due sottoproblemi da n − 1 dischi, ciascuno risolto per ricorsione, e il passo di combinazione è una singola mossa del disco più grande. Non è programmazione dinamica, e la memoizzazione non aiuta — anche se i sottoproblemi si ripetono davvero. Con tre torri ci sono solo sei modi di nominare origine, arrivo e appoggio, quindi hanoi(1, A, C, B) viene davvero chiamata due volte risolvendo tre dischi. Metterla in cache non porta nulla, perché la risposta a un sottoproblema è un elenco di 2ᵏ − 1 mosse, e riprodurre un elenco salvato di quella lunghezza costa quanto produrlo. Qui il lavoro è l'output, e nessuna tabella accorcia l'output.

Il Teorema Master si applica alla ricorrenza della Torre di Hanoi?

No. Il Teorema Master copre ricorrenze della forma T(n) = aT(n/b) + f(n), dove ogni sottoproblema è una frazione dell'originale. La ricorrenza della Torre di Hanoi è T(n) = 2T(n − 1) + 1: il sottoproblema è più piccolo di un disco, non di un fattore. Srotolarla dà T(n) = 2ⁿ − 1 direttamente, e l'induzione lo conferma.

Quanto in profondità arriva la ricorsione?

Con un caso base a n = 0, sullo stack ci sono al massimo n + 1 chiamate insieme: una per ogni numero di dischi da n a 0. Con un caso base a n = 1 sono n. In ogni caso la profondità cresce linearmente, ed è per questo che la soluzione ricorsiva ha bisogno solo di O(n) di memoria pur facendo un numero esponenziale di mosse.

Quante chiamate di funzione fa la soluzione ricorsiva?

2ⁿ⁺¹ − 1 chiamate quando il caso base è n = 0: le 2ⁿ − 1 chiamate che spostano un disco, più 2ⁿ chiamate che non trovano nulla da spostare e tornano. Tre dischi fanno 15 chiamate. Scritta con un caso base a n = 1, la stessa funzione fa esattamente 2ⁿ − 1 chiamate, una per mossa.

L'algoritmo iterativo è più veloce di quello ricorsivo?

Non in un modo che conti. Entrambi devono produrre 2ⁿ − 1 mosse, quindi entrambi impiegano un tempo proporzionale a 2ⁿ. La versione iterativa evita il costo delle chiamate di funzione e non può esaurire lo stack, ma qui la ricorsione è profonda solo n livelli: esaurire lo stack non è un rischio reale per nessun numero di dischi che tu possa aspettare.

Come si disegna l'algoritmo della Torre di Hanoi in un diagramma di flusso?

Viene fuori ben poco, ed è la risposta onesta. Un diagramma di flusso mostra il controllo che attraversa dei blocchi una volta sola, e il secondo blocco di questo algoritmo è l'intero diagramma da capo — tre livelli più sotto, con due torri scambiate e un disco in meno. Un diagramma di flusso non ha una notazione per questo: quindi un diagramma della soluzione ricorsiva o è sbagliato, o è l'immagine di una sola chiamata con due blocchi che dicono «chiama hanoi», e non insegna nulla che lo pseudocodice di quattro righe non insegni già. Il diagramma che invece lo esprime è l'albero di ricorsione: ogni chiamata disegnata sotto la chiamata che l'ha fatta, ogni casella sopra la mossa che compie. È su questa pagina, e leggerne le caselle da sinistra a destra dà le mosse in ordine.

L'algoritmo può risolvere un rompicapo già a metà?

La versione da manuale non può: presuppone che tutti i dischi partano da una sola torre. Si generalizza con un caso in più — se il disco più grande è già sul suo arrivo, saltalo e risolvi i dischi sopra — e quella versione trova la soluzione più breve da qualsiasi posizione valida. Il risolutore di questo sito esegue esattamente quello. Apri il risolutore →