遞迴和堆疊

讓我們回到函式，並更深入地研究它們。

我們的第一個主題將是遞迴。

如果你不是程式設計新手，那麼它可能很熟悉，你可以跳過本章節。

遞迴是一種程式設計模式，適用於任務可以自然地拆分成數個同類但較簡單的任務的情況。或者當一個任務可以簡化成一個簡單的動作加上同一個任務的較簡單變體時。或者，正如我們很快就會看到的，用於處理某些資料結構。

當一個函式解決一個任務時，在處理過程中它可以呼叫許多其他函式。其中一個部分案例是當一個函式呼叫它自己時。這稱為遞迴。

兩種思考方式

從簡單的事情開始 – 讓我們寫一個函式 `pow(x, n)`，將 `x` 提升到 `n` 的自然次方。換句話說，將 `x` 乘以它自己 `n` 次。

pow(2, 2) = 4
pow(2, 3) = 8
pow(2, 4) = 16

有兩種方法可以實作它。

1. 反覆思考：`for` 迴圈

   function pow(x, n) {
     let result = 1;
   
     // multiply result by x n times in the loop
     for (let i = 0; i < n; i++) {
       result *= x;
     }
   
     return result;
   }
   
   alert( pow(2, 3) ); // 8

2. 遞迴思考：簡化任務並呼叫自己

   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)

1. 如果 `n == 1`，那麼一切都微不足道。它稱為遞迴的基礎，因為它立即產生明顯的結果：`pow(x, 1)` 等於 `x`。
2. 否則，我們可以將 `pow(x, n)` 表示為 `x * pow(x, n - 1)`。在數學中，可以寫成 `x<sup>n</sup> = x * x<sup>n-1</sup>`。這稱為遞迴步驟：我們將任務轉換為一個較簡單的動作（乘以 `x`）和同一個任務的較簡單呼叫（`pow`，其中 `n` 較低）。後續步驟會進一步簡化，直到 `n` 達到 `1`。

我們也可以說 `pow` 遞迴地呼叫它自己，直到 `n == 1`。

例如，要計算 `pow(2, 4)`，遞迴變體會執行以下步驟

1. pow(2, 4) = 2 * pow(2, 3)
2. pow(2, 3) = 2 * pow(2, 2)
3. pow(2, 2) = 2 * pow(2, 1)
4. pow(2, 1) = 2

因此，遞迴會將函式呼叫簡化為一個較簡單的呼叫，然後再簡化為更簡單的呼叫，以此類推，直到結果變得明顯。

function pow(x, n) {
  return (n == 1) ? x : (x * pow(x, n - 1));
}

巢狀呼叫的最大數量（包括第一個呼叫）稱為遞迴深度。在我們的案例中，它將正好等於 `n`。

最大遞迴深度受到 JavaScript 引擎的限制。我們可以依賴它為 10000，有些引擎允許更多，但 100000 可能超過大多數引擎的限制。有一些自動最佳化有助於緩解這個問題（「尾呼叫最佳化」），但它們尚未在所有地方受到支援，而且只適用於簡單的案例。

這限制了遞迴的應用，但它仍然非常廣泛。在許多任務中，遞迴思考方式會產生更簡單的程式碼，更容易維護。

執行環境和堆疊

現在讓我們來探討遞迴呼叫如何運作。為此，我們將深入了解函式的內部運作。

正在執行的函式的執行過程資訊儲存在其執行環境中。

執行環境是一個內部資料結構，其中包含函式執行的詳細資訊：目前控制流程在哪裡、目前的變數、this 的值（我們在此不使用它）和其他一些內部詳細資訊。

一個函式呼叫只有一個與之關聯的執行環境。

當函式執行巢狀呼叫時，會發生以下情況

• 目前的函式暫停。
• 與之關聯的執行環境會記在一個稱為執行環境堆疊的特殊資料結構中。
• 巢狀呼叫執行。
• 執行結束後，舊的執行環境會從堆疊中擷取，而外部函式會從停止的地方繼續執行。

讓我們看看在 pow(2, 3) 呼叫期間會發生什麼事。

pow(2, 3)

在 pow(2, 3) 呼叫開始時，執行環境將儲存變數：x = 2, n = 3，函式的執行流程在第 1 行。

我們可以將其描繪成

• 環境：{ x: 2, n: 3, 在第 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) );

