遞歸和堆棧

讓我們回到函數，進行更深入的研究。

我們的第壹個主題是 遞歸（recursion）。

如果妳不是剛接觸編程，那麽妳可能已經很熟悉它了，那麽妳可以跳過這壹章。

遞歸是壹種編程模式，在壹個任務可以自然地拆分成多個相同類型但更簡單的任務的情況下非常有用。或者，在壹個任務可以簡化爲壹個簡單的行爲加上該任務的壹個更簡單的變體的時候可以使用。或者，就像我們很快會看到的那樣，處理某些數據結構。

當壹個函數解決壹個任務時，在解決的過程中它可以調用很多其它函數。在部分情況下，函數會調用 自身。這就是所謂的 遞歸。

兩種思考方式

簡單起見，讓我們寫壹個函數 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;
   
     // 在循環中，用 x 乘以 result n 次
     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. 否則，我們可以用 x * pow(x, n - 1) 表示 pow(x, n)。在數學裏，可能會寫爲 xn = x * xn-1。這叫做 壹個遞歸步驟：我們將任務轉化爲更簡單的行爲（x 的乘法）和更簡單的同類任務的調用（帶有更小的 n 的 pow 運算）。接下來的步驟將其進壹步簡化，直到 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

因此，遞歸將函數調用簡化爲壹個更簡單的函數調用，然後再將其簡化爲壹個更簡單的函數，以此類推，直到結果變得顯而易見。

遞歸通常更短

遞歸解通常比叠代解更短。

在這兒，我們可以使用條件運算符 ? 而不是 if 語句，從而使 pow(x, n) 更簡潔並且可讀性依然很高：

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) 的開始，執行上下文（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，但這絕對沒問題。所有函數的處理都是壹樣的：

1. 當前上下文被“記錄”在堆棧的頂部。

2. 爲子調用創建新的上下文。

3. 當子調用結束後 —— 前壹個上下文被從堆棧中彈出，並繼續執行。

下面是進入子調用 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 級嵌套的子循環來遍曆單個對象， 那代碼得多醜啊。

我們試試遞歸吧。

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

1. 要麽是由壹個人員 數組 構成的“簡單”的部門 —— 這樣我們就可以通過壹個簡單的循環來計算薪資的總和。

2. 或者它是壹個有 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

代碼很短也容易理解（希望是這樣？）。這就是遞歸的能力。它適用于任何層次的子部門嵌套。

下面是調用圖：

我們可以很容易地看到其原理：對于對象 {...} 會生成子調用，而數組 [...] 是遞歸樹的“葉子”，它們會立即給出結果。

請注意，該代碼使用了我們之前講過的智能特性（smart features）：

• 在 數組方法 中我們介紹過的數組求和方法 arr.reduce。

• 使用循環 for(val of Object.values(obj)) 遍曆對象的（屬性）值：Object.values 返回它們組成的數組。

遞歸結構

遞歸（遞歸定義的）數據結構是壹種部分複制自身的結構。

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

壹個公司的 部門 是：

• 人員數組。

• 或壹個 部門 對象。

對于 Web 開發者而言，有更熟知的例子：HTML 和 XML 文檔。

在 HTML 文檔中，壹個 HTML 標簽 可能包括以下內容：

• 文本片段。

• HTML 注釋。

• 其它 HTML 標簽（它有可能又包括文本片段、注釋或其它標簽等）。

這又是壹個遞歸定義。

爲了更好地理解遞歸，我們再講壹個遞歸結構的例子“鏈表”，在某些情況下，它可能是優于數組的選擇。

鏈表

想象壹下，我們要存儲壹個有序的對象列表。

正常的選擇會是壹個數組：

let arr = [obj1, obj2, obj3];

……但是用數組有個問題。“刪除元素”和“插入元素”的操作代價非常大。例如，arr.unshift(obj) 操作必須對所有元素重新編號以便爲新的元素 obj 騰出空間，而且如果數組很大，會很耗時。arr.shift() 同理。

唯壹對數組結構做修改而不需要大量重排的操作就是對數組末端的操作：arr.push/pop。因此，對于大隊列來說，當我們必須對數組首端的元素進行操作時，數組會很慢。（譯注：此處的首端操作其實指的是在尾端以外的數組內的元素進行插入/刪除操作。）

如果我們確實需要快速插入/刪除，則可以選擇另壹種叫做 鏈表 的數據結構。

鏈表元素 是壹個使用以下元素通過遞歸定義的對象：

• value。

• 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 };

// 將新值添加到鏈表頭部
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 元素樹或者本章中的  department 樹等，本質上也是遞歸：它們有分支，而且分支又可以有其他分支。

  就像我們在示例 sumSalary 中看到的那樣，可以使用遞歸函數來遍曆它們。

任何遞歸函數都可以被重寫爲叠代（譯注：也就是循環）形式。有時這是在優化代碼時需要做的。但對于大多數任務來說，遞歸方法足夠快，並且容易編寫和維護。

任務

對數字求和到給定值

重要程度: 5

編寫壹個函數 sumTo(n) 計算 1 + 2 + ... + n 的和。

舉個例子：

