Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Salve, volevo chiedervi se qualcuno conosce qualche metodo per imparare ad utilizzare la ricorsione, sono tre mesi ormai che ci sbatto la testa sopra, sopratutto con la risoluzione del problema delle Torri di Hanoi (in pratica devo svolgere un esercizio che mi dice di realizzare un programma capace di indicarti le mosse minime necessarie per la risoluzione del gioco, ci ho perso la salute ma non sono venuto a capo di niente, così ho cercato l'algoritmo esatto in rete, ho ricostruito passaggio per passaggio cosa fa il programma, ma non sono comunque riuscito a capire perché ottiene il risultato esatto e sopratutto, come avrei dovuto arrivarci), qualcuno ha qualche consiglio da darmi, qualche metodo per riuscire a padroneggiare questa tecnica di programmazione?
Poi, io fino a questo momento, prima di svolgere gli esercizi ho sempre utilizzato lo pseudo-codice come consigliatomi nel testo, ma non riesco a scriverne uno esatto se non dopo che ho già risolto il problema nella mia mente, quindi penso di starlo utilizzando male, in quanto altrimenti non sarebbe più sensato scriverlo direttamente il programma? Aspetto con impazienza quel grand'uomo che mi illumini la via
Ps. Il manuale che utilizzo è C corso completo di programmazione della Deitel, ho risolto tutti gli esercizi precedenti con successo, anche se quando mi confronto con gli esercizi svolti dagli altri, molte volte risulta che io ho utilizzato qualche variabile o passaggio in più.
Ultima modifica effettuata da Davrock il 14/01/2010 alle 16:18
Una funzione si dice ricorsiva quando essa richiama se stessa nel proprio corpo. Il classico esempio è il calcolo del fattoriale:
Codice sorgente - presumibilmente C/C++
//Poniamo n > 0 per ipotesi
int fact(int n)
{
return (n < 2) ? 1 : n * fact(n - 1);
}
Una volta raggiunto il punto in cui la funzione richiama se stessa, il controllo del programma passa a quest'ultima, la quale elabora, ancora, richiamando fact e così via. Risulta che per calcolare 4!, essendo 4! = 4 * 3!, bisogna conoscere 3! e per far questo bisogna conoscere 2! e per far questo bisogna conoscere 1!, che è 1 per definizione.
Ti sarà utile costruire il grafico delle chiamate a funzione.
In sostanza, le funzioni ricorsive risolvono solo il problema di base e costruiscono tutti i problemi più grandi basandosi su quello. Non so come rendere la spiegazione più semplice, e non saprei indicarti una risorsa particolarmente efficacie su questo argomento. Infatti, le funzioni ricorsive non sono nulla di speciale: sono solo un caso particolare della chiamata a funzione, un argomento elementare che conoscerai benissimo. Dato che la chiamata a funzione viene eseguita sempre allo stesso modo, dovresti saper sviscerare il problema... senza problemi XD
Grazie per la risposta, l'esercizio che hai postato per esempio sono riuscito a risolverlo, perché la logica che ci sta dietro è semplice, il fatto è nei casi più complessi ho proprio difficoltà a figurami il controllo del programma e quindi giungere spontaneamente a una soluzione con questo metodo, nel caso delle torri mi sfugge anche la logica, in quanto ho ricostruito passo per passo il procedimento che effettivamente attraverso le ricorsioni, nonostante qualsiasi numero di dischi tu indichi alla fine ti da veramente le mosse minime corrette per risolvere il gioco, per essere più chiaro posto l'argoritmo:
Codice sorgente - presumibilmente C++
#include <stdio.h>
void muoviUnDisco(int sorgente, int destinazione)
{
printf(" muovi un disco da %2d a %2d\n", sorgente, destinazione);
}/* muoviUnDisco */
void muovi(int n, int sorgente, int destinazione, int ausiliario)
{
if(n == 1)
muoviUnDisco(sorgente, destinazione);
else{
muovi(n-1, sorgente, ausiliario, destinazione);
muoviUnDisco(sorgente, destinazione);
muovi(n - 1, ausiliario, destinazione, sorgente);
}
}/* muovi */
int main(void)
{
int dischi;/* numero di dischi */
int s, d;/* pali sorgente e destinazione */
printf("Numero di dischi? ");
scanf("%d", &dischi);
printf("Palo sorgente? [1, 2 o 3] ");
scanf("%d", &s);
printf("Palo destinazione? [1, 2 o 3] ");
scanf("%d", &d);
printf("\nIl palo ausiliario e` %d\n", 6 - d - s);
printf("Per %d dischi le mosse richieste sono:\n", dischi);
muovi(dischi, s, d, 6 - d - s);
putchar('\n');
return0;
}/* main */
ma inutile non ci arrivo, per questo mi chiedevo se c'era un metodo per esemplificare la visione di un problema che richiede la ricorsione, anche perché si presupporrebbe che uno dovrebbe arrivarci da solo attraverso lo pseudocodice se non ci si arriva spontaneamente.
E pensare che l'esercizio dopo mi chiede di risolverlo in maniera iterativa
Ultima modifica effettuata da netarrow il 14/01/2010 alle 17:37
Ti do un avvertimento: un conto è capire la ricorsione, un conto è capire il problema delle torri di hanoi.
Capire la prima cosa è fondamentale, la seconda completamente inutile.
Quindi ti consiglio di stare attento a non perdere tempo a capire il problema delle torri di hanoi se hai capito l'aspetto tecnico della ricorsione.
Altra cosa su cui devo avvertirti: non è per niente scontato che uno ci arrivi da solo alla soluzione delle torri di hanoi, per non parlare poi delle soluzioni iterative dei problemi ricorsivi che sono generalmente meno intuitive.
Cmq ti posto l'algoritmo in ruby che è molto simile a pseudo codice e più compatto del C ma funziona nella stessa maniera:
Codice sorgente - presumibilmente Delphi
def hanoi(n, da, app, a)
if n ==1
puts "da #{da} a #{a}"
else
hanoi(n -1, da, a, app)
puts "da #{da} a #{a}"
hanoi(n - 1, app, da, a)
end
end
Il suggerimento che posso darti è di cercare su google qualche gioco sulle torri di hanoi dove devi risolvere tu il problema spostando col mouse i dischi per entrare un pò nell'ottica.
A questo punto provi a giocare tu seguendo le mosse dell'algoritmo e cerchi di capire il trucco.
Cmq ti ripeto, non perderci troppo tempo.
Ultima modifica effettuata da netarrow il 14/01/2010 alle 17:55
Si, fondamentalmente ho capito la ricorsione, in quanto non è altro che chiamare una funzione all'interno di se stessa, con argomenti che rappresentano una versione sempre più piccola del problema principale, fino a convergere in quello che viene detto caso base, il quale innesca una serie di restituzioni a catena, dall'ultima funzione chiamata, alla prima.
Tenendo naturalmente conto che lo stack delle chiamate di funzione ha una capienza limitata e che troppe chiamate potrebbero generare il così detto "overflow".
La teoria c'è è la pratica che mi manca, quindi tu mi consigli di lasciare perdere per il momento la risoluzione delle Torri di Hanoi? Il problema è che andando avanti nel libro gli esercizi si fanno più complicati e non vorrei che non sapendo fare questo non posso farcela con gli altri, ma d'altro canto mi sono sbattuto veramente tanto e ho già fatto quello che hai detto tu, ho giocato e rigiocato ma basta una svista per trovarsi di colpo ingarbugliati tentando di risolverlo nel mondo reale, figurarsi provando a scrivere un programma che lo risolve.
Se non l'hai già provato potresti partire dalla fine, cioè invece di giocare al diritto giochi al rovescio, cioè dall'ultima mossa alla prima, così vedi come il problema diventa sempre più grosso, e come per risolvere quello grosso si risolve quallo immediatamente più piccolo.
.