Ricorsione vs Iterazione

[Luc@s]

Quando conviene usare l'iterazione e quando la ricorsione???



Tnk

[cionci]

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...

[Luc@s]

in genere quando è consigliata la ricorsione e quando proprio nn va(nrgli algoritmi)??

[cionci]

Dipende dall'algoritmo
Se nella stesura su foglio c'è una ricorsione allora puoi scriverlo con la ricorsione

[kingv]

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

[cionci]

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

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]

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

[cionci]

Originariamente inviato da Luc@s
Come iterativo sarebbe + semplice o performante ???

Quasi mai un algoritmo ricorsivo riportato ad iterativo è più semplice...magari più performante...

[Luc@s]

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?

[cionci]

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);
}

[leomagic]

considera che lo stack è di circa 220 funzioni..io ho avuto dei problemi con le ricorsive proprio x lo stack.

[cionci]

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...

[Angus]

1. è sempre possibile trasformare una ricorsione?

2. x trasformare una ricorsione è sempre necessaria una pila?

[cionci]

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)...

[soalle]

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...

[soalle]

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]

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?

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

[Angus]

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.

[/\/\@®¢Ø]

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.