sumTo(1) = 1
sumTo(2) = 2 + 1 = 3
sumTo(3) = 3 + 2 + 1 = 6
sumTo(4) = 4 + 3 + 2 + 1 = 10
...
sumTo(100) = 100 + 99 + ... + 2 + 1 = 5050

用三種方式實現：

1. 使用循環。

2. 使用遞歸，對 n > 1 執行 sumTo(n) = n + sumTo(n-1)。

3. 使用 等差數列 求和公式.

結果示例：

function sumTo(n) { /*... 妳的代碼 ... */ }

alert( sumTo(100) ); // 5050

P.S. 哪種解決方式最快？哪種最慢？爲什麽？

P.P.S. 我們可以使用遞歸來計算 sumTo(100000) 嗎？

解決方案

使用循環的解法：

function sumTo(n) {
  let sum = 0;
  for (let i = 1; i <= n; i++) {
    sum += i;
  }
  return sum;
}

alert( sumTo(100) );

使用遞歸的解法：

function sumTo(n) {
  if (n == 1) return 1;
  return n + sumTo(n - 1);
}

alert( sumTo(100) );

使用公式 sumTo(n) = n*(n+1)/2 的解法：

function sumTo(n) {
  return n * (n + 1) / 2;
}

alert( sumTo(100) );

P.S. 當然是公式解法最快。對任何數字 n，只需要進行 3 次運算。數學大法好！

循環的速度次之。在循環和遞歸方法裏，我們對相同的數字求和。但是遞歸涉及嵌套調用和執行堆棧管理。這也會占用資源，因此遞歸的速度更慢壹些。

P.P.S. 壹些引擎支持“尾調用（tail call）”優化：如果遞歸調用是函數中的最後壹個調用（例如上面的 sumTo），那麽外部的函數就不再需要恢複執行，因此引擎也就不再需要記住他的執行上下文。這樣就減輕了內存負擔，因此計算 sumTo(100000) 就變得可能。但是如果妳的 JavaScript 引擎不支持尾調用優化，那就會報錯：超出最大堆棧深度，因爲通常總堆棧的大小是有限制的。

計算階乘

重要程度: 4

自然數的 階乘 是指，壹個數乘以 數字減去 1，然後乘以 數字減去 2，以此類推直到乘以 1。n 的階乘被記作 n!。

我們可以將階乘的定義寫成這樣：

n! = n * (n - 1) * (n - 2) * ...*1

不同 n 的階乘的值：

1! = 1
2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6
4! = 4 * 3 * 2 * 1 = 24
5! = 5 * 4 * 3 * 2 * 1 = 120

任務是編寫壹個函數 factorial(n) 使用遞歸調用計算 n!。

alert( factorial(5) ); // 120

P.S. 提示：n! 可以被寫成 n * (n-1)!，比如 3! = 3*2! = 3*2*1! = 6。

解決方案

根據定義，階乘 n! 可以被寫成 n * (n-1)!。

換句話說，factorial(n) 的結果可以用 n 乘以 factorial(n-1) 的結果來獲得。對 n-1 的調用同理可以依次地遞減，直到 1。

function factorial(n) {
  return (n != 1) ? n * factorial(n - 1) : 1;
}

alert( factorial(5) ); // 120

遞歸的基礎是數值 1。我們也可以用 0 作爲基礎，不影響，除了會多壹次遞歸步驟：

function factorial(n) {
  return n ? n * factorial(n - 1) : 1;
}

alert( factorial(5) ); // 120

斐波那契數

重要程度: 5

斐波那契數 序列有這樣的公式： Fn = Fn-1 + Fn-2。換句話說，下壹個數字是前兩個數字的和。

前兩個數字是 1，然後是 2(1+1)，然後 3(1+2)，5(2+3) 等：1, 1, 2, 3, 5, 8, 13, 21...。

斐波那契數與 黃金比例 以及我們周圍的許多自然現象有關。

編寫壹個函數 fib(n) 返回第 n 個斐波那契數。

工作示例：

function fib(n) { /* 妳的代碼 */ }

alert(fib(3)); // 2
alert(fib(7)); // 13
alert(fib(77)); // 5527939700884757

P.S. 函數運行速度要快，對 fib(77) 的調用不應該超過幾分之壹秒。

解決方案

我們可以嘗試的第壹種解法是遞歸。

斐波那契數根據定義是遞歸的：

