迎接ECMAScript 6, 使用尾遞歸

whatsns 發布于2019-08-21 10:21 / 1844人閱讀

摘要：而且最的是，在，我們將迎來尾遞歸優化，享受只有這些古典函數式語言才擁有的能力。使用尾遞歸這里有一個使用尾遞歸提取絕對文件名的例子，可以來展示下尾遞歸的魅力。

尾調用，是指函數內部的最后一個動作是函數調用。該調用的返回值，直接返回給函數。

Example:

function sum(x) {
    return sum(x + 1);
}

這里的 sum() 內部的 sum 就是屬于尾調用，ta 所返回的值直接返回給調用 ta 的上層 sum() 函數。

function sum(x) {
    return 1 + sum(x + 1);
}

這里的 sum() 內部的 sum 就不屬于尾調用，ta 所返回的值在返回給調用 ta 的上層 sum() 函數之前，需要先跟 1 計算和，然后再返回。

尾調用和非尾調用有什么差異？

編寫一個求和函數，有大致3種方式:

循環

function sum(x) {
    var result = x;
    while (x >= 1) {
        result += --x;
    }
    return result;
}

循環自然是速度和性能最好的，但是在編寫復雜的代碼時，循環往往模塊化很差，可讀性很差，而且無法體現數學上的描述。

普通遞歸

function sum(x) {
    if (x === 1) {
        return 1;
    }
    return x + sum(--x);
}

普通遞歸時，內存需要記錄調用的堆棧所出的深度和位置信息。在最底層計算返回值，再根據記錄的信息，跳回上一層級計算，然后再跳回更高一層，依次運行，直到最外層的調用函數。在cpu計算和內存會消耗很多，而且當深度過大時，會出現堆棧溢出。

比如，計算 sum(5) 的時候，其計算過程是這樣的:

sum(5)
(5 + sum(4))
(5 + (4 + sum(3)))
(5 + (4 + (3 + sum(2))))
(5 + (4 + (3 + (2 + sum(1)))))
(5 + (4 + (3 + (2 + 1))))
(5 + (4 + (3 + 3)))
(5 + (4 + 6))
(5 + 10)
15

在計算的過程中，堆棧一直不停的記錄每一層次的詳細信息，以確保該層次的操作完成，能返回到上一層次。

通過尾遞歸，可以取消過多的堆棧記錄，而只記錄最外層和當前層的信息，完成計算后，立刻返回到最上層。從而減少 cpu 計算和內存消耗。

尾遞歸

function sum(x, total) {
    if (x === 1) {
        return x + total;
    }
    return sum(--x, x + total);
}

這個函數更具有數學描述性:

如果輸入值是1 => 當前計算數1 + 上一次計算的和total

如果輸入值是x => 當前計算數x + 上一次計算的和total

計算 sum(5, 0)的時候，其過程是這樣的:

sum(5, 0)
sum(4, 5)
sum(3, 9)
sum(2, 12)
sum(1, 14)
15

整個計算過程是線性的，調用一次 sum(x, total) 后，會進入下一個棧，相關的數據信息和跟隨進入，不再放在堆棧上保存。當計算完最后的值之后，直接返回到最上層的 sum(5,0)。

這能有效的防止堆棧溢出。

而且最happy的是，在ECMAScript 6，我們將迎來尾遞歸優化，享受只有LISP
HASKELL這些古典函數式語言才擁有的能力。通過尾遞歸優化，javascript代碼在解釋成機器碼的時候，將會向while看起，也就是說，同時擁有數學表達能力和while的效能。

使用尾遞歸

這里有一個使用尾遞歸提取絕對文件名的例子，可以來展示下尾遞歸的魅力。這個函數需要輸入一個(或幾個)目錄名和當前所在的文件位置，然后會遞歸提取目錄下的所有文件名，放入一個棧中。

var FS = require("fs");
var PATH = require("path");

function readSync(paths, i) {
    if (i >= 0 && i < paths.length) {
        var stats = FS.statSync(paths[i]);
        if (stats.isFile()) {
            return readSync(paths, ++i);
        } else if (stats.isDirectory()) {
            var newPaths = FS.readdirSync(paths[i]).map(function (path) {
                return PATH.join(paths[i],path);
            });
            return readSync(paths.slice(0, i).concat(newPaths, 
                                                     paths.slice(i + 1)), 
                            i);
        } else {
            return readSync(paths.slice(0, i).concat(paths.slice(i + 1)), 
                            i);
        }
    } else {
        return paths;
    }
}

測試一下，這個函數可以在服務器啟動時，提取某一個(或者幾個)目錄內的所有文件，然后用于編譯或者是其他的操作。

readSync([PATH.join(__dirname, "./tpls")], 0).forEach(function (path) {
    console.log(path);
});
readSync([PATH.join(__dirname, "./tpls"), PATH.join(__dirname, "./pages")], 0).forEach(function (path) {
    console.log(path);
});

文章來源：http://www.jianshu.com/p/269ba1ba1644

GPU云服務器云服務器 ECMAScript 6 迎接云計算時代的到來 ECMAScript 尾隊列

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

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

《javascript語言精粹》學習筆記 - 遞歸函數

摘要：遞歸函數就是會直接或者間接地調用自身的一種函數。一般來說，一個遞歸函數調用自身去解決它的子問題。書上第二個例子是說遞歸函數可以非常高效率的操作樹形結構，比如。有一些語言提供了尾遞歸的優化。好運的是，給我們帶來了尾遞歸，詳細迎接使用尾遞歸。遞歸函數就是會直接或者間接地調用自身的一種函數。遞歸是一種強大的編程技術，它把一問題分解為一組相似的子問題，每一個都用一個尋常解去解決。一般來...

Ryan_Li 2019-08-21 10:28 評論0 收藏0
Javascript 深入學習循環

摘要：遞歸函數還會受到瀏覽器調用棧的大小的限制。雖然迭代也會導致性能問題，但是使用優化的循環就可以代替長時間運行的遞歸函數，可以提高新能，因為運行一個循環比反復調用一個函數的開銷要小。本文章記錄本人在深入學習js循環中看書理解到的一些東西，加深記憶和并且整理記錄下來，方便之后的復習。選擇正確的循環體在大部分編程語言中，代碼執行的時間多數消耗在循環的執行上。 js定義了4種...

Cristalven 2019-08-22 10:57 評論0 收藏0
ECMAScript6 新特性——“函數的擴展”

摘要：返回空字符串，返回將一個具名函數賦值給一個變量，則和的屬性都返回這個具名函數原本的名字。不可以使用對象，該對象在函數體內不存在。等到運行結束，將結果返回到，的調用幀才會消失。 1 函數參數的默認值 ES6允許為函數的參數設置默認值，即直接寫在參數定義的后面： function log(x = message.,y = duration infomation.) { consol...

Jiavan 2019-08-19 18:04 評論0 收藏0
JS的函數調用棧有多深？

摘要：中尾遞歸優化支持尾遞歸優化如果一個函數的最后一個操作是函數調用，那么將會用跳轉而不是子調用。自從年雙十一正式上線，累計處理了億錯誤事件，付費客戶有陽光保險核桃編程荔枝掌門對微脈青團社等眾多知名企業。譯者按：有時候會遇到Maximum call stack size exceeded的問題，本文教你stack size的計算方法。原文: The maximum call stac...

AprilJ 2019-08-22 18:20 評論0 收藏0
ES6學習第七章函數的擴展

摘要：前言本章介紹函數的擴展。形式為變量名，函數的最后一個命名參數以為前綴。規定只要函數參數使用了默認值解構賦值或者擴展運算符，那么函數內部就不能顯式設定為嚴格模式，否則會報錯。箭頭函數不能用作構造函數。尾遞歸函數調用自身，稱為遞歸。前言本章介紹函數的擴展。有些不常用的知識了解即可。本章原文鏈接：函數的擴展。函數參...

番茄西紅柿 2021-11-29 10:50 評論0 收藏2637