Re: Torre di Hanoi ricorsione

Messaggioda ZfreS » 21/06/2019, 11:33

Mi stai dicendo quindi che una volta spostato il disco in cima, vengono eseguitele istruzioni dell'else anzichè resistuire il controllo alla chiamata precedente?
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1752 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Torre di Hanoi ricorsione

Messaggioda axpgn » 21/06/2019, 11:49

Ma che significa?
L'else viene eseguito tutto le volte che la funzione viene chiamata con $n>1$ e viene eseguito TUTTO.
axpgn
Cannot live without
Cannot live without
 
Messaggio: 13703 di 40641
Iscritto il: 20/11/2013, 22:03

Re: Torre di Hanoi ricorsione

Messaggioda ZfreS » 21/06/2019, 12:04

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.
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1753 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Torre di Hanoi ricorsione

Messaggioda vict85 » 21/06/2019, 12:25

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).
vict85
Moderatore
Moderatore
 
Messaggio: 9737 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: Torre di Hanoi ricorsione

Messaggioda ZfreS » 21/06/2019, 13:12

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?
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1754 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Torre di Hanoi ricorsione

Messaggioda ZfreS » 23/06/2019, 14:06

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.
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1757 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Torre di Hanoi ricorsione

Messaggioda vict85 » 23/06/2019, 16:02

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.
vict85
Moderatore
Moderatore
 
Messaggio: 9739 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: Torre di Hanoi ricorsione

Messaggioda vict85 » 23/06/2019, 16:35

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.
vict85
Moderatore
Moderatore
 
Messaggio: 9740 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: Torre di Hanoi ricorsione

Messaggioda ZfreS » 23/06/2019, 17:36

Ora ho capito bene come funziona. Ti ringrazio Vict per questa lunga e paziente assistenza!
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1758 di 4589
Iscritto il: 22/10/2016, 17:52

Precedente

Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite