詳解JavaScript調(diào)用棧、尾遞歸和手動優(yōu)化
調(diào)用棧(Call Stack)
調(diào)用棧(Call Stack)是一個基本的計算機概念,這里引入一個概念:棧幀。
棧幀是指為一個函數(shù)調(diào)用單獨分配的那部分棧空間。
當(dāng)運行的程序從當(dāng)前函數(shù)調(diào)用另外一個函數(shù)時,就會為下一個函數(shù)建立一個新的棧幀,并且進(jìn)入這個棧幀,這個棧幀稱為當(dāng)前幀。而原來的函數(shù)也有一個對應(yīng)的棧幀,被稱為調(diào)用幀。每一個棧幀里面都會存入當(dāng)前函數(shù)的局部變量。
當(dāng)函數(shù)被調(diào)用時,就會被加入到調(diào)用棧頂部,執(zhí)行結(jié)束之后,就會從調(diào)用棧頂部移除該函數(shù)。并將程序運行權(quán)利(幀指針)交給此時棧頂?shù)臈_@種后進(jìn)后出的結(jié)構(gòu)也就是函數(shù)的調(diào)用棧。
而在JavaScript里,可以很方便的通過console.trace()這個方法查看當(dāng)前函數(shù)的調(diào)用幀
尾調(diào)用
說尾遞歸之前必須先了解一下什么是尾調(diào)用。簡單的說,就是一個函數(shù)執(zhí)行的最后一步是將另外一個函數(shù)調(diào)用并返回。
以下是正確示范:
// 尾調(diào)用正確示范1.0 function f(x){ return g(x); } // 尾調(diào)用正確示范2.0 function f(x) { if (x > 0) { return m(x) } return n(x); }
1.0程序的最后一步即是執(zhí)行函數(shù)g,同時將其返回值返回。2.0中,尾調(diào)用并不是非得寫在最后一行中,只要執(zhí)行時,是最后一步操作就可以了。
以下是錯誤示范:
// 尾調(diào)用錯誤示范1.0 function f(x){ let y = g(x); return y; } // 尾調(diào)用錯誤示范2.0 function f(x){ return g(x) + 1; } // 尾調(diào)用錯誤示范3.0 function f(x) { g(x); // 這一步相當(dāng)于g(x) return undefined }
1.0最后一步為賦值操作,2.0最后一步為加法運算操作,3.0隱式的有一句return undefined
尾調(diào)用優(yōu)化
在調(diào)用棧的部分我們知道,當(dāng)一個函數(shù)A調(diào)用另外一個函數(shù)B時,就會形成棧幀,在調(diào)用棧內(nèi)同時存在調(diào)用幀A和當(dāng)前幀B,這是因為當(dāng)函數(shù)B執(zhí)行完成后,還需要將執(zhí)行權(quán)返回A,那么函數(shù)A內(nèi)部的變量,調(diào)用函數(shù)B的位置等信息都必須保存在調(diào)用幀A中。不然,當(dāng)函數(shù)B執(zhí)行完繼續(xù)執(zhí)行函數(shù)A時,就會亂套。
那么現(xiàn)在,我們將函數(shù)B放到了函數(shù)A的最后一步調(diào)用(即尾調(diào)用),那還有必要保留函數(shù)A的棧幀么?當(dāng)然不用,因為之后并不會再用到其調(diào)用位置、內(nèi)部變量。因此直接用函數(shù)B的棧幀取代A的棧幀即可。當(dāng)然,如果內(nèi)層函數(shù)使用了外層函數(shù)的變量,那么就仍然需要保留函數(shù)A的棧幀,典型例子即是閉包。
在網(wǎng)上有很多關(guān)于講解尾調(diào)用的博客文章,其中流傳廣泛的一篇中有這樣一段。我不是很認(rèn)同。
function f() { let m = 1; let n = 2; return g(m + n); } f(); // 等同于 function f() { return g(3); } f(); // 等同于 g(3);
以下為博客原文:上面代碼中,如果函數(shù)g不是尾調(diào)用,函數(shù)f就需要保存內(nèi)部變量m和n的值、g的調(diào)用位置等信息。但由于調(diào)用g之后,函數(shù)f就結(jié)束了,所以執(zhí)行到最后一步,完全可以刪除 f() 的調(diào)用記錄,只保留 g(3) 的調(diào)用記錄。
但我認(rèn)為第一種中,也是先執(zhí)行m+n這步操作,再調(diào)用函數(shù)g同時返回。這應(yīng)當(dāng)是一次尾調(diào)用。同時m+n的值也通過參數(shù)傳入函數(shù)g內(nèi)部,并沒有直接引用,因此也不能說需要保存f內(nèi)部的變量的值。
總得來說,如果所有函數(shù)的調(diào)用都是尾調(diào)用,那么調(diào)用棧的長度就會小很多,這樣需要占用的內(nèi)存也會大大減少。這就是尾調(diào)用優(yōu)化的含義。
尾遞歸
遞歸,是指在函數(shù)的定義中使用函數(shù)自身的一種方法。函數(shù)調(diào)用自身即稱為遞歸,那么函數(shù)在尾調(diào)用自身,即稱為尾遞歸。
最常見的遞歸,斐波拉契數(shù)列,普通遞歸的寫法:
function f(n) { if (n === 0 || n === 1) return n else return f(n - 1) + f(n - 2) }
這種寫法,簡單粗暴,但是有個很嚴(yán)重的問題。調(diào)用棧隨著n的增加而線性增加,當(dāng)n為一個大數(shù)(我測了一下,當(dāng)n為100的時候,瀏覽器窗口就會卡死。。)時,就會爆棧了(棧溢出,stack overflow)。這是因為這種遞歸操作中,同時保存了大量的棧幀,調(diào)用棧非常長,消耗了巨大的內(nèi)存。
接下來,將普通遞歸升級為尾遞歸看看。
function fTail(n, a = 0, b = 1) { if (n === 0) return a return fTail(n - 1, b, a + b) }
很明顯,其調(diào)用棧為
fTail(5) => fTail(4, 1, 1) => fTail(3, 1, 2) => fTail(2, 2, 3) => fTail(1, 3, 5) => fTail(0, 5, 8) => return 5
被尾遞歸改寫之后的調(diào)用棧永遠(yuǎn)都是更新當(dāng)前的棧幀而已,這樣就完全避免了爆棧的危險。
但是,想法是好的,從尾調(diào)用優(yōu)化到尾遞歸優(yōu)化的出發(fā)點也沒錯),讓我們看看V8引擎官方團(tuán)隊的解釋
Proper tail calls have been implemented but not yet shipped given that a change to the feature is currently under discussion at TC39.
意思就是人家已經(jīng)做好了,但是就是還不能不給你用:)嗨呀,好氣喔。
當(dāng)然,人家肯定是有他的正當(dāng)理由的:
- 在引擎層面消除尾遞歸是一個隱式的行為,程序員寫代碼時可能意識不到自己寫了死循環(huán)的尾遞歸,而出現(xiàn)死循環(huán)后又不會報出stack overflow的錯誤,難以辨別。
- 堆棧信息會在優(yōu)化的過程中丟失,開發(fā)者調(diào)試非常困難。
道理我都懂,但是不信邪的我拿nodeJs(v6.9.5)手動測試了一下:
好的,我服了
手動優(yōu)化
雖然我們暫時用不上ES6的尾遞歸高端優(yōu)化,但遞歸優(yōu)化的本質(zhì)還是為了減少調(diào)用棧,避免內(nèi)存占用過多,爆棧的危險。而俗話說的好,一切能用遞歸寫的函數(shù),都能用循環(huán)寫——尼克拉斯·夏,如果將遞歸改成循環(huán)的話,不就解決了這種調(diào)用棧的問題么。
方案一:直接改函數(shù)內(nèi)部,循環(huán)執(zhí)行
function fLoop(n, a = 0, b = 1) { while (n--) { [a, b] = [b, a + b] } return a }
這種方案簡單粗暴,缺點就是沒有遞歸的那種寫法比較容易理解。
方案二:Trampolining(蹦床函數(shù))
function trampoline(f) { while (f && f instanceof Function) { f = f() } return f } function f(n, a = 0, b = 1) { if (n > 0) { [a, b] = [b, a + b] return f.bind(null, n - 1, a, b) } else { return a } } trampoline(f(5)) // return 5
這種寫法算是容易理解一些了,就是蹦床函數(shù)的作用需要仔細(xì)看看。缺點還有就是需要修改原函數(shù)內(nèi)部的寫法。
方案三:尾遞歸函數(shù)轉(zhuǎn)循環(huán)方法
function tailCallOptimize(f) { let value let active = false const accumulated = [] return function accumulator() { accumulated.push(arguments) if (!active) { active = true while (accumulated.length) { value = f.apply(this, accumulated.shift()) } active = false return value } } } const f = tailCallOptimize(function(n, a = 0, b = 1) { if (n === 0) return a return f(n - 1, b, a + b) }) f(5) // return 5
經(jīng)過 tailCallOptimize 包裝后返回的是一個新函數(shù) accumulator,執(zhí)行 f時實際執(zhí)行的是這個函數(shù)。這種方法可以不用修改原遞歸函數(shù),當(dāng)調(diào)用遞歸時只用使用該方法轉(zhuǎn)置一下便可解決遞歸調(diào)用的問題。
總結(jié)
尾遞歸優(yōu)化是個好東西,但既然暫時用不上,那我們就該在平時編碼的過程中,對使用到了遞歸的地方特別敏感,時刻避免出現(xiàn)死循環(huán),爆棧等危險。畢竟,好的工具不如好的習(xí)慣。
以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
JavaScript中removeChild 方法開發(fā)示例代碼
這篇文章主要介紹了JavaScript中removeChild 方法開發(fā)示例代碼,非常不錯,具有參考借鑒價值,需要的朋友可以參考下2016-08-08Bootstrap打造一個左側(cè)折疊菜單的系統(tǒng)模板(二)
這篇文章主要介紹了Bootstrap打造一個左側(cè)折疊菜單的系統(tǒng)模板(二)的相關(guān)資料,需要的朋友可以參考下2016-05-05基于d3.js/neovis.js/neod3.js實現(xiàn)鏈接neo4j圖形數(shù)據(jù)庫的圖像化顯示功能
neovis.js?由vis.js支持的圖形可視化以及來自Neo4j的數(shù)據(jù)。這篇文章主要介紹了基于d3.js/neovis.js/neod3.js實現(xiàn)鏈接neo4j圖形數(shù)據(jù)庫的圖像化顯示功能,需要的朋友可以參考下2022-02-02JS如何判斷瀏覽器類型和詳細(xì)區(qū)分IE各版本瀏覽器
本篇文章主要介紹了JS判斷瀏覽器類型和詳細(xì)區(qū)分IE各版本瀏覽器的代碼,非常具有實用價值,有興趣的可以了解一下。2017-03-03