從JS角度直觀理解遞歸的本質

讓我們寫一個函數 pow(x, n)，它可以計算 x 的 n 次方。換句話說就是，x 乘以自身 n 次。

有兩種實現方式。

迭代思路：使用 for 循環：

function pow(x, n) {let result = 1;// 在循環中，用 x 乘以 result n 次for (let i = 0; i < n; i++) {result *= x;}return result;
}alert( pow(2, 3) ); // 8

遞歸思路：簡化任務，調用自身：

function pow(x, n) {if (n == 1) {return x;} else {return x * pow(x, n - 1);}
}alert( pow(2, 3) ); // 8

當 pow(x, n) 被調用時，執行分為兩個分支：

              if n==1  = x/
pow(x, n) =\else     = x * pow(x, n - 1)

如果 n == 1，所有事情都會很簡單，這叫做基礎的遞歸，因為它會立即產生明顯的結果：pow(x, 1) 等于 x。
否則，我們可以用 x * pow(x, n - 1) 表示 pow(x, n)。在數學里，可能會寫為 xn = x * xn-1。這叫做 一個遞歸步驟：我們將任務轉化為更簡單的行為（x 的乘法）和更簡單的同類任務的調用（帶有更小的 n 的 pow 運算）。接下來的步驟將其進一步簡化，直到 n 達到 1。

這是一個很簡單的例子，我們從直覺上很容易理解遞歸，但是有很多人會有一種不可名狀的困惑，這個問題可以總結為“為什么會這樣？”

現在我們來研究一下遞歸調用是如何工作的。為此，我們會先看看函數底層的工作原理。

有關正在運行的函數的執行過程的相關信息被存儲在其執行上下文中。

執行上下文是一個內部數據結構，它包含有關函數執行時的詳細細節：當前控制流所在的位置，當前的變量，this的值（此處我們不使用它），以及其它的一些內部細節。

一個函數調用僅具有一個與其相關聯的執行上下文。

當一個函數進行嵌套調用時，將發生以下的事兒：

當前函數被暫停；
與它關聯的執行上下文被一個叫做執行上下文堆棧的特殊數據結構保存；
執行嵌套調用；
嵌套調用結束后，從堆棧中恢復之前的執行上下文，并從停止的位置恢復外部函數。

讓我們看看 pow(2, 3) 調用期間都發生了什么。

pow(2, 3)

在調用 pow(2, 3) 的開始，執行上下文（context）會存儲變量：x = 2, n = 3，執行流程在函數的第 1 行。

我們將其描繪如下：

Context: { x: 2, n: 3, at line 1 } pow(2, 3)

這是函數開始執行的時候。條件 n == 1 結果為假，所以執行流程進入 if 的第二分支。

function pow(x, n) {if (n == 1) {return x;} else {return x * pow(x, n - 1);}
}alert( pow(2, 3) );

變量相同，但是行改變了，因此現在的上下文是：

Context: { x: 2, n: 3, at line 5 } pow(2, 3)

為了計算 x * pow(x, n - 1)，我們需要使用帶有新參數的新的 pow 子調用 pow(2, 2)。

pow(2, 2)

為了執行嵌套調用，JavaScript 會在 執行上下文堆棧 中記住當前的執行上下文。

這里我們調用相同的函數 pow，但這絕對沒問題。所有函數的處理都是一樣的：

當前上下文被“記錄”在堆棧的頂部。
為子調用創建新的上下文。
當子調用結束后 —— 前一個上下文被從堆棧中彈出，并繼續執行。

下面是進入子調用 pow(2, 2) 時的上下文堆棧：

Context: { x: 2, n: 2, at line 1 } pow(2, 2)
Context: { x: 2, n: 3, at line 5 } pow(2, 3)

新的當前執行上下文位于頂部（粗體顯示），之前記住的上下文位于下方。

當我們完成子調用后 —— 很容易恢復上一個上下文，因為它既保留了變量，也保留了當時所在代碼的確切位置。

請注意：

在上面的圖中，我們使用“行（line）”一詞，因為在我們的示例中，每一行只有一個子調用，但通常一行代碼可能會包含多個子調用，例如 pow(…) + pow(…) + somethingElse(…)。

因此，更準確地說，執行是“在子調用之后立即恢復”的。

pow(2, 1)

重復該過程：在第 5 行生成新的子調用，現在的參數是 x=2, n=1。

新的執行上下文被創建，前一個被壓入堆棧頂部：

Context: { x: 2, n: 1, at line 1 } pow(2, 1)
Context: { x: 2, n: 2, at line 5 } pow(2, 2)
Context: { x: 2, n: 3, at line 5 } pow(2, 3)

此時，有 2 個舊的上下文和 1 個當前正在運行的 pow(2, 1) 的上下文。

出口

