Matematicamente.it

Ecco un'immagine d'esempio:



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

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.

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?

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.

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.

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.

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.

È 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)

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

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 …