La ricorsione è una cattiva idea per grandi dimensioni di input a causa delle dimensioni limitate dello stack di chiamate? [duplicare]

0

Stack di chiamate dimensioni in JavaScript :

Three results:
- Node.js: 11034
- Firefox: 50994
- Chrome: 10402

Sembra che sarebbe una cattiva idea usare la ricorsione per cose come l'inserimento BST, perché c'è una possibilità che tu possa avere a che fare con dimensioni di input in milioni o miliardi.

    
posta Adam Zerner 15.11.2015 - 19:49
fonte

3 risposte

3
La ricorsione

Senza limiti è in genere una cattiva idea se sai che le chiamate ricorsive potrebbero diventare molto profonde. Ma se hai un modo per garantire una profondità massima relativamente piccola per il tuo algoritmo ricorsivo, o se la tua lingua supporta la ricorsione in coda e il tuo algoritmo è uno che può trarne vantaggio, puoi tranquillamente ignorare questo problema.

P.S. ECMAScript 6 ha una ricorsione in coda, quindi per Javascript almeno, questo sarà significativamente meno un problema in futuro.

    
risposta data 15.11.2015 - 19:59
fonte
1

L'uso sconsiderato della ricorsione può metterti nei guai. Tuttavia, abbastanza spesso la profondità massima della ricorsione può essere mantenuta piccola. Se hai ricorsione con una chiamata ricorsiva one , può essere facilmente sostituita con iterazione. Se hai due o più chiamate ricorsive, in genere la maggior parte delle chiamate sta riducendo notevolmente il lavoro. Ad esempio in quicksort, dividi un array in due parti, una è più grande, una è più piccola. Fai le parti più piccole con ricorsione e la parte più grande con l'iterazione.

    
risposta data 15.11.2015 - 21:36
fonte
0

Se per BST intendi un albero di ricerca bilanciato, la ricorsione è perfettamente a posto, perché il bilanciamento assicura che la profondità di ricorsione sia O (log n). Ecco perché lo facciamo in primo luogo. Ma usando la ricorsione per implementare un elenco collegato - davvero pessimo, a meno che tu non abbia un'eliminazione di chiamata di coda.

    
risposta data 15.11.2015 - 22:30
fonte

Leggi altre domande sui tag