變數相同，但行數變更，因此環境現在是

• 環境：{ x: 2, n: 3, 在第 5 行 } pow(2, 3)

若要計算 x * pow(x, n - 1)，我們需要使用新的參數 pow(2, 2) 執行 pow 的子呼叫。

pow(2, 2)

要進行巢狀呼叫，JavaScript 會將目前的執行內容記在執行內容堆疊中。

這裡我們呼叫同一個函數 pow，但這完全不重要。所有函數的處理程序都相同

1. 目前的內容會「記在」堆疊的最上面。
2. 會為子呼叫建立新的內容。
3. 子呼叫完成時，會將先前的內容從堆疊中彈出，並繼續執行。

當我們進入子呼叫 pow(2, 2) 時，內容堆疊如下

• 內容：{ x: 2, n: 2, at line 1 } pow(2, 2)
• 環境：{ x: 2, n: 3, 在第 5 行 } pow(2, 3)

新的目前執行內容在最上面（以粗體顯示），而先前記住的內容在下面。

當我們完成子呼叫時，很容易恢復先前的內容，因為它會保留變數和程式碼停止執行時的確切位置。

pow(2, 1)

程序會重複：在第 5 行建立新的子呼叫，現在的引數為 x=2、n=1。

建立新的執行內容，將先前的內容推到堆疊的最上面

• 內容：{ x: 2, n: 1, at line 1 } pow(2, 1)
• 內容：{ x: 2, n: 2, at line 5 } pow(2, 2)
• 環境：{ x: 2, n: 3, 在第 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。

當函數完成時，其執行內容不再需要，因此會從記憶體中移除。會將先前的內容從堆疊的最上面還原

• 內容：{ x: 2, n: 2, at line 5 } pow(2, 2)
• 環境：{ x: 2, n: 3, 在第 5 行 } pow(2, 3)

pow(2, 2) 的執行會恢復。它有子呼叫 pow(2, 1) 的結果，因此也可以完成 x * pow(x, n - 1) 的評估，傳回 4。

然後會還原先前的內容

• 環境：{ x: 2, n: 3, 在第 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 個巢狀子迴圈來遍歷單一物件，它會變得相當難看。

讓我們嘗試遞迴。

正如我們所見，當我們的函數取得一個部門進行加總時，有兩種可能的情況

1. 它是一個包含人員陣列的「簡單」部門 - 然後我們可以在一個簡單的迴圈中加總薪資。
2. 或者它是一個包含 N 個子部門的物件 - 然後我們可以進行 N 個遞迴呼叫，以取得每個子部門的加總，並將結果合併。

第 1 種情況是遞迴的基礎，也就是取得陣列時的平凡情況。

第 2 種情況是取得物件時的遞迴步驟。一個複雜的任務會被拆分為較小部門的子任務。它們可能會再次拆分，但遲早會在 (1) 結束拆分。

這個演算法可能從程式碼中讀起來更容易

let company = { // the same object, compressed for brevity
  sales: [{name: 'John', salary: 1000}, {name: 'Alice', salary: 1600 }],
  development: {
    sites: [{name: 'Peter', salary: 2000}, {name: 'Alex', salary: 1800 }],
    internals: [{name: 'Jack', salary: 1300}]
  }
};

// The function to do the job
function sumSalaries(department) {
  if (Array.isArray(department)) { // case (1)
    return department.reduce((prev, current) => prev + current.salary, 0); // sum the array
  } else { // case (2)
    let sum = 0;
    for (let subdep of Object.values(department)) {
      sum += sumSalaries(subdep); // recursively call for subdepartments, sum the results
    }
    return sum;
  }
}

alert(sumSalaries(company)); // 7700

程式碼簡短且容易理解（希望如此？）。這就是遞迴的力量。它也適用於任何層級的子部門巢狀。

以下是呼叫圖

我們可以輕鬆地看到這個原則：對於一個物件 {...} 會進行子呼叫，而陣列 [...] 是遞迴樹的「葉子」，它們會提供立即的結果。

請注意，程式碼使用我們之前介紹過的智慧功能

• 方法 arr.reduce 在章節 陣列方法 中說明，用於取得陣列的加總。
• 迴圈 for(val of Object.values(obj)) 用於迭代物件值：Object.values 會傳回它們的陣列。

遞迴結構

遞迴（遞迴定義）資料結構是一種在部分中複製自身的結構。

我們剛在上面的公司結構範例中看過它。

一個公司的部門是

• 人員陣列。
• 或者包含部門的物件。

對於網頁開發人員來說，有更廣為人知的範例：HTML 和 XML 文件。

在 HTML 文件中，一個HTML 標籤可能包含下列清單

• 文字片段。
• HTML 註解。
• 其他HTML 標籤（它們又可能包含文字片段/註解或其他標籤等）。

這又是一個遞迴定義。

為了更好地理解，我們將介紹另一種名為「連結串列」的遞迴結構，它在某些情況下可能是陣列的更好替代方案。

連結串列

想像一下，我們想要儲存一個已排序的物件清單。

自然而然的選擇會是陣列

let arr = [obj1, obj2, obj3];

…但陣列有一個問題。執行「刪除元素」和「插入元素」的動作成本很高。例如，arr.unshift(obj) 動作必須重新編號所有元素，為新的 obj 騰出空間，如果陣列很大，就會花時間。arr.shift() 也一樣。

唯一不需大量重新編號的結構修改是針對陣列尾端的動作：arr.push/pop。因此，當我們必須處理開頭時，陣列對於大型佇列來說可能會非常慢。

或者，如果我們真的需要快速插入/刪除，我們可以選擇另一種稱為 連結串列 的資料結構。

連結串列元素 遞迴定義為具有下列內容的物件：

• 值.
• next 屬性，參照下一個 連結串列元素 或 null（如果是串列尾端）。

例如

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

串列的圖形表示

建立串列的替代程式碼

let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };
list.next.next.next.next = null;

在這裡，我們可以更清楚地看到有多個物件，每個物件都有 value 和指向鄰居的 next。list 變數是串列中的第一個物件，因此從中追蹤 next 指標，我們可以到達任何元素。

串列可以輕鬆拆分成多個部分，然後再合併回來

let secondList = list.next.next;
list.next.next = null;

合併

list.next.next = secondList;

而且我們當然可以在任何地方插入或移除項目。

例如，要前置一個新值，我們需要更新串列的開頭

let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };

