[C] - funzione ricorsiva

[tonno16]

ciao a tutti. Ho un problema nel capire le funzioni ricorsive.
un problema molto carino che già bene su c è proprio il gioco delle torri di hanoi.

l'algoritmo per la risoluzione consiste in tre punti:

1 trasferire n dischi dal paletto from al paletto to, usando temp come paletto temporaneo.

2 spostare n-1 dischi dall’origine alla sosta temporanea

3 spostare il disco n-esimo dall’origine alla destinazione

negli appunti che ho sotto mano il codice è:

void transfer (int n, char from, char to, char temp) {

if(n==0) return;
else {
transfer (n-1, from, temp, to);

printf(“Sposta il disco %d da %c a %c\n”, n, from, to);

transfer (n-1, temp, to, from);
}
}

e poi vabbe c'è una main dove viene richiamata transfer(n, paloA,paloB,paloC)


quello che non capisco è:
il punto uno -> trasferire n dischi dal paletto from al paletto to, usando temp come paletto temporaneo.

sotto forma di codice diventa: transfer (n-1, from, temp, to);

PERCHè??? qualcuno che mi spiega questa roba???

[sottovento]

ciao a tutti. Ho un problema nel capire le funzioni ricorsive.
un problema molto carino che già bene su c è proprio il gioco delle torri di hanoi.

l'algoritmo per la risoluzione consiste in tre punti:

1 trasferire n dischi dal paletto from al paletto to, usando temp come paletto temporaneo.

2 spostare n-1 dischi dall’origine alla sosta temporanea

3 spostare il disco n-esimo dall’origine alla destinazione

negli appunti che ho sotto mano il codice è:

void transfer (int n, char from, char to, char temp) {

if(n==0) return;
else {
transfer (n-1, from, temp, to);

printf(“Sposta il disco %d da %c a %c\n”, n, from, to);

transfer (n-1, temp, to, from);
}
}

e poi vabbe c'è una main dove viene richiamata transfer(n, paloA,paloB,paloC)


quello che non capisco è:
il punto uno -> trasferire n dischi dal paletto from al paletto to, usando temp come paletto temporaneo.

sotto forma di codice diventa: transfer (n-1, from, temp, to);

PERCHè??? qualcuno che mi spiega questa roba???

Prima di tutto: hai provato ad eseguirlo? Il caso piu' semplice da studiare e' quello con n=3 (per n inferiori non vedi bene tutti i passaggi, mentre per quelli superiori cominciano ad essercene troppi).

Altra premessa: visto com'e' scritto il codice, e' evidente che piu' grande e' il disco, maggiore sara' il numero che lo rappresenta. Sembra una considerazione banale ma non lo e'. Quindi, se hai 3 dischi, in partenza li dovrai immaginare impilati nella posizione from e leggerai la sequenza 1,2,3 a partire dall'alto.

Come sai, per usare la ricorsione
- devi sapere risolvere i casi base (uno o piu' casi base, a seconda del problema). Nel tuo caso, il caso base e' uno solo;
- devi assumere di conoscere la soluzione per i casi n-1, n-2, .... giu' fino al caso base.

Date queste assunzioni, se riesci ad esprimere la soluzione per il passo n in termini di passi n-1, n-2, .... allora hai vinto!

Proviamoci:

Base della ricorsione: n=0. Questo caso e' facile, visto che se non hai alcun disco non devi fare nulla. Il tuo codice si ferma qui, ed e' piu' che sufficiente.
Volendo essere piu' espliciti (solo per cercare di capire meglio l'esercizio) potremmo mettere anche il caso base n=1: in questo caso, avendo un solo disco, la nostra soluzione sarebbe quella di spostare il disco da from a to ed avremmo finito. Questo caso base si risolverebbe con una
printf(“Sposta il disco %d da %c a %c\n”, 1, from, to);
Semplice, no? Visto come funziona il gioco, potremmo mettere anche il caso base in cui n=2 (cioe' due dischi), spostando il primo disco (il piu' piccolo) sul piolo temporaneo, il secondo disco (il piu' grande) nella posizione finale e poi il piu' piccolo dal temporaneo al finale, proprio sopra il piu' grande:
printf(“Sposta il disco %d da %c a %c\n”, 1, from, temp);
printf(“Sposta il disco %d da %c a %c\n”, 2, from, to);
printf(“Sposta il disco %d da %c a %c\n”, 1, temp, to);

Quante condizioni di base ti servono? Ovviamente ti ho fatto vedere che ne puoi aggiungere quante ne vuoi, anche se risulterebbero ridondanti.
Puoi facilmente immaginare che il numero minimo di condizioni di base e' legato a quanti valori precedenti devi guardare per risolvere il tuo problema al caso n: se riesci ad esprimere (come in questo caso) la tua soluzione al caso n in termini semplicemente di n-1, un solo caso base e' sufficiente. Altrimenti te ne serviranno tante quanto hai deciso di guardare indietro: se usi n-2 allora ne avrai almeno due e cosi' via.


Passo ricorsivo: il piatto forte :D
Riesci ad esprimere la soluzione al passo n in termini dei passi precedenti?
Ovviamente si: se devi spostare n dischi dal piolo from al to
- sposterai n-1 dischi dal piolo from al piolo temp;
- sposterai il disco n dal piolo from al piolo to;
- infine, sposterai i precedenti n-1 dischi dal piolo temp al piolo to

Siccome hai supposto di saper fare tutti gli spostamenti di dischi n-1, n-2,... allora puoi usare direttamente la tua funzione.
Quindi, il passo n si riduce a quanto hai scritto:

transfer (n-1, from, temp, to);
printf(“Sposta il disco %d da %c a %c\n”, n, from, to);
transfer (n-1, temp, to, from);