2011-08-17 4 views
18

我知道在使用JavaScript遞歸調用函數時應該小心,因爲第二個調用的速度可能會降低10倍。用JavaScript調用遞歸函數

Eloquent JavaScript狀態:

還有一個重要的問題:在大多數JavaScript實現,這第二個版本比第一次慢10倍左右。在JavaScript中,運行一個簡單的循環比多次調用函數便宜得多。

John Resig甚至說這是this後的問題。

我的問題是:爲什麼使用遞歸效率太低?它只是一個特定引擎的構建方式嗎?如果情況並非如此,我們會在JavaScript中看到一段時間嗎?

+1

我猜這是一個範圍的事情:P偉大的問題,我很好奇他們回答的是! – Pelshoff

+4

函數調用的開銷大於循環控制的開銷;幾乎所有的編程語言都是如此。在調用一個函數時,需要做更多的簿記工作:分配和初始化一個新的作用域,保存返回地址,編組參數等。注意,JavaScript解釋器以更快的速度變得更快,所以性能提示在3應該質疑一個四歲的博客文章(或書)。 – Pointy

+1

「因爲你的第二個電話可能會慢10倍」這不是文字所說的。它說第二版的代碼慢了10倍。 –

回答

11

由於更改堆棧和設置新的上下文等所有開銷,函數調用僅比簡單循環更昂貴。爲了使遞歸非常有效,語言必須支持某種形式的tail-call消除,這基本上意味着將某些類型的遞歸函數轉換爲循環。像OCaml,Haskell和Scheme這樣的函數式語言可以做到這一點,但是我沒有意識到JavaScript的實現是這樣做的(除非他們都這麼做,否則我們會遇到哲學哲學家的問題)。

+5

ES6應該有尾部調用優化。 [適當的尾巴呼叫](http://wiki.ecmascript.org/doku.php?id=harmony:proper_tail_calls) – Raynos

3

這只是瀏覽器使用的特定JS引擎的一種方式,是的。如果沒有尾部調用消除,每次執行遞歸時都必須創建一個新的堆棧幀,而使用循環時,只需將程序計數器重新設置爲開始。例如,Scheme將此語言作爲語言規範的一部分,因此您可以以這種方式使用遞歸而不必擔心性能。

https://bugzilla.mozilla.org/show_bug.cgi?id=445363表示Firefox正在取得進展(並且Brendan Eich在這裏講到它可能成爲ECMAScript規範的一部分),但我認爲目前的瀏覽器目前還沒有實現這一功能。