Torre di Hanoi ricorsione

[ZfreS]

Ecco un'immagine d'esempio:



Quello che non capisco è evidenziato. Sono proprio quelle chiamate ricorsive successive in cui cambiano sempre le variabili.

[vict85]

La logica del passaggio ricorsivo è la seguente:
Voglio spostare il disco di dimensione n dalla colonna A alla colonna C, ma non posso perché ho n-1 dischi sopra quello. Quindi prima di spostare questo disco in C, sposto i restanti dischi nella colonna di appoggio. A quel punto puoi spostare il disco di dimensione n nella colonna finale e rispostare gli altri dischi sopra quello (che ora si trovano nella colonna B). Questo ragionamento lo fai ricorsivamente. Nel codice si usano nomi discutibili per le variabili.

[ZfreS]

Ok, il ragionamento mi è chiaro. Se devo spostare 3 dischi non posso perchè ne ho due e non posso ancora perchè ne ho uno ancora, ma una volta spostato quello, cosa succede? La chiamata a chi torna? Epoi prosegue col resto del codice o no?

[vict85]

Le domande che fai sono più di C++ che sull'algoritmo. Insomma, ogni chiamata a quella funzione (ad esclusione del caso n=1 che stampa e ritorna subito) fa tre cose: (1) chiama ricorsivamente se stessa, (2) stampa la propria azione, (3) chiama ricorsivamente se stessa. Fatto quello ritorna al proprio chiamante.

[ZfreS]

Ok vict, penso di essere sulla giusta strada per capire, sto facendo tutto l'algoritmo a mano e nel codice ho inserito delle cout che di volta in volta mi stampano i valori di A B e C.

[ZfreS]

Prima viene spostato il disco in cima e viene stampato A-C, poi la chiamata passa al secondo disco e viene stampato A-B. Ma dopo la chiamata deve andare a ritroso e passare al terzo disco, perchè invece ritorna al primo? Non mi è chiaro questo.

[ZfreS]

Forse non mi sono espresso chiaramente. All'inizio viene chiamta hanoi(3) che a sua volta chiama hanoi(2) che a sua volta chiama hanoi(1). Questa non avendo dischi al di sopra soddisfa il caso base della ricorsione e viene spostato da A a C. Ora, in base al meccanismo della ricorsione la chiamata torna ad hanoi(2) che è rimasta in attesa e poi compie il suo spostamento da A a B, ora mi aspetto che la chiamata torni ad hanoi(3) e invece torna ad hanoi(1). Questo fa si he le regole del gioco siano rispettate, ma stravolge il meccanismo della ricorsione che conosco. Vorrei capire la logica di questo.

[vict85]

È solo una ricorsione diversa, una ricorsione può chiamare se stessa un numero indeterminato di volte, e il numero può anche cambiare a seconda dagli input. Comunque non mi sembra sia un procedimento diverso dal QuickSort e in generale rientra negli algoritmi divide-et-impera. https://it.wikipedia.org/wiki/Divide_et ... nformatica)

[ZfreS]

Ok, ma in questo caso perhè cambia così, quale sarebbe l'ordine delle chiamata ricorsive?

[axpgn]

Quello scritto nel codice …
Dopo l'else c'è una chiamata alla funzione col parametro $n-1$; quando torna ci sono ancora due righe di codice, no?
E quindi esegue quelle …
Una di esse è un'altra chiamata alla funzione con lo stesso parametro; quando ritorna anche da questa, dato che non ci sono più comandi da eseguire, ritorna alla funzione che l'ha chiamata …