function fib(n) {
  return n <= 1 ? n : fib(n - 1) + fib(n - 2);
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
// fib(77); // 超級慢！

……但是 n 比較大時會很慢。比如 fib(77) 會挂起引擎壹段時間，並且消耗所有 CPU 資源。

因爲函數産生了太多的子調用。同樣的值被壹遍又壹遍地計算。

例如，我們看下計算 fib(5) 的片段：

...
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
...

可以看到，fib(5) 和 fib(4) 都需要 fib(3) 的值，所以 fib(3) 被獨立計算了兩次。

這是完整的遞歸樹：

我們可以清楚的看到 fib(3) 被計算了兩次，fib(2) 被計算了三次。總計算量遠遠超過了 n，這造成僅僅對于計算 n=77 來講，計算量就是巨量的。

我們可以通過記錄已經計算過的值來進行優化：如果壹個值比如 fib(3) 已經被計算過壹次，那麽我們可以在後面的計算中重複使用它。

另壹個選擇就是不使用遞歸，而是使用完全不同的基于循環的算法。

與從 n 到降到更小的值相反，我們可以使用循環從 1 和 2 開始，然後得到它們的和 fib(3)，然後再通過前兩個數的和得到 fib(4)，然後 fib(5)，以此類推，直至達到所需要的值。在每壹步，我們只需要記錄前兩個值就可以。

下面是新算法的細節步驟：

開始：

// a = fib(1), b = fib(2)，這些值是根據定義 1 得到的
let a = 1, b = 1;

// 求兩者的和得到 c = fib(3)
let c = a + b;

/* 現在我們有 fib(1)，fib(2) 和 fib(3)
a  b  c
1, 1, 2
*/

現在我們想要得到 fib(4) = fib(2) + fib(3)。

我們移動變量：a,b 將得到 fib(2),fib(3)，c 將得到兩者的和：

a = b; // 現在 a = fib(2)
b = c; // 現在 b = fib(3)
c = a + b; // c = fib(4)

/* 現在我們有這樣的序列
   a  b  c
1, 1, 2, 3
*/

下壹步得到另壹個序列數：

a = b; // 現在 a = fib(3)
b = c; // 現在 b = fib(4)
c = a + b; // c = fib(5)

/* 現在序列是（又加了壹個數）：
      a  b  c
1, 1, 2, 3, 5
*/

……依次類推，直到我們得到需要的值。這比遞歸快很多，而且沒有重複計算。

完整代碼：

function fib(n) {
  let a = 1;
  let b = 1;
  for (let i = 3; i <= n; i++) {
    let c = a + b;
    a = b;
    b = c;
  }
  return b;
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
alert( fib(77) ); // 5527939700884757

循環從 i=3 開始，因爲前兩個序列值被硬編碼到變量 a=1，b=1。

這種方式稱爲 自下而上的動態規劃。

輸出壹個單鏈表

重要程度: 5

假設我們有壹個單鏈表（在 遞歸和堆棧 那章有講過）：

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

編寫壹個可以逐個輸出鏈表元素的函數 printList(list)。

使用兩種方式實現：循環和遞歸。

哪個更好：用遞歸還是不用遞歸的？

解決方案

循環解法

循環解法

基于循環的解法：

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

function printList(list) {
  let tmp = list;

  while (tmp) {
    alert(tmp.value);
    tmp = tmp.next;
  }

}

printList(list);

請注意，我們使用了壹個臨時變量 tmp 來遍曆鏈表。從技術上講，我們可以使用函數的入參 list 來代替：

function printList(list) {

  while(list) {
    alert(list.value);
    list = list.next;
  }

}

……但是這不夠明智。未來我們可能想要擴展這個函數，使用這個鏈表做其他的事兒，如果我們修改了 list，那麽我們就失去了這個能力。

說到好的變量命名，list 在這裏是鏈表本身。代表它的第壹個元素。它應該保持原樣，這是清晰可靠的。

從另壹個方面來說，tmp 是充當了完全遍曆鏈表的角色，就像 for 循環中的 i 壹樣。

遞歸解法

遞歸解法

printList(list) 的遞歸實現遵循壹個簡單的邏輯：爲了輸出鏈表，我們應該輸出 list 的當前的元素，list.next 同理：

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

function printList(list) {

  alert(list.value); // 輸出當前元素

  if (list.next) {
    printList(list.next); // 鏈表中其余部分同理
  }

}

printList(list);

哪個更好呢？

從技術上講，循環更有效。這兩種解法的做了同樣的事兒，但循環不會爲嵌套函數調用消耗資源。

另壹方面，遞歸解法更簡潔，有時更容易理解。

反向輸出單鏈表

重要程度: 5

反向輸出前壹個任務 輸出壹個單鏈表 中的單鏈表。

使用兩種解法：循環和遞歸。

解決方案

使用遞歸

使用遞歸

遞歸邏輯在這稍微有點兒棘手。

我們需要先輸出列表的其它元素，然後 輸出當前的元素：

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

function printReverseList(list) {

  if (list.next) {
    printReverseList(list.next);
  }

  alert(list.value);
}

printReverseList(list);

使用循環

使用循環

循環解法也比直接輸出稍微複雜了點兒。

在這而沒有什麽方法可以獲取 list 中的最後壹個值。我們也不能“從後向前”讀取。

因此，我們可以做的就是直接按順序遍曆每個元素，並把它們存到壹個數組中，然後反向輸出我們存儲在數組中的元素：

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

function printReverseList(list) {
  let arr = [];
  let tmp = list;

  while (tmp) {
    arr.push(tmp.value);
    tmp = tmp.next;
  }

  for (let i = arr.length - 1; i >= 0; i--) {
    alert( arr[i] );
  }
}

printReverseList(list);

請注意，遞歸解法實際上也是這樣做的：它順著鏈表，記錄每壹個嵌套調用裏鏈表的元素（在執行上下文堆棧裏），然後輸出它們。