// prepend the new value to the list
list = { value: "new item", next: list };

要從中間移除一個值，請變更前一個值的 next

list.next = list.next.next;

我們讓 list.next 跳過 1 到值 2。值 1 現在已從串列中排除。如果它沒有儲存在其他任何地方，它將自動從記憶體中移除。

與陣列不同，沒有大量重新編號，我們可以輕鬆重新排列元素。

當然，串列並不總是優於陣列。否則，每個人都只會使用串列。

主要的缺點是我們無法輕鬆透過其編號來存取元素。在陣列中很容易：arr[n] 是直接參照。但在串列中，我們需要從第一個項目開始，並執行 next N 次才能取得第 N 個元素。

…但我們並不總是需要此類操作。例如，當我們需要一個佇列，甚至是一個 雙端佇列 時，這種有序結構必須允許從兩端非常快速地新增/移除元素，但不需要存取其中間。

串列可以增強

• 除了 next 之外，我們還可以新增屬性 prev 來參照前一個元素，以便輕鬆後退。
• 我們還可以新增一個名為 tail 的變數，參照串列的最後一個元素（並在從尾端新增/移除元素時更新它）。
• …資料結構可能會根據我們的需求而有所不同。

摘要

術語

• 遞迴是程式設計術語，意指從函數本身呼叫函數。遞迴函數可以用來優雅地解決任務。

  當函數呼叫自身時，稱為遞迴步驟。遞迴的基礎是函數參數，讓任務變得如此簡單，以致函數不會進行進一步的呼叫。

• 遞迴定義的資料結構是可以使用自身來定義的資料結構。

  例如，連結串列可以定義為包含參考串列（或 null）的物件的資料結構。

  list = { value, next -> list }

  像 HTML 元素樹或本章節的部門樹等樹狀結構，本質上也是遞迴的：它們有分支，每個分支都可以有其他分支。

  遞迴函數可用來遍歷它們，就像我們在 sumSalary 範例中看到的。

任何遞迴函數都可以改寫成遞迴函數。有時為了最佳化而需要這麼做。但對於許多任務來說，遞迴解法夠快，而且寫起來和支援都比較容易。