Performance: ricorsione vs iterazione in Javascript

JavaScript non esegue l'ottimizzazione della ricorsione di coda , quindi se il tuo la ricorsione è troppo profonda, potresti ottenere un overflow dello stack di chiamate. L'iterazione non ha tali problemi. Se pensi di recidare troppo e hai davvero bisogno della ricorsione (ad esempio, per riempire tutto), sostituisci la ricorsione con il tuo stack.

Le prestazioni della ricorsione sono probabilmente peggiori delle prestazioni di iterazione, perché le chiamate e i ritorni delle funzioni richiedono la conservazione e il ripristino dello stato, mentre l'iterazione salta semplicemente a un altro punto di una funzione.

Aggiornamento : poiché ES2015, JavaScript ha TCO , quindi parte dell'argomento riportato di seguito non regge più.

Sebbene Javascript non abbia l'ottimizzazione della coda, la ricorsione è spesso il modo migliore per andare. E sinceramente, tranne che nei casi limite, non avrai overflow dello stack di chiamate.

Le prestazioni sono qualcosa da tenere a mente, ma anche un'ottimizzazione prematura. Se pensate che la ricorsione sia più elegante dell'iterazione, allora provatela. Se si scopre che questo è il collo di bottiglia (che potrebbe non essere mai), puoi sostituirlo con una brutta iterazione. Ma il più delle volte, il collo di bottiglia si trova nelle manipolazioni DOM o più in generale nell'I / O, non nel codice stesso.

La ricorsione è sempre più elegante ¹ .

¹ : opinione personale.

Ero piuttosto curioso di questa performance anche in javascript, quindi ho fatto alcuni esperimenti (anche se su una versione precedente del nodo). Ho scritto un calcolatore fattoriale in modo ricorsivo vs iterazioni e l'ho eseguito alcune volte localmente. Il risultato sembrava piuttosto strongmente inclinato verso la ricorsione con una tassa (prevista).

Codice: link

Result:
j03m-MacBook-Air:trickyQuestions j03m$ node factorial.js 
Time:557
Time:126
j03m-MacBook-Air:trickyQuestions j03m$ node factorial.js 
Time:519
Time:120
j03m-MacBook-Air:trickyQuestions j03m$ node factorial.js 
Time:541
Time:123
j03m-MacBook-Air:trickyQuestions j03m$ node --version
v0.8.22

Come per richiesta dall'OP effettuerò il chip (senza rendermi ridicolo, spero: P)

Penso che siamo tutti d'accordo sul fatto che la ricorsione è solo un modo più elegante di codifica. Se fatto bene, può rendere il codice più gestibile, che è IMHO altrettanto importante (se non di più) che rasatura via 0,0001 ms.

Per quanto riguarda l'argomento secondo il quale JS non esegue l'ottimizzazione di Tail-call: non è più completamente vero, utilizzando la modalità rigorosa di ECMA5 abilita il TCO. Era qualcosa di cui non ero molto contento da un po 'di tempo fa, ma almeno ora so perché arguments.callee genera errori in modalità rigorosa. Conosco il link sopra link a un bug report, ma il bug è impostato su WONTFIX. Inoltre, è in arrivo il TCO standard: ECMA6 (dicembre 2013).

Istintivamente, e aderendo alla natura funzionale di JS, direi che la ricorsione è lo stile di codifica più efficiente del 99,99% delle volte. Tuttavia, Florian Margaine ha ragione quando afferma che il collo di bottiglia rischia di essere trovato altrove. Se stai manipolando il DOM, probabilmente stai concentrando la tua attenzione sulla scrittura del tuo codice quanto più possibile manutenibile. L'API DOM è quella che è: lenta.

Penso che sia quasi impossibile offrire una risposta definitiva su quale sia l'opzione più veloce. Ultimamente, un sacco di jspref che ho visto mostrano che il motore V8 di Chrome è ridicolmente veloce in alcune attività, che gira 4x più lentamente su SpiderMonkey di FF e viceversa. I moderni motori JS sono dotati di tutti i trucchi per ottimizzare il codice. Non sono esperto, ma ritengo che V8, ad esempio, sia altamente ottimizzato per chiusure (e ricorsione), mentre il motore JScript di MS non lo è. SpiderMonkey spesso funziona meglio quando il DOM è coinvolto ...

In breve: direi quale tecnica sarà più performante, come sempre in JS, quasi impossibile da prevedere.

Senza la modalità strict, le prestazioni di Iteration sono solitamente leggermente più veloci della ricorsione ( oltre a rendere il JIT più efficiente ). L'ottimizzazione della ricorsione di coda elimina sostanzialmente qualsiasi differenza evidente perché trasforma l'intera sequenza di chiamate in un salto.

Esempio: Jsperf

Suggerirei di preoccuparmi molto di più sulla chiarezza del codice e sulla semplicità quando si tratta di scegliere tra ricorsione e iterazione.