JavaScript尾遞歸優化探索

sean 發布于2019-08-22 18:27 / 2888人閱讀

摘要：原文地址尾調優化在知道尾遞歸之前，我們要直到什么是尾調用優化，因為尾調用優化是尾遞歸的基礎。尾遞歸優化，就是利用尾調用優化的原理，對遞歸進行優化。所以當我們使用尾遞歸進行優化的時候，依舊發生了棧溢出的錯誤。

原文地址：https://github.com/HolyZheng/...

尾調優化

在知道尾遞歸之前，我們要直到什么是尾調用優化，因為尾調用優化是尾遞歸的基礎。尾調用就是：在函數的最后一步調用另一個函數。

function f() {
  return g()
}

ps：最后一步必須是之久調用另一函數，而不能是一個常量或是一個表達式，如 return y 或 return g() + 1

尾調用優化的原理是什么？

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

這里的“調用幀”和“調用棧”，說的應該就是“執行環境”和“作用域鏈”。因為尾調用時函數的最后一部操作，所以不再需要保留外層的調用幀，而是直接取代外層的調用幀，所以可以起到一個優化的作用。

尾遞歸優化

我們知道，遞歸雖然使用起來方便，但是遞歸是在函數內部調用自身，當遞歸次數達到一定數量級的時候，他形成的調用棧的深度是很可怕的，很可能會發生“棧溢出”錯誤。尾遞歸優化，就是利用尾調用優化的原理，對遞歸進行優化。舉一個很常見的例子：
求斐波那契數值

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

此函數沒有進行任何的優化，當我們在控制臺去執行此函數的時候，fibonacci(40)就已經出現了明顯的響應慢的問題，fibonacci(50)的時候瀏覽器卡死。
優化

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

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

局限性

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

蹦床函數

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

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

代碼修改為返回一個新函數。

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

兩個函數結合就可以將遞歸狀態為循環，棧溢出的問題也就解決了。

trampoline(fibonacci (100000))
// Infinity

GPU云服務器云服務器優化遞歸數據棧 javascript優化 JavaScript代碼優化尾隊列

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/95881.html

ES6函數與Lambda演算

摘要：高階函數函數式編程中，接受函數作為參數，或者返回一個函數作為結果的函數通常就被稱為高階函數。均屬于高階函數，高階函數并不神秘，我們日常編程也會用到。參考演算函數式編程指南入門康托爾哥德爾圖靈永恒的金色對角線原文函數與演算緣起造了一個輪子，根據GitHub項目地址，生成項目目錄樹，直觀的展現項目結構，以便于介紹項目。歡迎Star。 repository-tree 技術棧： ES6 ...

fasss 2019-08-21 18:45 評論0 收藏0
ES6被你忽略的尾調用

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

xeblog 2019-08-22 11:04 評論0 收藏0
用 JavaScript 實現鏈表操作 - 08 Remove Duplicates

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

Me_Kun 2019-08-21 15:04 評論0 收藏0
js 實現斐波那契數列(數組緩存、動態規劃、尾調用優化)

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

趙連江 2019-08-23 11:38 評論0 收藏0
翻譯連載 | 第 9 章：遞歸（下）－《JavaScript輕量級函數式編程》 |《你不知道的JS》

摘要：每個函數調用都將開辟出一小塊稱為堆棧幀的內存。當第二個函數開始執行，堆棧幀增加到個。當這個函數調用結束后，它的幀會從堆棧中退出。保持堆棧幀跟蹤函數調用的狀態，并將其分派給下一個遞歸調用迭。原文地址：Functional-Light-JS 原文作者：Kyle Simpson－《You-Dont-Know-JS》作者關于譯者：這是一個流淌著滬江血液的純粹工程：認真，是 HTM...

LeviDing 2019-08-21 16:44 評論0 收藏0