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

2 人贊了文章

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

博客原文

遞歸概念

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

圖1：

圖2：

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

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

5! = 5 * 4 * 3 * 2 * 1function factorial(num) { if (num === 1) { // 基線條件 return 1; } // 遞歸條件 return num * factorial(num-1);}factorial(5);

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

調用棧

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

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);

直接看圖:

遞歸注意事項

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

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