国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

JavaScript尾遞歸優(yōu)化探索

sean / 2887人閱讀

摘要：原文地址尾調(diào)優(yōu)化在知道尾遞歸之前，我們要直到什么是尾調(diào)用優(yōu)化，因?yàn)槲舱{(diào)用優(yōu)化是尾遞歸的基礎(chǔ)。尾遞歸優(yōu)化，就是利用尾調(diào)用優(yōu)化的原理，對遞歸進(jìn)行優(yōu)化。所以當(dāng)我們使用尾遞歸進(jìn)行優(yōu)化的時(shí)候，依舊發(fā)生了棧溢出的錯誤。

原文地址：https://github.com/HolyZheng/...
尾調(diào)優(yōu)化

在知道尾遞歸之前，我們要直到什么是尾調(diào)用優(yōu)化，因?yàn)槲舱{(diào)用優(yōu)化是尾遞歸的基礎(chǔ)。尾調(diào)用就是：在函數(shù)的最后一步調(diào)用另一個函數(shù)。

function f() {
  return g()
}
ps：最后一步必須是之久調(diào)用另一函數(shù)，而不能是一個常量或是一個表達(dá)式，如 return y 或 return g() + 1
尾調(diào)用優(yōu)化的原理是什么？

按照阮一峰老師在es6的函數(shù)擴(kuò)展中的解釋就是：函數(shù)調(diào)用會在內(nèi)存形成一個“調(diào)用記錄”，又稱“調(diào)用幀”（call frame），保存調(diào)用位置和內(nèi)部變量等信息。如果在函數(shù)A的內(nèi)部調(diào)用函數(shù)B，那么在A的調(diào)用幀上方，還會形成一個B的調(diào)用幀。等到B運(yùn)行結(jié)束，將結(jié)果返回到A，B的調(diào)用幀才會消失。如果函數(shù)B內(nèi)部還調(diào)用函數(shù)C，那就還有一個C的調(diào)用幀，以此類推。所有的調(diào)用幀，就形成一個“調(diào)用棧”（call stack）。

這里的“調(diào)用幀”和“調(diào)用棧”，說的應(yīng)該就是“執(zhí)行環(huán)境”和“作用域鏈”。因?yàn)槲舱{(diào)用時(shí)函數(shù)的最后一部操作，所以不再需要保留外層的調(diào)用幀，而是直接取代外層的調(diào)用幀，所以可以起到一個優(yōu)化的作用。

尾遞歸優(yōu)化

我們知道，遞歸雖然使用起來方便，但是遞歸是在函數(shù)內(nèi)部調(diào)用自身，當(dāng)遞歸次數(shù)達(dá)到一定數(shù)量級的時(shí)候，他形成的調(diào)用棧的深度是很可怕的，很可能會發(fā)生“棧溢出”錯誤。尾遞歸優(yōu)化，就是利用尾調(diào)用優(yōu)化的原理，對遞歸進(jìn)行優(yōu)化。舉一個很常見的例子：
求斐波那契數(shù)值

function fibonacci (n) {
    return n <= 1 ? 1 : fibonacci(n - 1) + fibonacci(n - 2);
}

此函數(shù)沒有進(jìn)行任何的優(yōu)化，當(dāng)我們在控制臺去執(zhí)行此函數(shù)的時(shí)候，fibonacci(40)就已經(jīng)出現(xiàn)了明顯的響應(yīng)慢的問題，fibonacci(50)的時(shí)候?yàn)g覽器卡死。
優(yōu)化

function fibonacci (n, ac1, ac2) {
    (ac1 = ac1 || 1), (ac2 = ac2 || 1);
    return n <= 1 ? ac2 :fibonacci(n - 1, ac2, ac1 + ac2);
}

此優(yōu)化有兩個點(diǎn)：首先進(jìn)行了算法上的優(yōu)化，減少了很多重復(fù)的計(jì)算，時(shí)間復(fù)雜度大大降低；第二進(jìn)行了尾遞歸優(yōu)化，按理說不會發(fā)生“棧溢出”。我們可以到控制臺中再嘗試，發(fā)現(xiàn)速度的提升不是一般的快，證明第一個優(yōu)化生效了，但是當(dāng)我們允許fibonacci(10000)的時(shí)候，報(bào)錯了：Uncaught RangeError: Maximum call stack size exceeded，這就說明我們的尾遞歸優(yōu)化并沒有生效。為什么呢？

局限性

上面說到，我們直接再瀏覽器的控制臺中執(zhí)行fibonacci(10000)的時(shí)候，發(fā)生了棧溢出，這是為什么呢？關(guān)于這一點(diǎn)，我目前查閱資料之后的理解就是，雖然es6已經(jīng)提出了要實(shí)現(xiàn)尾遞歸優(yōu)化，但是真正落地實(shí)現(xiàn)了尾遞歸優(yōu)化的瀏覽器并不多。所以當(dāng)我們使用尾遞歸進(jìn)行優(yōu)化的時(shí)候，依舊發(fā)生了“棧溢出”的錯誤。

