Ricorsione vs Iterazione

[Luc@s]

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



Tnk

[Lardoman]

L'iterazione si usa quando devi ripetere qualcosa ( ad esempio i cicli FOR).

La ricorsione, se non sbaglio, è quando ua funzione al suo interno richiama se stessa. L?esempio classico è quella del fattoriale

Cmq le iterazioni sono molto + usate delle ricorsioni

[Luc@s]

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

Se mi ricrei questa in iterativa ti spiego perche secondo me le ricorsive sono meglio

[Lardoman]

Io non ho detto che le iterazioni sono le migliori. Ci sono casi in cui sono + adatte ,altre no.

Per quando riguarda la funzione che hai postato, perdonami, ma non ho proprio capito cosa dovrebbe ordinare... Puoi spiegarmelo?

Poi c'è una riga che mi è misteriosa:

template<class T>

[Luc@s]

è una funz di ricerca binaria su array.
template<class T> è un template C++

[infinitejustice]

La ricorsione se usata con cervello di evita righe e righe di codice, ma ha il difettuccio di portare via tanta memoria (crea un''istanza' della funzione ogni volta)

A parte il solito esempio di Fibonacci guardati Quicksort, se nn ricordo male è ricorsivo.


Io lo feci all'esame di programmazione, i prof apprezzarono parekkio la cosa rispetto all'iterazione :metallica

[LeleFT]

Qualsiasi codice iterativo è anche riesprimibile in modo ricorsivo (l'iterazione, infatti, si chiama ricorsione di coda) e, (quasi) viceversa.

La ricorsione ha il difetto di portare via memoria, ma ha l'enorme pregio di semplificare la stesura del codice: uno o più casi base e una chiamata ricorsiva, come si fa per le induzioni.

Esistono, tuttavia, dei casi che sono risolvibili esclusivamente tramite ricorsione (almeno, non ho trovato soluzioni iterative): uno, per esempio, è il calcolo del determinante di una matrice di ordine qualsiasi. L'esempio postato da Luc@s anche: una ricerca binaria su di un albero di altezza arbitraria, non è risolvibile (così facilmente) in modo iterativo... puntatori e via dicendo non sono certo un modo semplice di risoluzione del problema.

Il QuickSort è una delle più famose funzioni ricorsive che esistano.

Quicksort (A, p, r) {
   q = Partition(A, p, r);
   QuickSort(A, p, q);
   QuickSort(A, q+1, r);
}

Ciao.

[Luc@s]

lo sto studiando ora sul Sedgewick il quicksort

[iguana13]

A me sembra che invece ogni problema ricorsivo può essere risolto con l'iterazione.
E' abbastanza complicato perchè devi crearti tu uno stack.



P.S. Facciamo 1 bel thread sugli algoritmi di ordinamento?

[Luc@s]

Originariamente inviato da iguana13


P.S. Facciamo 1 bel thread sugli algoritmi di ordinamento?

Ottima idea.
Partiamo dal Bubble.
Poi segnalalo al Mod e lo mettiamo tra le pillole