Ricorsione e Iterazione?
https://stackoverflow.com/questions/72209
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
C'è un calo di prestazioni se usiamo un ciclo invece di ricorsione, o viceversa in algoritmi in cui entrambi possono servire allo stesso scopo?Ad esempio:Controllare se la stringa e ' un palindromo.Ho visto molti programmatori utilizzando la ricorsione come un mezzo per mostrare quando un semplice iterazione dell'algoritmo può misura la fattura.Fa il compilatore a giocare un ruolo fondamentale nel decidere cosa usare?
Soluzione
È possibile che la ricorsione essere più costoso, a seconda se la funzione ricorsiva è tail ricorsiva (l'ultima riga è chiamata ricorsiva).Ricorsività dovrebbe essere riconosciuti dal compilatore e ottimizzato per la sua iterativo controparte (mantenendo il conciso, chiaro attuazione hai nel tuo codice).
Vorrei scrivere l'algoritmo in modo che rende più senso ed è più chiaro per i poveri ventosa (essere voi stessi o qualcun altro) che deve mantenere il codice in un paio di mesi o anni.Se si esegue in problemi di prestazioni, quindi il profilo di codice, e allora, e solo allora prendete in considerazione l'ottimizzazione spostando su di un processo iterativo di attuazione.Si potrebbe desiderare di guardare in memoization e programmazione dinamica.
Altri suggerimenti
I cicli possono ottenere un guadagno in termini di prestazioni per il vostro programma.La ricorsione può ottenere un miglioramento delle prestazioni per il programmatore.Scegli quello che è più importante nella tua situazione!
Confrontando la ricorsione per iterazione è come paragonare un cacciavite a croce per un cacciavite a testa piatta.Per la maggior parte si potrebbe rimuovere ogni vite con testa a croce con testa piatta, ma non sarebbe più facile se si è usato il cacciavite progettato per la vite di destra?
Alcuni algoritmi appena si prestano per ricorsione causa del modo in cui sono progettati (sequenze di Fibonacci, l'attraversamento di un albero come la struttura, etc.).Ricorsione rende l'algoritmo più sintetica e più facile da capire (e quindi condivisibili e riutilizzabili).
Inoltre, alcuni algoritmi ricorsivi uso "Lazy Evaluation", che li rende più efficienti dei loro iterativo fratelli.Questo significa che fanno solo i costosi calcoli nel momento in cui sono necessari, piuttosto che ogni volta che il ciclo viene eseguito.
Questo dovrebbe essere sufficiente per iniziare.Esaminare alcuni articoli ed esempi per voi.
Link 1: Haskel vs PHP (Ricorsione vs Iterazione)
Ecco un esempio in cui il programmatore deve elaborare un ampio set di dati utilizzando PHP.Egli mostra come sarebbe stato facile affrontare in Haskel utilizzando la ricorsione, ma dato che PHP non aveva modo semplice per ottenere lo stesso metodo, è stato costretto a utilizzare l'iterazione per ottenere il risultato.
http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html
Link 2: Mastering Di Ricorsione
La maggior parte di ricorsione fama negativa viene dall'alto i costi e l'inefficienza in linguaggi imperativi.L'autore di questo articolo parla di come ottimizzare ricorsiva algoritmi per rendere più veloce e più efficiente.Egli va anche su come convertire un tradizionale ciclo in una funzione ricorsiva e i vantaggi dell'utilizzo di coda di ricorsione.Le sue ultime parole riassume alcuni dei miei punti chiave penso:
"ricorsiva di programmazione dà al programmatore un modo migliore per organizzare il codice in modo che sia gestibile e logicamente coerente."
Link 3: È la ricorsione mai più veloce di looping?(Risposta)
Ecco un link di una risposta per un stackoverflow domanda che è simile alla tua.L'autore sottolinea che un sacco di parametri associati con recursing o loop sono molto linguaggio specifico.Linguaggi imperativi sono in genere più veloce utilizzando un ciclo e più lento con la ricorsione, e viceversa per i linguaggi funzionali.Credo che il punto principale da prendere da questo link è che è molto difficile rispondere alla domanda in una lingua agnostico / situazione cieco senso.
La ricorsione è più costoso a memoria, come ogni chiamata ricorsiva generalmente richiede un indirizzo di memoria per essere spinto a pila - in modo che il programma potrebbe tornare a quel punto.
Ancora, ci sono molti casi in cui la ricorsione è molto più naturale e leggibile di loop - come quando si lavora con gli alberi.In questi casi mi sento di raccomandare di attaccare per ricorsione.
In genere, ci si aspetterebbe la pena di prestazioni che risiedono in altra direzione.Chiamate ricorsive possono portare alla costruzione di extra stack frame;la pena per questo varia.Inoltre, in alcuni linguaggi come Python (più correttamente, in alcune implementazioni di alcune lingue...), è possibile eseguire limiti di stack piuttosto facilmente per attività che è possibile specificare in modo ricorsivo, come trovare il valore massimo in una struttura di dati ad albero.In questi casi, si ha realmente bisogno di attaccare con i passanti.
Scrittura di funzioni ricorsive in grado di ridurre la pena di prestazioni un po', se si dispone di un compilatore, che ottimizza la coda ricorsioni, etc.(Anche doppio controllo per assicurarsi che la funzione è davvero tail recursive---e ' una di quelle cose che molte persone commettono errori su.)
Oltre a "bordo" i casi (high performance computing, molto grande profondità di ricorsione, etc.), è preferibile adottare l'approccio che più esprime chiaramente il vostro intento, è ben progettato e facile da gestire.Ottimizzare solo dopo l'identificazione di un bisogno.
La ricorsione è meglio di iterazione per i problemi che possono essere suddivisi in più, pezzi più piccoli.
Per esempio, per fare una ricorsiva Fibonnaci algoritmo di abbattere fib(n) fib(n-1) fib(n-2) e calcolare entrambe le parti.Iterazione permette solo di ripetere una singola funzione più e più volte.
Tuttavia, Fibonacci è effettivamente rotto un esempio e penso iterazione è in realtà più efficiente.Si noti che il fib(n) = fib(n-1) + fib(n-2) fib(n-1) = fib(n-2) + fib(n-3).fib(n-1) viene calcolato due volte!
Un esempio migliore è un algoritmo ricorsivo per un albero.Il problema di analizzare il nodo principale può essere suddiviso in più piccoli problemi di analizzare ogni nodo figlio.A differenza di Fibonacci esempio, i problemi più piccoli sono indipendenti tra di loro.
Così sì - la ricorsione è meglio di iterazione per i problemi che possono essere suddivisi in più, più piccole, indipendenti, simili problemi.
Il rendimento peggiora quando si utilizza la ricorsione, perché la chiamata di un metodo, in qualsiasi lingua, implica un sacco di preparazione:il codice chiamante post di un indirizzo di ritorno parametri di chiamata, alcuni altri informazioni di contesto, quali i registri del processore potrebbe essere salvato da qualche parte, e al tempo di ritorno del metodo chiamato post di un valore di ritorno che viene poi recuperato dal chiamante, e le eventuali informazioni di contesto che è stato salvato in precedenza, verranno ripristinati.le prestazioni diff tra un iterativa e ricorsiva approccio sta nel tempo di tali operazioni.
Da un punto di vista implementativo, davvero iniziare a notare la differenza quando il tempo necessario per gestire la chiamata contesto è paragonabile al tempo che impiega il metodo da eseguire.Se il tuo metodo ricorsivo richiede più tempo per eseguire la chiamata di gestione del contesto di parte, andare ricorsiva modo il codice è più leggibile e di facile comprensione e non si noterà la perdita di prestazioni.In caso contrario, andare iterativo, per ragioni di efficienza.
Credo ricorsività in java non è attualmente ottimizzato.I dettagli sono sparsi in tutta questo discussione su LtU e i collegamenti associati.Si può essere una funzionalità nella prossima versione 7, ma a quanto pare presenta alcune difficoltà quando combinato con Stack di Ispezione, poiché alcuni fotogrammi mancherebbe.Stack di Ispezione è stato utilizzato per implementare la loro fine-grained modello di sicurezza dato che Java 2.
Ci sono molti casi in cui dà una soluzione più elegante oltre il metodo iterativo, il comune è l'esempio di attraversamento di un albero binario, in modo che non è necessariamente più difficile da mantenere.In generale, versioni iterative sono di solito un po ' più veloce (e durante la fase di ottimizzazione può ben sostituire una versione ricorsiva), ma ricorsiva versioni sono più semplici da comprendere e implementare correttamente.
La ricorsione è molto utile in alcune situazioni.Si consideri, per esempio il codice per trovare il fattoriale
int factorial ( int input )
{
int x, fact = 1;
for ( x = input; x > 1; x--)
fact *= x;
return fact;
}
Ora a considerare utilizzando la funzione ricorsiva
int factorial ( int input )
{
if (input == 0)
{
return 1;
}
return input * factorial(input - 1);
}
Osservando questi due, possiamo vedere che la ricorsione è facile da capire.Ma se non è usato con cura si può essere così tanto di errori di troppo.Supponiamo che se ci manca if (input == 0), quindi il codice sarà eseguito per qualche tempo e si conclude di solito con un overflow dello stack.
In molti casi la ricorsione è più veloce a causa della cache, che migliora le prestazioni.Per esempio, qui è una versione iterativa di merge sort, con la tradizionale unione di routine.Verrà eseguito più lento rispetto ricorsiva applicazione, a causa di memorizzazione nella cache di un miglioramento delle performance.
Iterativo attuazione
public static void sort(Comparable[] a)
{
int N = a.length;
aux = new Comparable[N];
for (int sz = 1; sz < N; sz = sz+sz)
for (int lo = 0; lo < N-sz; lo += sz+sz)
merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}
Implementazione ricorsiva
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid+1, hi);
merge(a, aux, lo, mid, hi);
}
PS - questo è ciò che è stato detto dal Professor Kevin Wayne (Università di Princeton) in corso di algoritmi presentati su Coursera.
Utilizzando la ricorsione, sei di affrontare il costo di una chiamata di funzione con ogni "iterazione", mentre con un ciclo, l'unica cosa che si paga è un incremento/decremento.Così, se il codice per il ciclo non è molto più complicato rispetto del codice per la soluzione ricorsiva, loop di solito essere superiore a ricorsione.
Ricorsione e iterazione dipende dalla logica di business che si desidera implementare, anche se nella maggior parte dei casi può essere usato in modo intercambiabile.La maggior parte degli sviluppatori andare per ricorsione, perché è più facile da capire.
Dipende dalla lingua.In Java si dovrebbe usare il loop.I linguaggi funzionali ottimizzare la ricorsione.
Se sei solo scorrendo l'elenco, poi certo, l'iterazione di distanza.
Un paio di altre risposte hanno detto (prima di profondità) tree traversal.Veramente un grande esempio, perché è una cosa molto comune per fare una molto comune struttura di dati.La ricorsione è estremamente intuitiva per questo problema.
Controllare il "trovare" i metodi qui:http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html
La ricorsione è più semplice (e quindi più fondamentale) di ogni possibile definizione di una iterazione.È possibile definire un Turing-completo, solo con un coppia di combinatori (sì, anche una ricorsione di per sé è un derivato nozione di un tale sistema). Lambda il tartaro è un altrettanto potente fondamentali del sistema, dotato di funzioni ricorsive.Ma se si desidera definire un'iterazione correttamente, avete bisogno di molto di più primitive per iniziare con.
Come per il codice n, codice ricorsivo è infatti molto più facile da capire e da mantenere, oltre a quello puramente iterativo uno, poiché la maggior parte delle strutture di dati ricorsive.Naturalmente, al fine di ottenere una avrebbe bisogno di un linguaggio con un supporto per l'alta funzioni di ordine e chiusure, almeno - per avere tutti gli standard combinatori e iteratori in un modo pulito.In C++, naturalmente, complicato ricorsiva soluzioni possono sembrare un po ' brutto, a meno che non sei un hardcore utente di FC++ e simili.
Io penso che in (senza coda) ricorsione ci sarebbe un calo di prestazioni per l'assegnazione di un nuovo stack ecc ogni volta che la funzione viene chiamata (dipende dalla lingua del corso).
dipende dalla "profondità di ricorsione".dipende da quanto la chiamata di funzione overhead influenzerà il tempo totale di esecuzione.
Ad esempio, il calcolo classico fattoriale in modo ricorsivo è molto inefficiente a causa di:- rischio di straripamento - rischio di stack traboccante - chiamata di funzione sovraccarico di occupare l ' 80% del tempo di esecuzione
durante lo sviluppo di un min-max algoritmo per l'analisi della sua posizione nel gioco degli scacchi, che analizza le successive N mosse e può essere implementato in ricorsione su "analisi approfondita" (come sto facendo ^_^)
La ricorsione?Da dove inizio, wiki ti dirà “è il processo di ripetizione di elementi in un self-simile"
Indietro nel giorno quando facevo il C, C++ ricorsione è stato un inviato di dio, roba come "ricorsività".Troverete anche molti algoritmi di ordinamento utilizzare la ricorsione.Quick sort esempio: http://alienryderflex.com/quicksort/
La ricorsione è come qualsiasi altro algoritmo utile per un problema specifico.Forse si mightn non utilizzare immediatamente o, spesso, ma non ci sarà problema sarete contenti di che è disponibile.
In C++, se la funzione ricorsiva è un basato su modelli, quindi il compilatore non ha più possibilità di ottimizzare, come tutti i tipo di deduzione e la funzione istanze avverrà in fase di compilazione.I compilatori moderni anche possibile incorporare la funzione, se possibile.Quindi se uno usa flag di ottimizzazione come -O3 o -O2 in g++, poi ricorsioni può avere la possibilità di essere più veloce di iterazioni.In iterativo codici, il compilatore viene meno la possibilità di ottimizzare, come si è già più o meno in ottimo stato (se scritto bene).
Nel mio caso, stavo cercando di implementare matrice di elevamento a potenza da squadratura utilizzando Armadillo matrice di oggetti, sia ricorsiva e iterativa modo.L'algoritmo può essere trovato qui... https://en.wikipedia.org/wiki/Exponentiation_by_squaring.Le mie funzioni, erano basati su modelli, e ho calcolato 1,000,000 12x12 matrici elevato a potenza 10.Ho ottenuto il seguente risultato:
iterative + optimisation flag -O3 -> 2.79.. sec
recursive + optimisation flag -O3 -> 1.32.. sec
iterative + No-optimisation flag -> 2.83.. sec
recursive + No-optimisation flag -> 4.15.. sec
Questi risultati sono stati ottenuti utilizzando gcc-4.8 con c++11 flag (-std=c++11) e Armadillo 6.1 con Intel mkl.Intel compiler, inoltre, mostra risultati simili.
Mike è corretto.Ricorsività è non ottimizzato dal compilatore Java o JVM.Si otterrà sempre un overflow dello stack con qualcosa di simile a questo:
int count(int i) {
return i >= 100000000 ? i : count(i+1);
}
Devi tenere a mente che utilizzando troppo in profondità di ricorsione in Overflow dello Stack, a seconda permesso la dimensione dello stack.Per evitare questo, assicurarsi di fornire alcune ipotesi di base che conclude la ricorsione.
La ricorsione è uno svantaggio che l'algoritmo di scrivere utilizzando la ricorsione è spazio O(n) complessità.Mentre iterativo approccio di disporre di uno spazio complessità di O(1).Questo è il advantange di utilizzo di iterazione su ricorsione.Perché fare utilizzare la ricorsione?
Vedere di seguito.
A volte è più facile scrivere un algoritmo che utilizza la ricorsione mentre è leggermente più difficile da scrivere un algoritmo che utilizza iterazione.In questo caso, se si sceglie di seguire l'iterazione approccio sarebbe necessario per gestire lo stack di te.
Per quanto ne so, Perl non ottimizza la coda di chiamate ricorsive, ma non si può fingere.
sub f{
my($l,$r) = @_;
if( $l >= $r ){
return $l;
} else {
# return f( $l+1, $r );
@_ = ( $l+1, $r );
goto &f;
}
}
Quando chiamarono prima allocazione di spazio sullo stack.Quindi cambierà i suoi argomenti, e riavviare il sottoprogramma, senza aggiungere nulla di più a pila.Sarà, dunque, far finta che non è mai chiamato la sua auto, trasformandosi in un processo iterativo.
Nota che non c'è "my @_;"o "local @_;"se l'avete fatto non funzionerebbe più.
Uso solo Chrome 45.0.2454.85 m, la ricorsione sembra essere una bella quantità più veloce.
Ecco il codice:
(function recursionVsForLoop(global) {
"use strict";
// Perf test
function perfTest() {}
perfTest.prototype.do = function(ns, fn) {
console.time(ns);
fn();
console.timeEnd(ns);
};
// Recursion method
(function recur() {
var count = 0;
global.recurFn = function recurFn(fn, cycles) {
fn();
count = count + 1;
if (count !== cycles) recurFn(fn, cycles);
};
})();
// Looped method
function loopFn(fn, cycles) {
for (var i = 0; i < cycles; i++) {
fn();
}
}
// Tests
var curTest = new perfTest(),
testsToRun = 100;
curTest.do('recursion', function() {
recurFn(function() {
console.log('a recur run.');
}, testsToRun);
});
curTest.do('loop', function() {
loopFn(function() {
console.log('a loop run.');
}, testsToRun);
});
})(window);
RISULTATI
// 100 viene eseguito utilizzando standard per il ciclo
100x per il ciclo di esecuzione.Tempo: 7.683 ms
// 100 viene eseguito utilizzando funzionale ricorsiva approccio w/ ricorsione di coda
100x ricorsione eseguire.Tempo: 4.841 ms
Nella schermata qui sotto, la ricorsione vince ancora una volta da un grande margine di quando eseguire a 300 cicli al test
Se le iterazioni sono atomica e gli ordini di grandezza più costoso di spingere un nuovo stack frame e creazione di un nuovo thread e si hanno più core e il vostro ambiente di runtime è possibile utilizzare tutti loro, poi una ricorsiva approccio potrebbe produrre un enorme incremento di prestazioni quando combinato con multithreading.Se il numero medio di iterazioni non è prevedibile, allora potrebbe essere una buona idea di utilizzare un pool di thread che avrà il controllo allocazione dei thread e impedire che il processo di creazione di troppi thread e sopraelevazione del sistema.
Per esempio, in alcune lingue, ci sono ricorsiva multithreading merge sort implementazioni.
Ma, di nuovo, il multithreading può essere utilizzato con looping, piuttosto che la ricorsione, così come bene questa combinazione dipende da più fattori, tra cui il sistema operativo e la sua thread meccanismo di allocazione.
Ho intenzione di rispondere alla tua domanda, attraverso la progettazione di un Haskell struttura di dati da parte di "induzione", che è una sorta di "doppio" per ricorsione.E poi vorrei mostrare come questa dualità porta a cose belle.
Vi presentiamo un tipo per un semplice albero:
data Tree a = Branch (Tree a) (Tree a)
| Leaf a
deriving (Eq)
Possiamo leggere questa definizione come dire "Un albero è un Ramo (che contiene due alberi) o è una foglia (che contiene un valore di dati)".Così la foglia è una sorta di minimo caso.Se un albero non è una foglia, allora deve essere un composto albero contenente due alberi.Questi sono gli unici casi.
Facciamo un albero:
example :: Tree Int
example = Branch (Leaf 1)
(Branch (Leaf 2)
(Leaf 3))
Ora, supponiamo di voler aggiungere 1 per ogni valore dell'albero.Siamo in grado di farlo chiamando:
addOne :: Tree Int -> Tree Int
addOne (Branch a b) = Branch (addOne a) (addOne b)
addOne (Leaf a) = Leaf (a + 1)
Innanzitutto, si noti che questo è, infatti, una definizione ricorsiva.Prende i dati dei costruttori Ramo e la Foglia casi (e da Foglia è minimo e questi sono gli unici casi possibili), siamo sicuri che la funzione termina.
Cosa ci vuole a scrivere addOne in un processo iterativo di stile?Cosa looping in un numero arbitrario di rami sembrano?
Inoltre, questo tipo di ricorsione spesso può essere fattorizzato, in termini di "funtore".Siamo in grado di fare Alberi in Functors definendo:
instance Functor Tree where fmap f (Leaf a) = Leaf (f a)
fmap f (Branch a b) = Branch (fmap f a) (fmap f b)
e la definizione di:
addOne' = fmap (+1)
Siamo in grado di fattore di altri ricorsione regimi, come il catamorphism (o fold) per un algebrica del tipo di dati.Utilizzando un catamorphism, possiamo scrivere:
addOne'' = cata go where
go (Leaf a) = Leaf (a + 1)
go (Branch a b) = Branch a b
Stack overflow si verifica solo se sei di programmazione in un linguaggio che non hanno costruito la gestione della memoria....In caso contrario, assicurarsi di che avere qualcosa in funzione (o una chiamata di funzione, STDLbs, ecc).Senza ricorsione non sarebbe semplicemente possibile avere cose come...Google o SQL, o di qualsiasi luogo si deve in modo efficiente ordinamento attraverso le grandi strutture di dati (classi) o database.
La ricorsione è la strada da percorrere se si desidera scorrere i file, abbastanza sicuro che 'trova * | ?grep *' i lavori.Kinda doppia ricorsione, in particolare con il tubo (ma non fare un sacco di chiamate di sistema, come tanti, come fare se non è qualcosa che si sta andando a mettere fuori là per altri usi).
Linguaggi di alto livello e anche clang/cpp può attuare le stesse in background.
