Pagina 5 di 5

Re: Torre di Hanoi ricorsione

MessaggioInviato: 21/06/2019, 11:33
da ZfreS
Mi stai dicendo quindi che una volta spostato il disco in cima, vengono eseguitele istruzioni dell'else anzichè resistuire il controllo alla chiamata precedente?

Re: Torre di Hanoi ricorsione

MessaggioInviato: 21/06/2019, 11:49
da axpgn
Ma che significa?
L'else viene eseguito tutto le volte che la funzione viene chiamata con $n>1$ e viene eseguito TUTTO.

Re: Torre di Hanoi ricorsione

MessaggioInviato: 21/06/2019, 12:04
da ZfreS
Io fin'ora ho capito che una volta incontrata la chiamata a se stessa nell'else veniva richimata la funzione ignorando le altre istruzioni dell'else.

Re: Torre di Hanoi ricorsione

MessaggioInviato: 21/06/2019, 12:25
da vict85
Ma no, non tutte le funzioni ricorsive sono tail recursive1.

Note

  1. Tra l'altro per capire davvero cosa significa questa ottimizzazione dovresti capire prima la calling convention (insomma a livello di istruzioni del processore e layout di memoria).

Re: Torre di Hanoi ricorsione

MessaggioInviato: 21/06/2019, 13:12
da ZfreS
Vict, mi dispiace, ma non ho studiato l'argomento a livelli approfonditi, non so cosa significhi tail recursive. Ho letto tanti articoli sulla torre di hanoi ma nessuno che spiegasse passo passo il meccanismo ricorsivo, forse perchè troppo difficile. Ma se la funzione non è tail recursive, allora cos'è. In pratica è come dice axpgn, che una volta chiamata se stessa al caso base continua a eseguire le istruzioni nell'else e solo dopo ritorna alla chiamata precedente?

Re: Torre di Hanoi ricorsione

MessaggioInviato: 23/06/2019, 14:06
da ZfreS
Ho messo delle stampe dopo ogni chiamata alla funzione e dopo le altre cout. In pratica una volta eseguita la prima ricorsioneil codice va avanti poi entra nell'altra ricorsione e gira fino alla fine. Ma per capire meglio mi servirebbe uno schema dei passaggi che fa la funzione con l'ordine delle varie chiamate.

Re: Torre di Hanoi ricorsione

MessaggioInviato: 23/06/2019, 16:02
da vict85
Sinceramente trovo che sia una cosa che devi capire tu. Insomma qui si tratta di capire cosa fa un codice, devi concentrarti sulla sintassi, non sulla teoria delle funzioni ricorsive. Non avrai sempre una guida che ti spiega cosa fa un codice, leggendolo lo dovresti capire da solo. Se hai dubbi su dove ritorni una funzione è un problema di C++, non ha nulla a che fare con la torre di Hanoi. Una funzione ritorna SEMPRE alla funzione che l'ha chiamata (per lo meno dal punto di vista teorico, ci sono eccezioni ma sono legate alle ottimizzazioni del compilatore).

Un codice del tipo:
Codice:
void A()
{
    B();
    C();
    B();
}

fa le seguenti operazioni:
Codice:
inizia A
    inizia B
        esegue contenuto di B
    finisce B e ritorna ad A
    inizia C
        esegue contenuto di C
    finisce C e ritorna ad A
    inizia D
        esegue contenuto di D
    finisce D e ritorna ad A
finisce A e ritorna a chi l'ha chiamata

Applicalo al codice e vedrai l'ordine delle operazioni.

Re: Torre di Hanoi ricorsione

MessaggioInviato: 23/06/2019, 16:35
da vict85
Una volta che ci hai ragionato puoi controllare il ragionamento con questo codice:
Codice:
#include <iostream>
#include <string>

using namespace std;

void hanoi(int n, char from, char to, char other, const string& spaces)
{
   cout << spaces << "Inizia hanoi(n=" << n << ", to=" << to << ", from=" << from << ")" << endl;
   string next_spaces = spaces + "    ";
   if (n == 1)
   {
      cout << next_spaces << "Stampa AZIONE hanoi(n=1, to=" << to << ", from=" << from << ")" << endl;
   }
   else
   {
      hanoi(n - 1, from, other, to, next_spaces);
      cout << "hanoi(n=" << n << ", to=" << to << ", from=" << from << ")" << endl; // per il ritorna a
      cout << next_spaces << "Stampa AZIONE hanoi(n=" << n << ", to=" << to << ", from=" << from << ")" << endl;
      hanoi(n - 1, other, to, from, next_spaces);
      cout << "hanoi(n=" << n << ", to=" << to << ", from=" << from << ")" << endl; // per il ritorna a
   }
   cout << spaces << "Finisce hanoi(n=" << n << ", to=" << to << ", from=" << from << ") e ritorna a ";
}

int main(void)
{
   string s = "";
   hanoi(3, 'a', 'c', 'b', s);
   cout << "main" << endl;
}

Ma prima ragionaci.

Re: Torre di Hanoi ricorsione

MessaggioInviato: 23/06/2019, 17:36
da ZfreS
Ora ho capito bene come funziona. Ti ringrazio Vict per questa lunga e paziente assistenza!