在執行 pow(2, 1) 時，與之前的不同，條件 n == 1 為真，因此 if 的第一個分支生效：

function pow(x, n) {if (n == 1) {return x;} else {return x * pow(x, n - 1);}
}

此時不再有更多的嵌套調用，所以函數結束，返回 2。

函數完成后，就不再需要其執行上下文了，因此它被從內存中移除。前一個上下文恢復到堆棧的頂部：

Context: { x: 2, n: 2, at line 5 } pow(2, 2)
Context: { x: 2, n: 3, at line 5 } pow(2, 3)

恢復執行 pow(2, 2)。它擁有子調用 pow(2, 1) 的結果，因此也可以完成 x * pow(x, n - 1) 的執行，并返回 4。

然后，前一個上下文被恢復：

Context: { x: 2, n: 3, at line 5 } pow(2, 3)

當它結束后，我們得到了結果 pow(2, 3) = 8。

本示例中的遞歸深度為：3。

從上面的解釋我們可以看出，遞歸深度等于堆棧中上下文的最大數量。

請注意內存要求。上下文占用內存，在我們的示例中，求 n 次方需要存儲 n 個上下文，以供更小的 n 值進行計算使用。

而循環算法更節省內存：

function pow(x, n) {let result = 1;for (let i = 0; i < n; i++) {result *= x;}return result;
}

迭代 pow 的過程中僅使用了一個上下文用于修改 i 和 result。它的內存要求小，并且是固定了，不依賴于 n。

任何遞歸都可以用循環來重寫。通常循環變體更有效。

但有時重寫很難，尤其是函數根據條件使用不同的子調用，然后合并它們的結果，或者分支比較復雜時。而且有些優化可能沒有必要，完全不值得。

遞歸可以使代碼更短，更易于理解和維護。并不是每個地方都需要優化，大多數時候我們需要一個好代碼，這就是為什么要使用它。

既然循環更好，為什么要使用遞歸，接下來舉個例子。

遞歸的另一個重要應用就是遞歸遍歷。

假設我們有一家公司。人員結構可以表示為一個對象：

let company = {sales: [{name: 'John',salary: 1000}, {name: 'Alice',salary: 1600}],development: {sites: [{name: 'Peter',salary: 2000}, {name: 'Alex',salary: 1800}],internals: [{name: 'Jack',salary: 1300}]}
};

換句話說，一家公司有很多部門。

一個部門可能有一數組的員工，比如，sales 部門有 2 名員工：John 和 Alice。
或者，一個部門可能會劃分為幾個子部門，比如 development 有兩個分支：sites 和 internals，它們都有自己的員工。
當一個子部門增長時，它也有可能被拆分成幾個子部門（或團隊）。
例如，sites 部門在未來可能會分為 siteA 和 siteB。并且，它們可能會被再繼續拆分。沒有圖示，腦補一下吧。

現在，如果我們需要一個函數來獲取所有薪資的總數。我們該怎么做？

迭代方式并不容易，因為結構比較復雜。首先想到的可能是在 company 上使用 for 循環，并在第一層部分上嵌套子循環。但是，之后我們需要更多的子循環來遍歷像 sites 這樣的二級部門的員工…… 然后，將來可能會出現在三級部門上的另一個子循環？如果我們在代碼中寫 3-4 級嵌套的子循環來遍歷單個對象，那代碼得多丑啊。

我們試試遞歸吧。

我們可以看到，當我們的函數對一個部門求和時，有兩種可能的情況：

要么是由一個人員數組構成的“簡單”的部門 —— 這樣我們就可以通過一個簡單的循環來計算薪資的總和。
或者它是一個有 N 個子部門的對象 —— 那么我們可以通過 N 層遞歸調用來求每一個子部門的薪資，然后將它們合并起來。

第一種情況是由人員數組構成的部門，這種情況很簡單，是最基礎的遞歸。

第二種情況是我們得到的是對象。那么可將這個復雜的任務拆分成適用于更小部門的子任務。它們可能會被繼續拆分，但很快或者不久就會拆分到第一種情況那樣。

這個算法從代碼來看可能會更簡單：

let company = { // 是同一個對象，簡潔起見被壓縮了sales: [{name: 'John', salary: 1000}, {name: 'Alice', salary: 1600 }],development: {sites: [{name: 'Peter', salary: 2000}, {name: 'Alex', salary: 1800 }],internals: [{name: 'Jack', salary: 1300}]}
};// 用來完成任務的函數
function sumSalaries(department) {if (Array.isArray(department)) { // 情況（1）return department.reduce((prev, current) => prev + current.salary, 0); // 求數組的和} else { // 情況（2）let sum = 0;for (let subdep of Object.values(department)) {sum += sumSalaries(subdep); // 遞歸調用所有子部門，對結果求和}return sum;}
}alert(sumSalaries(company)); // 7700