Salve a tutti.
Nel preparare un esame universitario , mi sono imbattuto nella Ricorsività multipla.
Il concetto di CHIAMATA RICORSIVA , nel caso di 1 singola funzione mi è chiaro .
Quello che non mi è chiaro è : come si comporta il compilatore passo per passo nel caso in cui nel corpo di una certa funzione ci siano più chiamate a sé stessa.
#include <stdio.h>
#define DISCHI 100
int mossa; //la definisco come variabile globale per usarla anche nella funzione
void hanoi(int n_dischi, char orig, char dest , char aus);
//dove orig è il piolo da dove prendo i dischi, dest dove voglio spostarli, aus come ausilio
int main()
{
mossa=0; //la inizializzo per il sottoprogramma hanoi
printf("Risoluzione torre di Hanoi\n");
printf("Numero di dischi inseriti: %d\n\n",DISCHI);
hanoi(DISCHI,'A','C','B');
/*al sottoprogramma hanoi devo passare:
* 1) Il numero di dischi
* 2) Il nome del piolo di origine (dove iniziano tutti i dischi)
* 3) Il nome del piolo di arrivo (dove arrivano tutti i dischi)
* 4) Il nome del piolo di ausilio */
//N.B. Non confondere i parametri che stai passando ora, con quelli nel sottoprogramma.
//Nel main passi i valori effettivi del problema, mentre nel sottoprogramma passerai
//i valori risolutivi della ricorsione. Nel main il campo orig vuole il punto di partenza del problema
//il campo dest vuole dove voglio spostare tutti i dischi.
//Invece nel sottoprogramma il campo orig cambierà di significato a seconda della risoluzione
//della ricorsione
}
void hanoi(int n_dischi, char orig, char dest, char aus)
{
if (n_dischi==1)
{
mossa++;
printf("%d) Sposta disco da %c a %c\n", mossa, orig, dest);
}
else
{
hanoi(n_dischi-1,orig,aus,dest);
//cioè voglio spostare n-1 dischi da Origine a Ausilio usando come intermezzo Destinazione
hanoi(1,orig,dest,aus);
//cioè voglio spostare 1 disco da Origine a Destinazione
hanoi(n_dischi-1,aus,dest,orig);
//sposto infine gli n-1 dischi dall'Ausilio in Destinazione usando l'Origine come intermezzo
}
}
Da un punto di vista teorico mi è chiaro qual è la sequenza di azioni base da compiere per portare ad es. 3 dischi dal piolo origine al piolo destinazione , utilizzando il piolo intermedio.
Il tutto rispettando le condizioni di :
1) spostare 1 solo disco per volta
2)non spostare dischi di diametro maggiore su dischi di diametro minore.
Tuttavia, quando vado a simulare il programma "su carta" passo passo \ Chiamata ricorsiva dopo chiamata ricorsiva arrivo a conclusioni errate.
Nello specifico ho:
1) nel main() la CHIAMATA alla funzione hanoi()
2) a questo punto entro con n=3 nel sottoprogramma , eseguo il Controllo , salto nell'else e faccio la CHIAMATA alla 1° funzione() nell'else
ovvero hanoi(2,orig,aus,dest);
3) A questo punto , l'esecuzione per n=3 si blocca in attesa che sia completata la CHIAMATA RICORSIVA di quella funzione
E si ha che: Chiamare hanoi(2,orig,aus,dest); significa rientrare nello stesso sottoprogramma .
Quindi eseguo il Controllo if(n==1) ? NO perché siamo entrati con n=2 e salto all'else (di questa che in memoria è una replica della funzione precedente).
Ora nell'else mi ritrovo di nuovo ad eseguire la 1° funzione ovvero hanoi(n_dischi-1,orig,aus,dest);
che in questo casos sarò hanoi(1,orig,aus,dest);
4) A questo punto l'esecuzione di quel secondo stage (per n=2) si blocca in attesa che sia terminata la chiamata ad hanoi(1,orig,aus,dest);
--> di nuovo rientro nel sottoprogramma ma questa volta con n=1 quindi questa volta quel 1° check è verificato.
PROBLEMA: avendo fatto giocare il ruolo di "piolo destinazione" al "piolo ausiliario" , quell'istruzione:
printf("%d) Sposta disco da %c a %c\n", mossa, orig, dest);
mi dovrebbe stampare "sposta disco da origine ad ausiliario"//modo simbolico per spostare 1 disco da ... a...
Tuttavia , nella soluzione , mi si dice che la 1° Azione BASE , dev'essere quella di spostare il primo disco da origine a destinazione H_o,d(1)
ed io invece mi trovo H_o,i(1).
Soluzione: