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

Ryan_Li 發布于2019-08-21 10:28 / 3392人閱讀

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

遞歸函數就是會直接或者間接地調用自身的一種函數。遞歸是一種強大的編程技術，它把一問題分解為一組相似的子問題，每一個都用一個尋常解去解決。一般來說，一個遞歸函數調用自身去解決它的子問題。

書上的一個小例子“漢諾塔”。塔上有3根柱子和一個套直徑都不同的空心圓盤。開始時源柱子的所有圓盤都按照從小到大的順序堆疊。目標是每次移動一個圓盤到另一根柱子，最終把一堆圓盤移動到目標柱子上，期間不允許把較大的圓盤放在較小的圓盤上。

 var hanoi = function(disc, src, aux, dst){
    if (disc > 0) {
        hanoi(disc - 1, src, dst, aux);
        document.writeln("Move disc" + disc + " form " + src + " to " + dst);
        hanoi(disc - 1, aux, src, dst);
    }
};

hanoi(3, "src", "aux", "dst");

運行代碼結果：

Move disc1 form src to dst
Move disc2 form src to aux
Move disc1 form dst to aux
Move disc3 form src to dst
Move disc1 form aux to src
Move disc2 form aux to dst
Move disc1 form src to dst

hanoi函數把一堆圓盤從一根柱子移動到另外一根柱子，必要使用輔助的柱子。它把該問題拆分成3個小問題。它先移動到一對圓盤中較小的圓盤到輔助柱子上，從而露出下面較大的圓盤，然后移動下面的圓盤到目標柱子上。最后，他將剛才較小的圓盤從輔助柱子上再移動到目標柱子上。通過遞推地調用自身去處理一堆圓盤的移動，從而解決那些問題。

傳遞給hanoi函數的參數包括當前移動的圓盤的編號和它將要用到的3根柱子。當它調用自身的時候，它去處理當前正在處理的圓盤之上的圓盤。最終，他會一個不存在的圓盤編號去調用。在這樣的情況下，他不執行任何操作。由于該函數對非法只不理會，也不用擔心死循環的問題。

書上第二個例子是說遞歸函數可以非常高效率的操作樹形結構，比如DOM。每次遞歸調用是處理指定的樹的一小段。

// 它從某個指定的節點開始，按照 HTML 源碼中的順序訪問該數的每個節點。
var walk_the_DOM = function(node, func){
    func(node);
    node = node.firstChild;
    while (node) {
        walk_the_DOM(node, func);
        node = node.nextSibling;
    }
};

// 它調用 walk_the_DOM 函數，傳遞一個用來查找節點屬性名的函數為參數。
// 匹配的節點會累加到一個結果數組里面。
var getElementsByAttribute = function(att, val){
    var results = [];

    walk_the_DOM(document.body, function(node){
        var actual = node.nodeType === 1 && node.getAttribute(att);
        if (typeof actual === "string" && (actual === val || typeof value 
            != "string")) {
            results.push(node);
        }
    });

    return results;
};

有一些語言提供了尾遞歸的優化。這意味著如果一個函數返回自身遞歸的結果，那么調用的過程會被替換成以循環，可以提高速度?？上?b>js并沒有尾遞歸的優化。

好運的是，ES6給我們帶來了尾遞歸，詳細迎接ECMAScript 6, 使用尾遞歸。
拓展：什么情況下用遞歸？。

云服務器 GPU云服務器 javascript語言精粹 javascript學習筆記 javascript精粹 javascript編程精粹

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

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

《JavaScript 語言精粹》讀書筆記 - 函數（二）

摘要：對象被傳遞到從句中被捕獲。一些語言提供了尾遞歸優化。這意味著如果一個函數返回自身遞歸調用的結果，那么調用的過程會被替換為一個循環，可以顯著提高速度。構建一個帶尾遞歸的函數。語言精粹讀書筆記函數第四章函數 Functions （二）參數 arguments arguments數組：函數可以通過此參數訪問所有它被調用時傳遞給它的參數列表，包括哪些沒有被分配給函數聲明時定義的形式參數...

lufficc 2019-08-22 15:10 評論0 收藏0
【閱讀筆記】JavaScript語言精粹

摘要：對之前看高級程序設計時沒有注意到的一些知識點，結合本書做以補充語法注釋源于的型既可以出現在字符串字面量中，也可能出現在正則表達式字面量中，如故一般建議使用型注釋保留字語句變量參數屬性名運算符和標記等標識符不允許使用保留字，此外在對象字面量中對之前看《JavaScript高級程序設計》時沒有注意到的一些知識點，結合本書做以補充語法注釋源于PL/I的/* */型既可以出現在字符串字...

cucumber 2019-08-20 17:27 評論0 收藏0
《JavaScript 語言精粹》讀書筆記 - 函數

摘要：語言精粹讀書筆記第四章函數函數字面量函數字面量包含個部分第一部分，保留字第二部分，函數名，它可以被忽略。這個超級延遲綁定使得函數對高度復用。構造器調用模式一個函數，如果創建的目的就是希望結合的前綴來調用，那它就被稱為構造器構造。《JavaScript 語言精粹》讀書筆記第四章函數 Functions 函數字面量函數字面量包含4個部分：第一部分，保留字 function...

wdzgege 2019-08-22 14:54 評論0 收藏0
《JavaScript語言精粹修訂版》讀書筆記

摘要：于是我就先把這本薄的經典書語言精粹修訂版豆瓣讀書本書簡介總共章，除去附錄，才頁，讀完并記錄了一些筆記。讀書筆記還可以分享給別人看。編程語言第版定義了的標準。程序檢查時丟棄值為函數的屬性。之前看到這篇文章，前端網老姚淺談：怎么學JavaScript？，說到怎么學習JavaScript，那就是看書、分析源碼。10本書讀2遍的好處，應該大于一本書讀20遍?？磿鲃訉W習，看視頻是被動學習?？?..

EscapedDog 2019-08-20 18:15 評論0 收藏0
《javascript語言精粹》學習筆記 - 繼承

摘要：但采用構造器調用模式，即是使用了前綴去調用一個函數時，函數執行的方式會改變。對象包含構造器需要構造一個新的實例的所有信息。構造器的變量和內部函數變成了該實例的私有成員。 JavaScript 是一門弱類型語言，從不需要類型轉換。對象繼承關系變得無關緊要。對于一個對象來說重要的時它能夠做什么，而不是它從哪里來。閱讀《javascript語言精粹》筆記！偽類 js的原型存...

harriszh 2019-08-21 10:27 評論0 收藏0