建站
咨詢(xún)
售后
建站咨詢(xún)
新聞中心
成都創(chuàng)新互聯(lián)服務(wù)項(xiàng)目包括桐柏網(wǎng)站建設(shè)、桐柏網(wǎng)站制作、桐柏網(wǎng)頁(yè)制作以及桐柏網(wǎng)絡(luò)營(yíng)銷(xiāo)策劃等。多年來(lái)，我們專(zhuān)注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，桐柏網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶(hù)以成都為中心已經(jīng)輻射到桐柏省份的部分城市，未來(lái)相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶(hù)的支持與信任！
前言
在這里關(guān)于遞歸，這里就不贅述了，有興趣的可以去查一查資料。
需要了解如何優(yōu)化尾遞歸的話，我們需要從最開(kāi)始講起。
- 什么是尾調(diào)用
- 什么是尾遞歸
- 如何優(yōu)化尾遞歸
尾調(diào)用
從字面理解，自然而言就是在函數(shù)的尾部返回一個(gè)函數(shù)的調(diào)用，通常來(lái)說(shuō)，指的是函數(shù)執(zhí)行的最后一步。
舉個(gè)例子
- const fn = () => f1() || f2()
- // 這里的話, f2函數(shù)有可能是尾調(diào)用,f1不可能是尾調(diào)用
為什么f1函數(shù)不是呢，我們看這個(gè)函數(shù)的等價(jià)形式
- const fn = function () {
- const flag = f1()
- if(flag) {
- return flag
- } else {
- return f2()
- }
- }
似乎寫(xiě)到這里，根據(jù)尾調(diào)用定義，我們就明白了，只有f2函數(shù)是在尾部調(diào)用。
說(shuō)到這里，為什么要說(shuō)尾調(diào)用呢?我們事先想一想傳統(tǒng)的遞歸，典型的就是首先執(zhí)行遞歸調(diào)用，然后根據(jù)這個(gè)遞歸的返回值并結(jié)算結(jié)果，那么傳統(tǒng)的遞歸缺點(diǎn)有哪些呢
- 效率低，占內(nèi)存。
- 如果遞歸鏈過(guò)長(zhǎng)，可能會(huì)stack overflow
那么我們是不是可以做優(yōu)化呢，這就可以涉及上面提到的尾調(diào)用，它的原理是啥呢
“按照阮一峰老師在es6的函數(shù)擴(kuò)展中的解釋就是：函數(shù)調(diào)用會(huì)在內(nèi)存形成一個(gè)“調(diào)用記錄”，又稱(chēng)“調(diào)用幀”（call frame），保存調(diào)用位置和內(nèi)部變量等信息。如果在函數(shù)A的內(nèi)部調(diào)用函數(shù)B，那么在A的調(diào)用幀上方，還會(huì)形成一個(gè)B的調(diào)用幀。等到B運(yùn)行結(jié)束，將結(jié)果返回到A，B的調(diào)用幀才會(huì)消失。如果函數(shù)B內(nèi)部還調(diào)用函數(shù)C，那就還有一個(gè)C的調(diào)用幀，以此類(lèi)推。所有的調(diào)用幀，就形成一個(gè)“調(diào)用?！保╟all stack）。
“這里的“調(diào)用幀”和“調(diào)用?！?，說(shuō)的應(yīng)該就是“執(zhí)行環(huán)境”和“調(diào)用?！?。因?yàn)槲舱{(diào)用時(shí)函數(shù)的最后一部操作，所以不再需要保留外層的調(diào)用幀，而是直接取代外層的調(diào)用幀，所以可以起到一個(gè)優(yōu)化的作用。
從上述的描述中，我們視乎可以理解成
- 它的原理類(lèi)似于當(dāng)編譯器檢測(cè)到一個(gè)函數(shù)調(diào)用是尾遞歸時(shí)，它會(huì)覆蓋當(dāng)前的活動(dòng)記錄而不是在函數(shù)棧中創(chuàng)建一個(gè)新的調(diào)用記錄。
- 這樣子，我們也可以理解成，不同的語(yǔ)言編譯器或者是解釋器做了尾遞歸優(yōu)化，才讓它不會(huì)爆棧。
既然是這樣子的話，尾遞歸的優(yōu)化，取決于瀏覽器，那具體有哪些主流瀏覽器支持呢
safari 和火狐，有興趣的可以去了解一下，可以寫(xiě)個(gè)斐波那契數(shù)列數(shù)列驗(yàn)證一下。
手動(dòng)優(yōu)化
既然我們知道了，很多瀏覽器對(duì)于尾遞歸的優(yōu)化支持的瀏覽器并不多，那你會(huì)好奇，當(dāng)我們使用尾遞歸進(jìn)行優(yōu)化的時(shí)候，依然出現(xiàn)棧溢出的錯(cuò)誤，那么我們?nèi)绾谓鉀Q呢？
我在網(wǎng)上看到一個(gè)不錯(cuò)的方案，采用的是蹦床函數(shù)
- function trampoline(f) {
- while (f && f instanceof Function) {
- f = f();
- }
- return f;
- }
那么如何使用呢
我們拿最常見(jiàn)的斐波那契數(shù)列來(lái)說(shuō)吧
- function fibonacci(n) {
- if (n === 0) return 0
- if (n === 1) return 1
- return fibonacci(n - 1) + fibonacci(n - 2)
- }
根據(jù)上面的式子，我們可以將其寫(xiě)成迭代形式，用一個(gè)變量去緩存它的值
- function fibonacci (n, ac1 = 0, ac2 = 1) {
- return n <= 1 ? ac2 :fibonacci(n - 1, ac2, ac1 + ac2);
- }
其實(shí)試過(guò)的小伙伴，會(huì)發(fā)現(xiàn)，當(dāng)你需要求的n足夠大的時(shí)候，還是會(huì)報(bào)錯(cuò)，類(lèi)似于下面的錯(cuò)誤信息
- // fibonacci(10000)
- Uncaught RangeError: Maximum call stack size exceeded
這個(gè)時(shí)候，那么我們?nèi)绾稳?yōu)化呢？難道真的沒(méi)有辦法可以解決了嗎
這里得借鑒下別人的思路，我覺(jué)得挺不錯(cuò)的，這里就給出代碼
- function trampoline(f) {
- while (f && f instanceof Function) {
- f = f();
- }
- return f;
- }
你可以把這個(gè)函數(shù)稱(chēng)之為蹦床函數(shù), 這個(gè)函數(shù)的作用就是放回一個(gè)新的函數(shù)，我們將它們倆結(jié)合起來(lái)的話，棧溢出的問(wèn)題似乎就可以解決了
- // 可以試一試噢
- trampoline(fibonacci (10000))
這里的蹦床函數(shù)，我是參考別人的寫(xiě)法，似乎這樣子寫(xiě)的話，不太行，我個(gè)人覺(jué)得這樣子可以避免調(diào)用棧溢出，實(shí)際情況下，這樣子是行不通的，哪里有行不通的，還望指出。
當(dāng)然了，手動(dòng)優(yōu)化，可以將遞歸的過(guò)程改寫(xiě)成迭代的過(guò)程，就拿斐波那契數(shù)列這題來(lái)說(shuō)，我們可以使用動(dòng)態(tài)規(guī)劃來(lái)完成，O（n）完成答案的更新。
- // 偽代碼
- F[i] = F[i-1] + F[i-2]
嗯，將一個(gè)尾遞歸函數(shù)轉(zhuǎn)換成循環(huán)迭代函數(shù)，算是手動(dòng)優(yōu)化一種方式，在我們語(yǔ)言沒(méi)有原生支持尾遞歸優(yōu)化，那么可以考慮這種情況。
對(duì)于尾遞歸而言，我們需要了解優(yōu)化它的原理，如果有必要的話，將遞歸的形式寫(xiě)成迭代的形式，通過(guò)迭代方式，降低重復(fù)值的計(jì)算，當(dāng)然了，這個(gè)過(guò)程，有時(shí)候是比較難的，值得我們?nèi)ニ伎肌?/p>
網(wǎng)站欄目：如何優(yōu)化尾調(diào)用
本文路徑：http://www.5511xx.com/article/cdsspgo.html
