Overhead di ricorsione: quanto è grave?[duplicare]

Question

Possibile duplicato:
La ricorsione è mai più veloce del looping?

Sono stato addestrato per la prima volta a programmare seriamente in C, circa 15 anni fa.Il mio datore di lavoro voleva un codice altamente ottimizzato per compiti computazionalmente difficili.Ricordo di essere stato consigliato più di una volta di riscrivere le ricorsioni come loop, anche alla costosa leggibilità, al fine di evitare "sovraccarico di ricorsione". Come l'ho capito allora, il sovraccarico di ricorsione è stato lo sforzo extra richiesto per spingere i dati su uno stack e successivamente metterli via.

Ora codifico in C, Python, Perl e talvolta Java, e a volte mi chiedo quali siano le ricorsioni.C’è ancora qualcosa da guadagnare riscrivendoli?E se fossero ricorsioni in coda?I compilatori moderni hanno reso discutibili tutti questi problemi?Tali preoccupazioni sono irrilevanti per le lingue interpretate?

Answer 1

ricorsione può portare a grande carico di lavoro se il kernel della funzione ricorsiva è meno computazionalmente costoso di voce funzione / codice di uscita e il costo della chiamata stessa. Il modo migliore per scoprirlo è semplicemente al profilo due versioni del codice -. Uno ricorsiva, e uno non

Detto questo, se la vostra idea di evitare la ricorsione è quello di fare uno stack-come la struttura da soli, attenzione - potrebbe non necessariamente essere qualsiasi più veloce rispetto al metodo ricorsivo più semplice. Anche in questo caso, profiling è tuo amico.

Infine, ricordate che il tempo programmatore è più costoso di tempo di CPU. Prima di micro-ottimizzare il codice, è davvero una buona idea su misura per vedere se davvero sarà un problema.

Answer 2

E 'grave. La maggior parte del codice di lingue che in hanno un costo reale per chiamate di funzione (i compilatori per loro può generalmente fare ricorsione di coda pure in modo a volte non è un problema).

Tale costo, e il fatto che lo stack non è una risorsa illimitata, di solito mi fa tendo ad usare la ricorsione solo per i casi in cui so che c'è un limite alla profondità che può andare.

Per esempio, conosco un equilibrato albero binario di ricerca sarà solo andare cinquanta livelli di profondità per uno voci quadrilione. Non vorrei, tuttavia, l'uso:

def sum1through (n):
    if n == 0 return 0
    return n + sum1through (n-1)

Da quando faccio quello per n di venti milioni non sarebbe salutare per una pila.

Answer 3

Il problema esiste ancora. Ricorsione richiede molto spazio di stack, come ogni volta che un metodo si definisce, un puntatore ad esso e le sue variabili locali vengono generati nuovamente. Il numero di chiamate di funzione effettuate durante ricorsione rende un utilizzo della memoria O (n); rispetto a O (1) di una funzione non ricorsiva come loop.

Answer 4

Non credo che nessuna delle lingue che hai menzionato richiede che la piattaforma / compilatore implementa coda eliminazione chiamata . Si possono trovare le lingue che fanno richiedono questa ottimizzazione -. La maggior parte dei linguaggi funzionali hanno questo requisito

Tuttavia un'altra cosa che dovete considerare è che i computer sono diventati ordini di grandezza più veloce di quanto lo fossero 15 anni fa, quindi è molto più raro ora di prima che è necessario preoccuparsi di micro-ottimizzazioni. Un programma che 15 anni fa avrebbero richiesto l'ottimizzazione mano attenta in assembler per ottenere prestazioni decenti potrebbe correre incredibilmente veloce su un computer moderno, anche se scritto in un linguaggio di alto livello come Java. Questo non vuol dire che le prestazioni non è mai più un problema - ma si dovrebbe concentrarsi sulla scelta del algoritmo corretto e sulla scrittura di leggibile di codice. Solo fare micro-ottimizzazioni dopo aver misurato le prestazioni e si può vedere che il codice in questione è il collo di bottiglia.

Una cosa che non è necessario preoccuparsi di se è straripante stack. Se c'è il rischio che questo accada potrebbe essere utile riscrivere una funzione ricorsiva in modo iterativo, invece.

Answer 5

La gente dice un sacco di cose stupide riguardo alle prestazioni.

1. Se tu Bisogno ricorsione, come fare una passeggiata sugli alberi in profondità, quindi ne hai bisogno, quindi usala.

2. Prima di preoccuparsi delle prestazioni di nulla, scopri se hai un problema e dove si trova.
   I problemi di prestazioni sono come truffatori e imbroglioni: sono specializzati nell'essere dove meno te lo aspetti, quindi se sei preoccupato per qualcosa di specifico come la ricorsione, è quasi sicuro che ti preoccuperai della cosa sbagliata.

A mio parere, il modo migliore per individuare problemi di prestazioni è mediante il campionamento dello stack all'ora dell'orologio da parete, E esaminando i campioni per vedere cosa sta facendo il programma, non solo ottenendo misurazioni e chiedendosi cosa significano.

Detto questo, se trovi il 10% o più del tempo trascorso in una chiamata ricorsiva e non accade molto altro all'interno della routine ricorsiva, e puoi eseguirne il loop, probabilmente il loop sarà d'aiuto.