Il codice ricorsivo è più lento del codice non ricorsivo?

5

Ora sono solo un programmatore alle prime armi, ma quello che i miei amici che stanno studiando programmazione mi dicono che il codice ricorsivo è una buona cosa, porta a una minore duplicazione del codice e sembra più elegante.

Ora può essere così, ma ogni volta che ho provato la mia mano con il codice ricorsivo ho sempre trovato che è molto più lento del codice non ricorsivo, non sono sicuro che sia qualcosa riguardo al modo in cui ho l'ho usato ma ne dubito strongmente, l'ho usato per cose abbastanza semplici come Collatz Conjecture e la generazione di numeri di Fibonacci, ma ogni volta che l'ho confrontato con un normale codice iterativo l'approccio ricorsivo si attesta costantemente intorno al doppio del tempo delle soluzioni iterative .

    
posta Overly Excessive 04.05.2014 - 15:34
fonte

2 risposte

10

È bene capire almeno come funziona la ricorsione, perché alcuni algoritmi sono naturalmente ricorsivi e quindi molto più facili da esprimere usando la ricorsione.

Inoltre, gli algoritmi ricorsivi (o le implementazioni) non sono intrinsecamente più lenti di quelli iterativi. In effetti, ogni algoritmo ricorsivo può essere implementato da un'equivalente implementazione iterativa al costo di dover tenere traccia di alcuni valori intermedi / temporanei, dove la versione ricorsiva tiene automaticamente traccia di quelli nello stack delle chiamate di funzioni.

Un esempio di algoritmo ricorsivo è se si desidera applicare un'operazione a tutti i nodi di un albero. L'implementazione più naturale qui è quella di avere una funzione che esegue l'operazione su un nodo e si chiama in modo ricorsivo per ciascuno dei figli del nodo.

Per alcuni algoritmi, come il calcolo di una sequenza di Fibonacci, la ricorsione sembra naturale, ma un'implementazione ingenua sarà molto più lenta di un'implementazione iterativa, perché la versione ricorsiva continua a ripetere lo stesso lavoro più e più volte. Questo significa che per quei particolari algoritmi, la ricorsione potrebbe non essere la scelta migliore, o che è necessario utilizzare alcune tecniche per ricordare valori intermedi che potrebbero essere necessari di nuovo altrove nell'algoritmo.

Per altri algoritmi, in particolare quelli che usano tattiche divide e conquista, scoprirai che hai bisogno di uno stack per tenere traccia di alcune cose nella soluzione iterativa. In questi casi, una versione ricorsiva è molto più pulita, perché la gestione dello stack diventa implicita.

    
risposta data 04.05.2014 - 17:38
fonte
4

La ricorsione è più lenta e consuma più memoria poiché può riempire lo stack. Ma c'è un work-around chiamato ottimizzazione del tail-call che richiede un codice un po 'più complesso (poiché hai bisogno di un altro parametro per la funzione da passare in giro) ma è più efficiente poiché non riempie lo stack.

Purtroppo C # non supporta questo così Ti suggerisco di utilizzare la ricorsione con attenzione, perché potresti ottenere un overflow dello stack per valori di grandi dimensioni.

In conclusione, nei linguaggi funzionali hai solo ricorsione e devi affrontarla; ma nelle lingue imperative l'iterazione è più naturale e più efficiente. La maggior parte delle lingue imperative più utilizzate non supporta (Java, C #, Python) o non garantisce l'ottimizzazione della coda (C, C ++).

    
risposta data 04.05.2014 - 16:08
fonte

Leggi altre domande sui tag