蹦床函數(shù)

那怎么辦呢？我們還有另一個方法去達(dá)到尾遞歸優(yōu)化的效果，那就是使用蹦床函數(shù)(trampoline)。

function trampoline(f) {
  while (f && f instanceof Function) {
    f = f();
  }
  return f;
}

代碼修改為返回一個新函數(shù)。

function fibonacci (n, ac1, ac2) {
    (ac1 = ac1 || 1), (ac2 = ac2 || 1);
    return n <= 1 ? ac2 :fibonacci.bind(null, n - 1, ac2, ac1 + ac2);
}

兩個函數(shù)結(jié)合就可以將遞歸狀態(tài)為循環(huán)，棧溢出的問題也就解決了。

trampoline(fibonacci (100000))
// Infinity

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/95881.html

相關(guān)文章

  • ES6函數(shù)與Lambda演算

    摘要：高階函數(shù)函數(shù)式編程中，接受函數(shù)作為參數(shù)，或者返回一個函數(shù)作為結(jié)果的函數(shù)通常就被稱為高階函數(shù)。均屬于高階函數(shù)，高階函數(shù)并不神秘，我們?nèi)粘＞幊桃矔玫健⒖佳菟愫瘮?shù)式編程指南入門康托爾哥德爾圖靈永恒的金色對角線原文函數(shù)與演算 緣起 造了一個輪子，根據(jù)GitHub項(xiàng)目地址，生成項(xiàng)目目錄樹，直觀的展現(xiàn)項(xiàng)目結(jié)構(gòu)，以便于介紹項(xiàng)目。歡迎Star。 repository-tree 技術(shù)棧： ES6 ...

    fasss 評論0 收藏0

  • ES6被你忽略的尾調(diào)用

    摘要：被你忽略的尾調(diào)用尾調(diào)用是什么在有一個新特性尾調(diào)用用最簡單的一句話描述就是某個函數(shù)的最后一步再調(diào)用另一個函數(shù)，聽起來挺簡單的，但是它的功能特別強(qiáng)大，直接給你擼個例子吧。如果函數(shù)內(nèi)部還調(diào)用函數(shù)，那就還有一個的調(diào)用記錄棧，以此類推。 title: 被你忽略的‘尾調(diào)用’date: 2017-05-02 16:52:22 tags: [ES6,javascript] 尾調(diào)用是什么？ 在ES6有...

    xeblog 評論0 收藏0

  • 用 JavaScript 實(shí)現(xiàn)鏈表操作 - 08 Remove Duplicates

    摘要：遞歸版本尾遞歸很多遞歸沒辦法自然的寫成尾遞歸，本質(zhì)原因是無法在多次遞歸過程中維護(hù)共有的變量，這也是循環(huán)的優(yōu)勢所在。這是因?yàn)殡m然用的，但并沒有開啟尾遞歸優(yōu)化。 TL;DR 為一個已排序的鏈表去重，考慮到很長的鏈表，需要尾調(diào)用優(yōu)化。系列目錄見 前言和目錄 。 需求 實(shí)現(xiàn)一個 removeDuplicates() 函數(shù)，給定一個升序排列過的鏈表，去除鏈表中重復(fù)的元素，并返回修改后的鏈表。理想...

    Me_Kun 評論0 收藏0

  • js 實(shí)現(xiàn)斐波那契數(shù)列(數(shù)組緩存、動態(tài)規(guī)劃、尾調(diào)用優(yōu)化)

    摘要：根據(jù)該規(guī)則，返回第個斐波那契數(shù)。尾遞歸函數(shù)調(diào)用自身，稱為遞歸。一個前端眼中的斐波那契數(shù)列解斐波那契數(shù)列的實(shí)用解法調(diào)用棧尾遞歸和手動優(yōu)化尾調(diào)用優(yōu)化譯我從用寫斐波那契生成器中學(xué)到的令人驚訝的件事 斐波那契數(shù)列是以下一系列數(shù)字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在種子數(shù)字 0 和 1 ...

    趙連江 評論0 收藏0

  • 翻譯連載 | 第 9 章：遞歸（下）－《JavaScript輕量級函數(shù)式編程》 |《你不知道的JS》

    摘要：每個函數(shù)調(diào)用都將開辟出一小塊稱為堆棧幀的內(nèi)存。當(dāng)?shù)诙€函數(shù)開始執(zhí)行，堆棧幀增加到個。當(dāng)這個函數(shù)調(diào)用結(jié)束后，它的幀會從堆棧中退出。保持堆棧幀跟蹤函數(shù)調(diào)用的狀態(tài)，并將其分派給下一個遞歸調(diào)用迭。 原文地址：Functional-Light-JS 原文作者：Kyle Simpson－《You-Dont-Know-JS》作者 關(guān)于譯者：這是一個流淌著滬江血液的純粹工程：認(rèn)真，是 HTM...

    LeviDing 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<