Ci sono dei vantaggi nell'usare la ricorsione per l'iterazione, a parte la leggibilità e l'eleganza a volte? [duplicare]

Question

Ci sono dei vantaggi nell'usare la ricorsione per l'iterazione, a parte la leggibilità e l'eleganza a volte? [duplicare]

#1 da (9 voti)
#2 da (2 voti)
#3 da (2 voti)

7

Sto per fare due ipotesi. Per favore correggimi se hanno torto:

Non esiste un algoritmo ricorsivo senza un equivalente iterativo.
L'iterazione è sempre più economica in termini di prestazioni rispetto alla ricorsione (at almeno in linguaggi di uso generale come Java, C ++, Python ecc.).

Se è vero che la ricorsione è sempre più costosa dell'iterazione e che può sempre essere sostituita da un algoritmo iterativo (nelle lingue che lo consentono) - penso che i due motivi rimanenti per usare la ricorsione siano: l'eleganza e la leggibilità .

Alcuni algoritmi sono espressi in modo più elegante con la ricorsione. Per esempio. scansione di un albero binario.

Tuttavia, a parte questo, ci sono dei motivi per usare la ricorsione sull'iterazione? La ricorsione ha vantaggi rispetto all'iterazione se non a volte l'eleganza e la leggibilità?

recursion

posta Aviv Cohn 03.06.2014 - 17:07

fonte

3 risposte

2

La ricorsività utilizza lo stack di chiamate per memorizzare i ritorni delle chiamate di funzioni. Lo stato della funzione è memorizzato tra le chiamate.

L'iterazione deve anche utilizzare uno stack o un meccanismo simile per memorizzare gli stati intermedi, tranne che tu stesso crei lo stack. A meno che, naturalmente, non sia possibile trovare un algoritmo sostitutivo che non richieda tale archiviazione di stato.

La ricorsione è solo più costosa se si eccede nello stack. In un certo senso, l'iterazione sarà più costosa (in quegli algoritmi che si prestano alla ricorsione), perché stai ricreando il meccanismo di memorizzazione dello stato che la ricorsione fornisce già.

risposta data 03.06.2014 - 17:13

fonte

2

In primo luogo, mentre è vero che esiste sempre un equivalente iterativo equivalente a qualsiasi algoritmo ricorsivo, non è necessariamente il caso che l'equivalente iterativo sia migliore, per qualsiasi ragionevole definizione di "migliore".

Per alcuni algoritmi, l'equivalente iterativo si conclude simulando l'algoritmo ricorsivo, completo di parametri simulati e stacking e unstacking delle variabili locali. Considera la funzione di Ackermann . Prendi in considerazione la codifica di Huffman . In questi casi, si ottiene molto poco da (ri) scrivere le operazioni di stack esplicite.

In secondo luogo, non è necessariamente il caso che la ricorsione sia sempre più costosa dell'iterazione. Considera ricorsione della coda e leggi i documenti "Lambda: The Ultimate ...".

(Sì, so che questo ha bisogno di espansione. Devo andare ad un appuntamento dal dottore in questo momento.)

risposta data 03.06.2014 - 18:55

fonte

Leggi altre domande sui tag recursion

Come aggiungere una proprietà a un oggetto che non è possibile modificare? Logger.getLogger (MyClass.class) è il modo migliore per inizializzare i logger log4j?

score 9 · Accepted Answer

Beh, di solito è meno codice.

E nella misura in cui è meno codice, è meno soggetto a errori.

In particolare, la ricorsione è molto utile quando le soluzioni iterative richiedono che simuli la ricorsione con uno stack. La ricorsione riconosce che il compilatore già gestisce uno stack per ottenere esattamente ciò di cui hai bisogno. Quando inizi a gestire il tuo, non solo stai probabilmente reintroducendo il sovraccarico della chiamata alla funzione che intendevi evitare; ma stai reinventando una ruota (con tanto spazio per i bug) che esiste già in una forma piuttosto priva di bug.

IMO, evita la ricorsione solo se può essere eseguita in modo naturale e senza stack. (O altro stato non scalare e / o struttura di gestione dell'ambito.)