Torre di Hanoi ricorsione

[oleg.fresi]

Buongiorno! Sto studiando la torre di Hanoi e pur avendo capito il meccanismo che le sta dietro non riesco a capire il funzionamento del codice. Ho difficoltà a capire come funziona la ricorsione in questo problema. Ciò che non capisco dal codice è come fa l'algoritmo a spostare i dischi sul piolo b senza che b appaia nelle cout. Sembra che b sia un parametro che viene passato e non utilizzato, mentre poi compare nella stampa dei passaggi. Potreste farmi vedere passo dopo passo come opera la ricorsione con tre dischi? Grazie in anticipo!

void hanoi(int n, char a, char c, char b)
{
	if (n == 1)
		cout << a << " - " << c << endl;
	else
	{
		hanoi(n - 1, a, b, c);
		cout << a << " - " << c << endl;
		hanoi(n - 1, b, c, a);
	}
}

[axpgn]

Ma che significa?
L'else viene eseguito tutto le volte che la funzione viene chiamata con $n>1$ e viene eseguito TUTTO.

[oleg.fresi]

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.

[vict85]

Ma no, non tutte le funzioni ricorsive sono tail recursive[nota]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).[/nota].

[oleg.fresi]

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?

[oleg.fresi]

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.

[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:

void A()
{
    B();
    C();
    B();
}

fa le seguenti operazioni:

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]

Una volta che ci hai ragionato puoi controllare il ragionamento con questo 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.

[oleg.fresi]

Ora ho capito bene come funziona. Ti ringrazio Vict per questa lunga e paziente assistenza!