Luc@s
21-01-2004, 14:00
Quando conviene usare l'iterazione e quando la ricorsione???
Tnk
Tnk
View Full Version : Ricorsione vs Iterazione
cionci
21-01-2004, 14:09
Con la ricorsione è solitamente più semplice implementare gli algoritmi che ne necessitano...
Scrivendo algoritmi ricorsivi in modo iterativo si possono ottenere programmi più veloci (se implementati decentemente) che con la ricorsione (prologo ed epilogo di una chiamata a funzione portano via diverso tempo)...
Considera che una serie ricorsiva troppo lunga può portare ad esaurire lo stack...quindi in teoria ogni programma che adotta la ricorsione può nascondere questo difetto strutturale...
Scrivendo algoritmi ricorsivi in modo iterativo si possono ottenere programmi più veloci (se implementati decentemente) che con la ricorsione (prologo ed epilogo di una chiamata a funzione portano via diverso tempo)...
Considera che una serie ricorsiva troppo lunga può portare ad esaurire lo stack...quindi in teoria ogni programma che adotta la ricorsione può nascondere questo difetto strutturale...
Luc@s
21-01-2004, 14:16
in genere quando è consigliata la ricorsione e quando proprio nn va(nrgli algoritmi)??
cionci
21-01-2004, 14:23
Dipende dall'algoritmo ;)
Se nella stesura su foglio c'è una ricorsione allora puoi scriverlo con la ricorsione ;)
Se nella stesura su foglio c'è una ricorsione allora puoi scriverlo con la ricorsione ;)
kingv
21-01-2004, 14:23
Originariamente inviato da Luc@s
in genere quando è consigliata la ricorsione e quandoproprio nn va??
quando un leggero peggioramento prestazionale e' accettabile (ovvero quasi sempre), generalemente il codice che si ottiene e' così piu' semplice da capire rispetto alla versione iterativa che non vale la pena farlo in altro modo.
mi e' capitato varie volte di scrivere funzioni ricorsive, una volta ho provato a modificarne una in iterativa e ci ho ricavato solo un gran mal di testa :D
in genere quando è consigliata la ricorsione e quandoproprio nn va??
quando un leggero peggioramento prestazionale e' accettabile (ovvero quasi sempre), generalemente il codice che si ottiene e' così piu' semplice da capire rispetto alla versione iterativa che non vale la pena farlo in altro modo.
mi e' capitato varie volte di scrivere funzioni ricorsive, una volta ho provato a modificarne una in iterativa e ci ho ricavato solo un gran mal di testa :D
cionci
21-01-2004, 14:25
Originariamente inviato da kingv
mi e' capitato varie volte di scrivere funzioni ricorsive, una volta ho provato a modificarne una in iterativa e ci ho ricavato solo un gran mal di testa :D
Vero...ed a volte la versione iterativa diventa più dispendiosa di quela ricorsiva (proprio perchè la ricorsione semplifica tante cose e ci fa risparmiare tante varibili temporanee)...
mi e' capitato varie volte di scrivere funzioni ricorsive, una volta ho provato a modificarne una in iterativa e ci ho ricavato solo un gran mal di testa :D
Vero...ed a volte la versione iterativa diventa più dispendiosa di quela ricorsiva (proprio perchè la ricorsione semplifica tante cose e ci fa risparmiare tante varibili temporanee)...
Luc@s
21-01-2004, 14:29
Questo cod per esempio:
/*
Ricerca binaria
Funzia su array ordinati precendentemente
*/
template<class T>
void bin_search(const T a[], int first, int last, T target, bool& found, int& index)
{
int centro;
if (first > last)
found = false;
else
{
centro = (first + last)/2;
if (target == a[centro]) // META
{
found = true;
index = centro;
}
// PARTE SINISTRA
else if (target < a[centro]) bin_search(a, first, centro - 1, target, found, index);
// PARTE DESTRA
else if (target > a[centro]) bin_search(a, centro + 1, last, target, found, index);
}
}
Come iterativo sarebbe + semplice o performante ???
Tnk
/*
Ricerca binaria
Funzia su array ordinati precendentemente
*/
template<class T>
void bin_search(const T a[], int first, int last, T target, bool& found, int& index)
{
int centro;
if (first > last)
found = false;
else
{
centro = (first + last)/2;
if (target == a[centro]) // META
{
found = true;
index = centro;
}
// PARTE SINISTRA
else if (target < a[centro]) bin_search(a, first, centro - 1, target, found, index);
// PARTE DESTRA
else if (target > a[centro]) bin_search(a, centro + 1, last, target, found, index);
}
}
Come iterativo sarebbe + semplice o performante ???
Tnk
cionci
21-01-2004, 14:32
Originariamente inviato da Luc@s
Come iterativo sarebbe + semplice o performante ???
Quasi mai un algoritmo ricorsivo riportato ad iterativo è più semplice...magari più performante...
Come iterativo sarebbe + semplice o performante ???
Quasi mai un algoritmo ricorsivo riportato ad iterativo è più semplice...magari più performante...
Luc@s
21-01-2004, 14:34
Originariamente inviato da cionci
Quasi mai un algoritmo ricorsivo riportato ad iterativo è più semplice...magari più performante...
nel caso della funz sopra..............sarebbe molto + performante la vers iterativa?
Quasi mai un algoritmo ricorsivo riportato ad iterativo è più semplice...magari più performante...
nel caso della funz sopra..............sarebbe molto + performante la vers iterativa?
cionci
21-01-2004, 15:50
La differenza dovebbe essere poca, ma comunque a favore della versione iterativa (non l'ho provata)...
template<class T>
void bin_search(const T a[], int first, int last, T target, bool& found, int& index)
{
found = false;
if(last < first) return;
do {
int centro;
centro = (first + last)/2;
if (target == a[centro]) // META
{
found = true;
index = centro;
break;
}
// PARTE SINISTRA
else if (target < a[centro])
last = centro-1;
// PARTE DESTRA
else if (target > a[centro])
first = centro+1;
} while (first > last);
}
template<class T>
void bin_search(const T a[], int first, int last, T target, bool& found, int& index)
{
found = false;
if(last < first) return;
do {
int centro;
centro = (first + last)/2;
if (target == a[centro]) // META
{
found = true;
index = centro;
break;
}
// PARTE SINISTRA
else if (target < a[centro])
last = centro-1;
// PARTE DESTRA
else if (target > a[centro])
first = centro+1;
} while (first > last);
}
leomagic
21-01-2004, 21:27
considera che lo stack è di circa 220 funzioni..io ho avuto dei problemi con le ricorsive proprio x lo stack.
cionci
22-01-2004, 08:57
Quella ricorsiva potresti farla così:
/*
Ricerca binaria
Funzia su array ordinati precendentemente
*/
template<class T>
void bin_search(const T *a, int start, int size, const T &target, bool& found, int& index)
{
int centro;
if (start < 0 || size <= 0 || a == NULL)
found = false;
else
{
centro = (size)/2;
if (target == a[centro]) // META
{
found = true;
index = centro + first;
}
// PARTE SINISTRA
else if (target < a[centro]) bin_search(&a[centro-1], first, centro, target, found, index);
// PARTE DESTRA
else bin_search(&a[centro+1], first + centro + 1, size - centro - 1, target, found, index);
}
}
E' un po' più complessa, ma dovrebbe andare bene...e dovrebbe perdere diversi svantaggi prestazionali (come il passaggio per valore del vettore)...
Ovviamente bisogna fare un po' di attenzione sul primo parametro...
/*
Ricerca binaria
Funzia su array ordinati precendentemente
*/
template<class T>
void bin_search(const T *a, int start, int size, const T &target, bool& found, int& index)
{
int centro;
if (start < 0 || size <= 0 || a == NULL)
found = false;
else
{
centro = (size)/2;
if (target == a[centro]) // META
{
found = true;
index = centro + first;
}
// PARTE SINISTRA
else if (target < a[centro]) bin_search(&a[centro-1], first, centro, target, found, index);
// PARTE DESTRA
else bin_search(&a[centro+1], first + centro + 1, size - centro - 1, target, found, index);
}
}
E' un po' più complessa, ma dovrebbe andare bene...e dovrebbe perdere diversi svantaggi prestazionali (come il passaggio per valore del vettore)...
Ovviamente bisogna fare un po' di attenzione sul primo parametro...
Angus
22-01-2004, 10:15
1. è sempre possibile trasformare una ricorsione?
2. x trasformare una ricorsione è sempre necessaria una pila?
2. x trasformare una ricorsione è sempre necessaria una pila?
cionci
22-01-2004, 10:33
Originariamente inviato da Angus
1. è sempre possibile trasformare una ricorsione?
In linea di massima direi che è sempre possibile trasformare una ricorsione in una iterazione...
Originariamente inviato da Angus
2. x trasformare una ricorsione è sempre necessaria una pila?
Lo stack di cui si parlava è quella parte di memoria del programma dedicata alle operazioni push e pop ed a contenere l'indirizzo di ritorno da una funzione...
Quando si chiama una funzione l'istruzione assembler che viene usata è CALL...
CALL comporta il salvataggio dell'istruction pointer dell'istruzione successiva alla CALL all'interno dello stack...
L'operazione di RET (che è l'utima istruzione eseguita da una chiamata a funzione) comporta l'inizializzazione del registro istruction pointer con il valore letto dallo stack e la rimozione del suddetto valore dallo stack...
Lo stack solitamente non è molto grande (anche se è possibile impostarlo in fase di compilazione) ed annidandosi molte richieste ricorsive prima o poi si può esaurire (il programma crasha)...
1. è sempre possibile trasformare una ricorsione?
In linea di massima direi che è sempre possibile trasformare una ricorsione in una iterazione...
Originariamente inviato da Angus
2. x trasformare una ricorsione è sempre necessaria una pila?
Lo stack di cui si parlava è quella parte di memoria del programma dedicata alle operazioni push e pop ed a contenere l'indirizzo di ritorno da una funzione...
Quando si chiama una funzione l'istruzione assembler che viene usata è CALL...
CALL comporta il salvataggio dell'istruction pointer dell'istruzione successiva alla CALL all'interno dello stack...
L'operazione di RET (che è l'utima istruzione eseguita da una chiamata a funzione) comporta l'inizializzazione del registro istruction pointer con il valore letto dallo stack e la rimozione del suddetto valore dallo stack...
Lo stack solitamente non è molto grande (anche se è possibile impostarlo in fase di compilazione) ed annidandosi molte richieste ricorsive prima o poi si può esaurire (il programma crasha)...
soalle
22-01-2004, 11:17
Originariamente inviato da leomagic
considera che lo stack è di circa 220 funzioni..io ho avuto dei problemi con le ricorsive proprio x lo stack.
Non significativo... dipende dal numero di parametri passati alla funzione che vengono messi sullo stack per poterli andare prendere dalla funzione...
considera che lo stack è di circa 220 funzioni..io ho avuto dei problemi con le ricorsive proprio x lo stack.
Non significativo... dipende dal numero di parametri passati alla funzione che vengono messi sullo stack per poterli andare prendere dalla funzione...
soalle
22-01-2004, 11:18
Poi non dimentichiamoci che alcuni linguaggi di programmazione (sicuramente il prolog... ma credo anche il c / c++) ottimizzano la chiamata a funzione ricorsive tail utilizzando lo stesso record di attivazione...
Angus
22-01-2004, 11:24
Originariamente inviato da cionci
In linea di massima direi che è sempre possibile trasformare una ricorsione in una iterazione...
Lo stack di cui si parlava è quella parte di memoria del programma dedicata alle operazioni push e pop ed a contenere l'indirizzo di ritorno da una funzione...
Quando si chiama una funzione l'istruzione assembler che viene usata è CALL...
CALL comporta il salvataggio dell'istruction pointer dell'istruzione successiva alla CALL all'interno dello stack...
L'operazione di RET (che è l'utima istruzione eseguita da una chiamata a funzione) comporta l'inizializzazione del registro istruction pointer con il valore letto dallo stack e la rimozione del suddetto valore dallo stack...
Lo stack solitamente non è molto grande (anche se è possibile impostarlo in fase di compilazione) ed annidandosi molte richieste ricorsive prima o poi si può esaurire (il programma crasha)...
Riformulo la domanda numero 2:
2. Per trasformare un algoritmo che utilizzi una ricorsione in un algoritmo che utilizzi una iterazione, quest'ultimo deve essere dotato di istruzioni atte a salvare ad ogni iterazione lo stato corrente in una struttura dello heap che faccia da stack, oppure questo potrebbe essere solo un modo standard di effettuare la trasformazione dalla versione ricorsiva a quella iterativa di un algoritmo?
In linea di massima direi che è sempre possibile trasformare una ricorsione in una iterazione...
Lo stack di cui si parlava è quella parte di memoria del programma dedicata alle operazioni push e pop ed a contenere l'indirizzo di ritorno da una funzione...
Quando si chiama una funzione l'istruzione assembler che viene usata è CALL...
CALL comporta il salvataggio dell'istruction pointer dell'istruzione successiva alla CALL all'interno dello stack...
L'operazione di RET (che è l'utima istruzione eseguita da una chiamata a funzione) comporta l'inizializzazione del registro istruction pointer con il valore letto dallo stack e la rimozione del suddetto valore dallo stack...
Lo stack solitamente non è molto grande (anche se è possibile impostarlo in fase di compilazione) ed annidandosi molte richieste ricorsive prima o poi si può esaurire (il programma crasha)...
Riformulo la domanda numero 2:
2. Per trasformare un algoritmo che utilizzi una ricorsione in un algoritmo che utilizzi una iterazione, quest'ultimo deve essere dotato di istruzioni atte a salvare ad ogni iterazione lo stato corrente in una struttura dello heap che faccia da stack, oppure questo potrebbe essere solo un modo standard di effettuare la trasformazione dalla versione ricorsiva a quella iterativa di un algoritmo?
cionci
22-01-2004, 11:33
Con una struttura dati simile a stack con i tutti i valori necessari ad ogni pass dell'algoritmo la trasformazione dovrebbe essere sempre possibile...e direi che è un metodo abbastanza standard...ma sicuramente modificare l'algoritmo ad hoc per essere iterativo rende il programma più corto e più veloce...
Angus
22-01-2004, 11:47
Originariamente inviato da cionci
...ma sicuramente modificare l'algoritmo ad hoc per essere iterativo rende il programma più corto e più veloce...
ed è lì che si vede il vero programmatore...
grazie cionci per l'attenzione concessami.
...ma sicuramente modificare l'algoritmo ad hoc per essere iterativo rende il programma più corto e più veloce...
ed è lì che si vede il vero programmatore...
grazie cionci per l'attenzione concessami.
/\/\@®¢Ø
22-01-2004, 23:27
Originariamente inviato da Angus
Riformulo la domanda numero 2:
2. Per trasformare un algoritmo che utilizzi una ricorsione in un algoritmo che utilizzi una iterazione, quest'ultimo deve essere dotato di istruzioni atte a salvare ad ogni iterazione lo stato corrente in una struttura dello heap che faccia da stack, oppure questo potrebbe essere solo un modo standard di effettuare la trasformazione dalla versione ricorsiva a quella iterativa di un algoritmo?
Dipende dall'algoritmo considerato. Come detto precedentemente da soalle, certi compilatori riescono a volte ad eliminare la ricorsione da una funzione che chiami se' stessa quando la chiamata ricorsiva e' proprio l'ultima operazione. In tal caso infatti il compilatore riesce a riciclare il frame di attivazione della funzione piu' volte.
Piu' in generale, non tutte le funzioni ricorsive richiedono spazio proporzionale al numero di passi, e quindi non necessitano della pila.
Riformulo la domanda numero 2:
2. Per trasformare un algoritmo che utilizzi una ricorsione in un algoritmo che utilizzi una iterazione, quest'ultimo deve essere dotato di istruzioni atte a salvare ad ogni iterazione lo stato corrente in una struttura dello heap che faccia da stack, oppure questo potrebbe essere solo un modo standard di effettuare la trasformazione dalla versione ricorsiva a quella iterativa di un algoritmo?
Dipende dall'algoritmo considerato. Come detto precedentemente da soalle, certi compilatori riescono a volte ad eliminare la ricorsione da una funzione che chiami se' stessa quando la chiamata ricorsiva e' proprio l'ultima operazione. In tal caso infatti il compilatore riesce a riciclare il frame di attivazione della funzione piu' volte.
Piu' in generale, non tutte le funzioni ricorsive richiedono spazio proporzionale al numero di passi, e quindi non necessitano della pila.
/\/\@®¢Ø
22-01-2004, 23:29
Originariamente inviato da cionci
Con una struttura dati simile a stack con i tutti i valori necessari ad ogni pass dell'algoritmo la trasformazione dovrebbe essere sempre possibile...e direi che è un metodo abbastanza standard...ma sicuramente modificare l'algoritmo ad hoc per essere iterativo rende il programma più corto e più veloce...
Sono d'accordo sul piu' veloce, non sul piu' corto. Anzi, il non poter sfruttare la "pila naturale" delle chiamate ricorsive obbliga ad introdurre strutture dati ulteriori (provate voi a fare le operazioni su alberi in forma iterativa :D)
Con una struttura dati simile a stack con i tutti i valori necessari ad ogni pass dell'algoritmo la trasformazione dovrebbe essere sempre possibile...e direi che è un metodo abbastanza standard...ma sicuramente modificare l'algoritmo ad hoc per essere iterativo rende il programma più corto e più veloce...
Sono d'accordo sul piu' veloce, non sul piu' corto. Anzi, il non poter sfruttare la "pila naturale" delle chiamate ricorsive obbliga ad introdurre strutture dati ulteriori (provate voi a fare le operazioni su alberi in forma iterativa :D)
cionci
23-01-2004, 01:54
Più corto rispetto ad usare uno stack reale per la versione iterativa...
/\/\@®¢Ø
23-01-2004, 09:28
Pardon, avevo capito male .
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.