簡單易懂的現代魔法-遞歸

Joyven 發布于2019-08-23 10:32 / 2630人閱讀

摘要：完整的一次調用流程遞歸調用棧遞歸同樣使用調用棧我們來分析下階乘的調用棧直接看圖遞歸注意事項遞歸會導致程序的性能變低如果遞歸嵌套很深，那么調用棧會很長，這將占用大量內存，可能會導致棧溢出

平時在前端開發中，好像也沒啥用到遞歸的地方。不過這并不代表遞歸不重要，如果你看過一些框架的源碼，就會經常見到它的影子：比如渲染虛擬DOM的render函數，webpack中require依賴分析，Koa2洋蔥式的中間件模型，其實都運用到了遞歸算法。

博客原文

遞歸概念

那么遞歸到底是啥？先上兩張圖：

圖1：

圖2：

遞歸，就是在運行的過程中調用自己

我們來看個最簡單的階乘函數：

5! = 5 * 4 * 3 * 2 * 1

function factorial(num) {
    if (num === 1) { // 基線條件
        return 1;
    }

    // 遞歸條件
    return num * factorial(num-1);
}

factorial(5);

一個常規的遞歸函數都有兩部分：

基線條件(if (num === 1))：保證函數不再調用自己，避免無限循環

遞歸條件(num * factorial(num-1))：保證函數能夠調用自己

調用棧

棧是一種先進后出的數據結構，它只有兩種操作，出棧和入棧

const nekopara = ["chocolat", "Coconut"];
nekopara.push("vanilla"); // 入棧
nekopara.pop(); // 出棧

代碼在運行過程中，會有一個叫做調用棧(call stack)的概念。

function greet(name) {
    console.log(`hello, ${name}!`)
    greet2(name);
    console.log(`getting ready to say bye`);
    bye();
}

function greet2(name) {
    console.log(`how are you, ${name}?`);
}

function bye() {
    console.log(`bye`);
}

greet("deepred");

調用greet("deepred")時，計算機會首先給該函數分配一塊內存，并將變量名name設置為deepred

每當調用函數時，都會分配一個內存塊并將涉及到的變量值存儲到內存中。

打印hello, deepred后，調用了greet2("deepred")。同樣，計算機再次分配了一塊內存，并且該內存塊位于第一個內存塊上面。

調用棧的最上面表示當前運行的函數，如圖所示，現在正在運行的是greet2函數，打印輸出how are you, deepred?后，函數greet2執行完畢，棧頂的內存塊被彈出。

現在棧頂的內存塊又變回greet，這意味著我們從greet2的函數中跳出，再次返回到了greet。

我們在greet中調用了greet2時，greet只執行了一部分。

特別注意：調用另外一個函數時，當前函數暫停并且處于未完成狀態，暫停函數的所有變量的值仍然在內存中。

執行完greet2后，我們回到了greet，并從離開的地方開始接著往下執行：首先打印getting ready to say bye，然后調用bye函數。

在棧頂添加了bye函數的內存塊后，開始執行bye函數，打印bye，然后函數返回，內存塊被彈出。

我們又再次回到了greet中，這次沒有其他要運行的代碼了，于是從greet函數中返回，內存塊被彈出，調用棧最后為空。

完整的一次調用流程：

遞歸調用棧

遞歸同樣使用調用棧

我們來分析下階乘fact(3)的調用棧

function fact(num) {
   if (num === 1) { 
       return 1;
   }
   return num * fact(num-1);
}

fact(3);

直接看圖:

遞歸注意事項

遞歸會導致程序的性能變低

如果遞歸嵌套很深，那么調用棧會很長，這將占用大量內存，可能會導致棧溢出

GPU云服務器云服務器創造與魔法云鳥便宜的服務器創造與魔法所有服務器的云鳥在哪易懂深度學習最易懂

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

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

用最簡單易懂的道理告訴你，為什么JavaScript在現代引擎（V8，JavaScriptCore）

摘要：代碼在本文最后，首先是，編譯出字節碼耗時約，運行字節碼耗時約，。也有解釋過程，字節碼需要由虛擬機解釋執行。而引擎的做法是更接近二哥的，在編譯階段的過程是源碼抽象語法樹字節碼中間代碼。于是大量的字節碼優化措施被延后，比如。簡單性能測試首先，我們先來做一個簡單的性能測試，對比一下Java，JavaScript，PHP，Ruby這四門語言。這個性能測試，是計算斐波那契數列（兔子數列）。比...

Moxmi 2019-08-19 18:21 評論0 收藏0
手摸手教你用 js 寫一個 js 解釋器

摘要：手摸手教你用寫一個解釋器用來編譯看起來是個高大上的東西，實際原理其實很簡單，無非就是利用對象屬性可以用字符串表示這個特性來實現的黑魔法罷了。手摸手教你用 js 寫一個 js 解釋器用 js 來編譯 js 看起來是個高大上的東西，實際原理其實很簡單，無非就是利用 js 對象屬性可以用字符串表示這個特性來實現的黑魔法罷了。之所以看起來那么深奧, 大概是由于網上現有的教程，都是動不...

hss01248 2019-08-23 17:04 評論0 收藏0
窺探 Script 標簽（步入現代 Web 開發的魔法世界）

摘要：而且默認帶有執行的順序是，，即便是內聯的，依然具有屬性。模塊腳本只會執行一次必須符合同源策略模塊腳本在跨域的時候默認是不帶的。通常被用作腳本被禁用的回退方案。最后標簽真的令人感到興奮。窺探 Script 標簽 0x01 什么是 script 標簽？ script 標簽允許你包含一些動態腳本或數據塊到文檔中，script 標簽是非閉合的，你也可以將動態腳本或數據塊當做 script 的...

Terry_Tai 2019-08-20 18:17 評論0 收藏0
窺探 Script 標簽（步入現代 Web 開發的魔法世界）

摘要：而且默認帶有執行的順序是，，即便是內聯的，依然具有屬性。模塊腳本只會執行一次必須符合同源策略模塊腳本在跨域的時候默認是不帶的。通常被用作腳本被禁用的回退方案。最后標簽真的令人感到興奮。窺探 Script 標簽 0x01 什么是 script 標簽？ script 標簽允許你包含一些動態腳本或數據塊到文檔中，script 標簽是非閉合的，你也可以將動態腳本或數據塊當做 script 的...

gaosboy 2019-08-01 17:13 評論0 收藏0