Javascript 遞歸和堆棧

讓我們回到函數(shù)，進(jìn)行更深入的研究。

我們的第一個(gè)主題是 遞歸（recursion）。

如果你不是剛接觸編程，那么你可能已經(jīng)很熟悉它了，那么你可以跳過(guò)這一章。

遞歸是一種編程模式，在一個(gè)任務(wù)可以自然地拆分成多個(gè)相同類型但更簡(jiǎn)單的任務(wù)的情況下非常有用?；蛘撸谝粋€(gè)任務(wù)可以簡(jiǎn)化為一個(gè)簡(jiǎn)單的行為加上該任務(wù)的一個(gè)更簡(jiǎn)單的變體的時(shí)候可以使用。或者，就像我們很快會(huì)看到的那樣，處理某些數(shù)據(jù)結(jié)構(gòu)。

當(dāng)一個(gè)函數(shù)解決一個(gè)任務(wù)時(shí)，在解決的過(guò)程中它可以調(diào)用很多其它函數(shù)。在部分情況下，函數(shù)會(huì)調(diào)用 自身。這就是所謂的 遞歸。

兩種思考方式

簡(jiǎn)單起見(jiàn)，讓我們寫(xiě)一個(gè)函數(shù) pow(x, n)，它可以計(jì)算 x 的 n 次方。換句話說(shuō)就是，x 乘以自身 n 次。

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

有兩種實(shí)現(xiàn)方式。

1. 迭代思路：使用 for 循環(huán)：

function pow(x, n) {
  let result = 1;

  // 再循環(huán)中，用 x 乘以 result n 次
  for (let i = 0; i < n; i++) {
    result *= x;
  }

  return result;
}

alert( pow(2, 3) ); // 8

2. 遞歸思路：簡(jiǎn)化任務(wù)，調(diào)用自身：

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

alert( pow(2, 3) ); // 8

請(qǐng)注意，遞歸變體在本質(zhì)上是不同的。

當(dāng) ?pow(x, n)? 被調(diào)用時(shí)，執(zhí)行分為兩個(gè)分支：

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

1. 如果 ?n == 1?，所有事情都會(huì)很簡(jiǎn)單，這叫做 基礎(chǔ) 的遞歸，因?yàn)樗鼤?huì)立即產(chǎn)生明顯的結(jié)果：?pow(x, 1)? 等于 ?x?。
2. 否則，我們可以用 ?x * pow(x, n - 1)? 表示 ?pow(x, n)?。在數(shù)學(xué)里，可能會(huì)寫(xiě)為 ?xn = x * xn-1?。這叫做 一個(gè)遞歸步驟：我們將任務(wù)轉(zhuǎn)化為更簡(jiǎn)單的行為（x 的乘法）和更簡(jiǎn)單的同類任務(wù)的調(diào)用（帶有更小的 n 的 ?pow? 運(yùn)算）。接下來(lái)的步驟將其進(jìn)一步簡(jiǎn)化，直到 ?n? 達(dá)到 ?1?。

我們也可以說(shuō) pow 遞歸地調(diào)用自身 直到 n == 1。

比如，為了計(jì)算 pow(2, 4)，遞歸變體經(jīng)過(guò)了下面幾個(gè)步驟：

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?

因此，遞歸將函數(shù)調(diào)用簡(jiǎn)化為一個(gè)更簡(jiǎn)單的函數(shù)調(diào)用，然后再將其簡(jiǎn)化為一個(gè)更簡(jiǎn)單的函數(shù)，以此類推，直到結(jié)果變得顯而易見(jiàn)。

遞歸通常更短

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

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

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

最大的嵌套調(diào)用次數(shù)（包括首次）被稱為 遞歸深度。在我們的例子中，它正好等于 n。

最大遞歸深度受限于 JavaScript 引擎。對(duì)我們來(lái)說(shuō)，引擎在最大迭代深度為 10000 及以下時(shí)是可靠的，有些引擎可能允許更大的最大深度，但是對(duì)于大多數(shù)引擎來(lái)說(shuō)，100000 可能就超出限制了。有一些自動(dòng)優(yōu)化能夠幫助減輕這種情況（尾部調(diào)用優(yōu)化），但目前它們還沒(méi)有被完全支持，只能用于簡(jiǎn)單場(chǎng)景。

這就限制了遞歸的應(yīng)用，但是遞歸仍然被廣泛使用。有很多任務(wù)中，遞歸思維方式會(huì)使代碼更簡(jiǎn)單，更容易維護(hù)。

執(zhí)行上下文和堆棧

現(xiàn)在我們來(lái)研究一下遞歸調(diào)用是如何工作的。為此，我們會(huì)先看看函數(shù)底層的工作原理。

有關(guān)正在運(yùn)行的函數(shù)的執(zhí)行過(guò)程的相關(guān)信息被存儲(chǔ)在其 執(zhí)行上下文 中。

執(zhí)行上下文 是一個(gè)內(nèi)部數(shù)據(jù)結(jié)構(gòu)，它包含有關(guān)函數(shù)執(zhí)行時(shí)的詳細(xì)細(xì)節(jié)：當(dāng)前控制流所在的位置，當(dāng)前的變量，this 的值（此處我們不使用它），以及其它的一些內(nèi)部細(xì)節(jié)。

一個(gè)函數(shù)調(diào)用僅具有一個(gè)與其相關(guān)聯(lián)的執(zhí)行上下文。

當(dāng)一個(gè)函數(shù)進(jìn)行嵌套調(diào)用時(shí)，將發(fā)生以下的事兒：

• 當(dāng)前函數(shù)被暫停；
• 與它關(guān)聯(lián)的執(zhí)行上下文被一個(gè)叫做 執(zhí)行上下文堆棧 的特殊數(shù)據(jù)結(jié)構(gòu)保存；
• 執(zhí)行嵌套調(diào)用；
• 嵌套調(diào)用結(jié)束后，從堆棧中恢復(fù)之前的執(zhí)行上下文，并從停止的位置恢復(fù)外部函數(shù)。

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

pow(2, 3)

在調(diào)用 pow(2, 3) 的開(kāi)始，執(zhí)行上下文（context）會(huì)存儲(chǔ)變量：x = 2, n = 3，執(zhí)行流程在函數(shù)的第 1 行。

我們將其描繪如下：

這是函數(shù)開(kāi)始執(zhí)行的時(shí)候。條件 n == 1 結(jié)果為假，所以執(zhí)行流程進(jìn)入 if 的第二分支。

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

alert( pow(2, 3) );

變量相同，但是行改變了，因此現(xiàn)在的上下文是：

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

pow（2, 2)

為了執(zhí)行嵌套調(diào)用，JavaScript 會(huì)在 執(zhí)行上下文堆棧 中記住當(dāng)前的執(zhí)行上下文。

這里我們調(diào)用相同的函數(shù) pow，但這絕對(duì)沒(méi)問(wèn)題。所有函數(shù)的處理都是一樣的：

1. 當(dāng)前上下文被“記錄”在堆棧的頂部。
2. 為子調(diào)用創(chuàng)建新的上下文。
3. 當(dāng)子調(diào)用結(jié)束后 —— 前一個(gè)上下文被從堆棧中彈出，并繼續(xù)執(zhí)行。

下面是進(jìn)入子調(diào)用 pow(2, 2) 時(shí)的上下文堆棧：

新的當(dāng)前執(zhí)行上下文位于頂部（粗體顯示），之前記住的上下文位于下方。

當(dāng)我們完成子調(diào)用后 —— 很容易恢復(fù)上一個(gè)上下文，因?yàn)樗缺Ａ袅俗兞?，也保留了?dāng)時(shí)所在代碼的確切位置。

請(qǐng)注意：

在上面的圖中，我們使用“行（line）”一詞，因?yàn)樵谖覀兊氖纠?，每一行只有一個(gè)子調(diào)用，但通常一行代碼可能會(huì)包含多個(gè)子調(diào)用，例如 pow(…) + pow(…) + somethingElse(…)。

因此，更準(zhǔn)確地說(shuō)，執(zhí)行是“在子調(diào)用之后立即恢復(fù)”的。

pow(2, 1)

重復(fù)該過(guò)程：在第 5 行生成新的子調(diào)用，現(xiàn)在的參數(shù)是 x=2, n=1。

新的執(zhí)行上下文被創(chuàng)建，前一個(gè)被壓入堆棧頂部：

此時(shí)，有 2 個(gè)舊的上下文和 1 個(gè)當(dāng)前正在運(yùn)行的 pow(2, 1) 的上下文。

出口

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

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

此時(shí)不再有更多的嵌套調(diào)用，所以函數(shù)結(jié)束，返回 2。

函數(shù)完成后，就不再需要其執(zhí)行上下文了，因此它被從內(nèi)存中移除。前一個(gè)上下文恢復(fù)到堆棧的頂部：

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

然后，前一個(gè)上下文被恢復(fù)：

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

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

從上面的插圖我們可以看出，遞歸深度等于堆棧中上下文的最大數(shù)量。

請(qǐng)注意內(nèi)存要求。上下文占用內(nèi)存，在我們的示例中，求 n 次方需要存儲(chǔ) n 個(gè)上下文，以供更小的 n 值進(jìn)行計(jì)算使用。

而循環(huán)算法更節(jié)省內(nèi)存：

function pow(x, n) {
  let result = 1;

  for (let i = 0; i < n; i++) {
    result *= x;
  }

  return result;
}

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

任何遞歸都可以用循環(huán)來(lái)重寫(xiě)。通常循環(huán)變體更有效。

……但有時(shí)重寫(xiě)很難，尤其是函數(shù)根據(jù)條件使用不同的子調(diào)用，然后合并它們的結(jié)果，或者分支比較復(fù)雜時(shí)。而且有些優(yōu)化可能沒(méi)有必要，完全不值得。

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

遞歸遍歷

遞歸的另一個(gè)重要應(yīng)用就是遞歸遍歷。

假設(shè)我們有一家公司。人員結(jié)構(gòu)可以表示為一個(gè)對(duì)象：

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

換句話說(shuō)，一家公司有很多部門(mén)。

• 一個(gè)部門(mén)可能有一 數(shù)組 的員工，比如，?sales? 部門(mén)有 2 名員工：John 和 Alice。
• 或者，一個(gè)部門(mén)可能會(huì)劃分為幾個(gè)子部門(mén)，比如 ?development? 有兩個(gè)分支：?sites? 和 ?internals?，它們都有自己的員工。
• 當(dāng)一個(gè)子部門(mén)增長(zhǎng)時(shí)，它也有可能被拆分成幾個(gè)子部門(mén)（或團(tuán)隊(duì)）。
例如，?sites? 部門(mén)在未來(lái)可能會(huì)分為 ?siteA? 和 ?siteB?。并且，它們可能會(huì)被再繼續(xù)拆分。沒(méi)有圖示，腦補(bǔ)一下吧。

現(xiàn)在，如果我們需要一個(gè)函數(shù)來(lái)獲取所有薪資的總數(shù)。我們?cè)撛趺醋觯?

迭代方式并不容易，因?yàn)榻Y(jié)構(gòu)比較復(fù)雜。首先想到的可能是在 company 上使用 for 循環(huán)，并在第一層部分上嵌套子循環(huán)。但是，之后我們需要更多的子循環(huán)來(lái)遍歷像 sites 這樣的二級(jí)部門(mén)的員工…… 然后，將來(lái)可能會(huì)出現(xiàn)在三級(jí)部門(mén)上的另一個(gè)子循環(huán)？如果我們?cè)诖a中寫(xiě) 3-4 級(jí)嵌套的子循環(huán)來(lái)遍歷單個(gè)對(duì)象， 那代碼得多丑啊。

我們?cè)囋囘f歸吧。

我們可以看到，當(dāng)我們的函數(shù)對(duì)一個(gè)部門(mén)求和時(shí)，有兩種可能的情況：

1. 要么是由一 數(shù)組 的人組成的“簡(jiǎn)單”的部門(mén) —— 這樣我們就可以通過(guò)一個(gè)簡(jiǎn)單的循環(huán)來(lái)計(jì)算薪資的總和。
2. 或者它是一個(gè)有 ?N? 個(gè)子部門(mén)的 對(duì)象 —— 那么我們可以通過(guò) ?N? 層遞歸調(diào)用來(lái)求每一個(gè)子部門(mén)的薪資，然后將它們合并起來(lái)。

第一種情況是由一數(shù)組的人組成的部門(mén)，這種情況很簡(jiǎn)單，是最基礎(chǔ)的遞歸。

第二種情況是我們得到的是對(duì)象。那么可將這個(gè)復(fù)雜的任務(wù)拆分成適用于更小部門(mén)的子任務(wù)。它們可能會(huì)被繼續(xù)拆分，但很快或者不久就會(huì)拆分到第一種情況那樣。

這個(gè)算法從代碼來(lái)看可能會(huì)更簡(jiǎn)單：

let company = { // 是同一個(gè)對(duì)象，簡(jiǎn)潔起見(jiàn)被壓縮了
  sales: [{name: 'John', salary: 1000}, {name: 'Alice', salary: 1600 }],
  development: {
    sites: [{name: 'Peter', salary: 2000}, {name: 'Alex', salary: 1800 }],
    internals: [{name: 'Jack', salary: 1300}]
  }
};

// 用來(lái)完成任務(wù)的函數(shù)
function sumSalaries(department) {
  if (Array.isArray(department)) { // 情況（1）
    return department.reduce((prev, current) => prev + current.salary, 0); // 求數(shù)組的和
  } else { // 情況（2）
    let sum = 0;
    for (let subdep of Object.values(department)) {
      sum += sumSalaries(subdep); // 遞歸調(diào)用所有子部門(mén)，對(duì)結(jié)果求和
    }
    return sum;
  }
}

alert(sumSalaries(company)); // 7700

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

下面是調(diào)用圖：

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

請(qǐng)注意，該代碼使用了我們之前講過(guò)的智能特性（smart features）：

• 在 數(shù)組方法 中我們介紹過(guò)的數(shù)組求和方法 ?arr.reduce?。
• 使用循環(huán) ?for(val of Object.values(obj))? 遍歷對(duì)象的（屬性）值：?Object.values? 返回它們組成的數(shù)組。

遞歸結(jié)構(gòu)

遞歸（遞歸定義的）數(shù)據(jù)結(jié)構(gòu)是一種部分復(fù)制自身的結(jié)構(gòu)。

我們剛剛在上面的公司結(jié)構(gòu)的示例中看過(guò)了它。

一個(gè)公司的 部門(mén) 是：

• 一數(shù)組的人。
• 或一個(gè) 部門(mén) 對(duì)象。

對(duì)于 Web 開(kāi)發(fā)者而言，有更熟知的例子：HTML 和 XML 文檔。

在 HTML 文檔中，一個(gè) HTML 標(biāo)簽 可能包括以下內(nèi)容：

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

這又是一個(gè)遞歸定義。

為了更好地理解遞歸，我們?cè)僦v一個(gè)遞歸結(jié)構(gòu)的例子“鏈表”，在某些情況下，它可能是優(yōu)于數(shù)組的選擇。

鏈表

想象一下，我們要存儲(chǔ)一個(gè)有序的對(duì)象列表。

正常的選擇會(huì)是一個(gè)數(shù)組：

let arr = [obj1, obj2, obj3];

……但是用數(shù)組有個(gè)問(wèn)題?！皠h除元素”和“插入元素”的操作代價(jià)非常大。例如，arr.unshift(obj) 操作必須對(duì)所有元素重新編號(hào)以便為新的元素 obj 騰出空間，而且如果數(shù)組很大，會(huì)很耗時(shí)。arr.shift() 同理。

唯一對(duì)數(shù)組結(jié)構(gòu)做修改而不需要大量重排的操作就是對(duì)數(shù)組末端的操作：arr.push/pop。因此，對(duì)于大隊(duì)列來(lái)說(shuō)，當(dāng)我們必須對(duì)數(shù)組首端的元素進(jìn)行操作時(shí)，數(shù)組會(huì)很慢。（譯注：此處的首端操作其實(shí)指的是在尾端以外的數(shù)組內(nèi)的元素進(jìn)行插入/刪除操作。）

如果我們確實(shí)需要快速插入/刪除，則可以選擇另一種叫做 鏈表 的數(shù)據(jù)結(jié)構(gòu)。

鏈表元素 是一個(gè)使用以下元素通過(guò)遞歸定義的對(duì)象：

• ?value?。
• ?next? 屬性引用下一個(gè) 鏈表元素 或者代表末尾的 ?null?。

例如：

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

鏈表的圖形表示：

一段用來(lái)創(chuàng)建鏈表的代碼：

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;

在這兒我們可以清楚地看到，這里有很多個(gè)對(duì)象，每一個(gè)都有 value 和指向鄰居的 next。變量 list 是鏈條中的第一個(gè)對(duì)象，因此順著 next 指針，我們可以抵達(dá)任何元素。

該鏈表可以很容易被拆分為多個(gè)部分，然后再重新組裝回去：

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

合并：

list.next.next = secondList;

當(dāng)然，我們可以在任何位置插入或移除元素。

比如，要添加一個(gè)新值，我們需要更新鏈表的頭：

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

要從中間刪除一個(gè)值，可以修改前一個(gè)元素的 next：

list.next = list.next.next;

我們讓 list.next 從 1 跳到值 2。現(xiàn)在值 1 就被從鏈表中移除了。如果它沒(méi)有被存儲(chǔ)在其它任何地方，那么它會(huì)被自動(dòng)從內(nèi)存中刪除。

與數(shù)組不同，鏈表沒(méi)有大規(guī)模重排，我們可以很容易地重新排列元素。

當(dāng)然，鏈表也不總是優(yōu)于數(shù)組的。不然大家就都去使用鏈表了。

鏈表主要的缺點(diǎn)就是我們無(wú)法很容易地通過(guò)元素的編號(hào)獲取元素。但在數(shù)組中卻很容易：arr[n] 是一個(gè)直接引用。而在鏈表中，我們需要從起點(diǎn)元素開(kāi)始，順著 next 找 N 次才能獲取到第 N 個(gè)元素。

……但是我們也并不是總需要這樣的操作。比如，當(dāng)我們需要一個(gè)隊(duì)列甚至一個(gè) 雙向隊(duì)列 —— 有序結(jié)構(gòu)必須可以快速地從兩端添加/移除元素，但是不需要訪問(wèn)的元素。

鏈表可以得到增強(qiáng)：

• 我們可以在 ?next? 之外，再添加 ?prev? 屬性來(lái)引用前一個(gè)元素，以便輕松地往回移動(dòng)。
• 我們還可以添加一個(gè)名為 ?tail? 的變量，該變量引用鏈表的最后一個(gè)元素（并在從末尾添加/刪除元素時(shí)對(duì)該引用進(jìn)行更新）。
• ……數(shù)據(jù)結(jié)構(gòu)可能會(huì)根據(jù)我們的需求而變化。

總結(jié)

術(shù)語(yǔ)：

• 遞歸 是編程的一個(gè)術(shù)語(yǔ)，表示從自身調(diào)用函數(shù)（譯注：也就是自調(diào)用）。遞歸函數(shù)可用于以更優(yōu)雅的方式解決問(wèn)題。

當(dāng)一個(gè)函數(shù)調(diào)用自身時(shí)，我們稱其為 遞歸步驟。遞歸的 基礎(chǔ) 是函數(shù)參數(shù)使任務(wù)簡(jiǎn)單到該函數(shù)不再需要進(jìn)行進(jìn)一步調(diào)用。

• 遞歸定義 的數(shù)據(jù)結(jié)構(gòu)是指可以使用自身來(lái)定義的數(shù)據(jù)結(jié)構(gòu)。

例如，鏈表可以被定義為由對(duì)象引用一個(gè)列表（或 null）而組成的數(shù)據(jù)結(jié)構(gòu)。


list = { value, next -> list }

像 HTML 元素樹(shù)或者本章中的 department 樹(shù)等，本質(zhì)上也是遞歸：它們有分支，而且分支又可以有其他分支。


就像我們?cè)谑纠?nbsp;sumSalary 中看到的那樣，可以使用遞歸函數(shù)來(lái)遍歷它們。

任何遞歸函數(shù)都可以被重寫(xiě)為迭代（譯注：也就是循環(huán)）形式。有時(shí)這是在優(yōu)化代碼時(shí)需要做的。但對(duì)于大多數(shù)任務(wù)來(lái)說(shuō)，遞歸方法足夠快，并且容易編寫(xiě)和維護(hù)。

任務(wù)

---

對(duì)數(shù)字求和到給定值

重要程度: 5

編寫(xiě)一個(gè)函數(shù) sumTo(n) 計(jì)算 1 + 2 + ... + n 的和。

舉個(gè)例子：

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

用三種方式實(shí)現(xiàn)：

1. 使用循環(huán)。
2. 使用遞歸，對(duì) ?n > 1? 執(zhí)行 ?sumTo(n) = n + sumTo(n-1)?。
3. 使用 等差數(shù)列 求和公式.

結(jié)果示例：

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

alert( sumTo(100) ); // 5050

P.S. 哪種解決方式最快？哪種最慢？為什么？

P.P.S. 我們可以使用遞歸來(lái)計(jì)算 ?sumTo(100000)? 嗎？

---

解決方案

使用循環(huán)的解法：

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. 當(dāng)然是公式解法最快。對(duì)任何數(shù)字 n，只需要進(jìn)行 3 次運(yùn)算。數(shù)學(xué)大法好！

循環(huán)的速度次之。在循環(huán)和遞歸方法里，我們對(duì)相同的數(shù)字求和。但是遞歸涉及嵌套調(diào)用和執(zhí)行堆棧管理。這也會(huì)占用資源，因此遞歸的速度更慢一些。

P.P.S. 一些引擎支持“尾調(diào)用（tail call）”優(yōu)化：如果遞歸調(diào)用是函數(shù)中的最后一個(gè)調(diào)用（例如上面的 sumTo），那么外部的函數(shù)就不再需要恢復(fù)執(zhí)行，因此引擎也就不再需要記住他的執(zhí)行上下文。這樣就減輕了內(nèi)存負(fù)擔(dān)，因此計(jì)算 sumTo(100000) 就變得可能。但是如果你的 JavaScript 引擎不支持尾調(diào)用優(yōu)化，那就會(huì)報(bào)錯(cuò)：超出最大堆棧深度，因?yàn)橥ǔ？偠褩５拇笮∈怯邢拗频摹?

---

計(jì)算階乘

重要程度: 4

自然數(shù)的 階乘 是指，一個(gè)數(shù)乘以 數(shù)字減去 1，然后乘以 數(shù)字減去 2，以此類推直到乘以 1。n 的階乘被記作 n!。

我們可以將階乘的定義寫(xiě)成這樣：

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

任務(wù)是編寫(xiě)一個(gè)函數(shù) factorial(n) 使用遞歸調(diào)用計(jì)算 n!。

alert( factorial(5) ); // 120

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

---

解決方案

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

換句話說(shuō)，factorial(n) 的結(jié)果可以用 n 乘以 factorial(n-1) 的結(jié)果來(lái)獲得。對(duì) n-1 的調(diào)用同理可以依次地遞減，直到 1。

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

alert( factorial(5) ); // 120

遞歸的基礎(chǔ)是數(shù)值 1。我們也可以用 0 作為基礎(chǔ)，不影響，除了會(huì)多一次遞歸步驟：

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

alert( factorial(5) ); // 120

---

斐波那契數(shù)

重要程度: 5

斐波那契數(shù) 序列有這樣的公式： Fn = Fn-1 + Fn-2。換句話說(shuō)，下一個(gè)數(shù)字是前兩個(gè)數(shù)字的和。

前兩個(gè)數(shù)字是 1，然后是 2(1+1)，然后 3(1+2)，5(2+3) 等：1, 1, 2, 3, 5, 8, 13, 21...。

斐波那契數(shù)與 黃金比例 以及我們周?chē)脑S多自然現(xiàn)象有關(guān)。

編寫(xiě)一個(gè)函數(shù) fib(n) 返回第 n 個(gè)斐波那契數(shù)。

工作示例：

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

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

P.S. 函數(shù)運(yùn)行速度要快，對(duì) fib(77) 的調(diào)用不應(yīng)該超過(guò)幾分之一秒。

---

解決方案

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

斐波那契數(shù)根據(jù)定義是遞歸的：

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

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

……但是 n 比較大時(shí)會(huì)很慢。比如 fib(77) 會(huì)掛起引擎一段時(shí)間，并且消耗所有 CPU 資源。

因?yàn)楹瘮?shù)產(chǎn)生了太多的子調(diào)用。同樣的值被一遍又一遍地計(jì)算。

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

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

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

這是完整的遞歸樹(shù)：

我們可以清楚的看到 fib(3) 被計(jì)算了兩次，fib(2) 被計(jì)算了三次?？傆?jì)算量遠(yuǎn)遠(yuǎn)超過(guò)了 n，這造成僅僅對(duì)于計(jì)算 n=77 來(lái)講，計(jì)算量就是巨量的。

我們可以通過(guò)記錄已經(jīng)計(jì)算過(guò)的值來(lái)進(jìn)行優(yōu)化：如果一個(gè)值比如 fib(3) 已經(jīng)被計(jì)算過(guò)一次，那么我們可以在后面的計(jì)算中重復(fù)使用它。

另一個(gè)選擇就是不使用遞歸，而是使用完全不同的基于循環(huán)的算法。

與從 n 到降到更小的值相反，我們可以使用循環(huán)從 1 和 2 開(kāi)始，然后得到它們的和 fib(3)，然后再通過(guò)前兩個(gè)數(shù)的和得到 fib(4)，然后 fib(5)，以此類推，直至達(dá)到所需要的值。在每一步，我們只需要記錄前兩個(gè)值就可以。

下面是新算法的細(xì)節(jié)步驟：

開(kāi)始：

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

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

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

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

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

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

/* 現(xiàn)在我們有這樣的序列
   a  b  c
1, 1, 2, 3
*/

下一步得到另一個(gè)序列數(shù)：

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

/* 現(xiàn)在序列是（又加了一個(gè)數(shù)）：
      a  b  c
1, 1, 2, 3, 5
*/

……依次類推，直到我們得到需要的值。這比遞歸快很多，而且沒(méi)有重復(fù)計(jì)算。

完整代碼：

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

循環(huán)從 i=3 開(kāi)始，因?yàn)榍皟蓚€(gè)序列值被硬編碼到變量 a=1，b=1。

這種方式稱為 自下而上的動(dòng)態(tài)規(guī)劃。

---

輸出一個(gè)單鏈表

重要程度: 5

假設(shè)我們有一個(gè)單鏈表（在 遞歸和堆棧 那章有講過(guò)）：

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

編寫(xiě)一個(gè)可以逐個(gè)輸出鏈表元素的函數(shù) printList(list)。

使用兩種方式實(shí)現(xiàn)：循環(huán)和遞歸。

哪個(gè)更好：用遞歸還是不用遞歸的？

---

解決方法

循環(huán)解法

基于循環(huán)的解法：

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

請(qǐng)注意，我們使用了一個(gè)臨時(shí)變量 tmp 來(lái)遍歷鏈表。從技術(shù)上講，我們可以使用函數(shù)的入?yún)?nbsp;list 來(lái)代替：

function printList(list) {

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

}

……但是這不夠明智。未來(lái)我們可能想要擴(kuò)展這個(gè)函數(shù)，使用這個(gè)鏈表做其他的事兒，如果我們修改了 list，那么我們就失去了這個(gè)能力。

說(shuō)到好的變量命名，list 在這里是鏈表本身。代表它的第一個(gè)元素。它應(yīng)該保持原樣，這是清晰可靠的。

從另一個(gè)方面來(lái)說(shuō)，tmp 是充當(dāng)了完全遍歷鏈表的角色，就像 for 循環(huán)中的 i 一樣。

遞歸解法

printList(list) 的遞歸實(shí)現(xiàn)遵循一個(gè)簡(jiǎn)單的邏輯：為了輸出鏈表，我們應(yīng)該輸出 list 的當(dāng)前的元素，list.next 同理：

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

function printList(list) {

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

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

}

printList(list);

哪個(gè)更好呢？

從技術(shù)上講，循環(huán)更有效。這兩種解法的做了同樣的事兒，但循環(huán)不會(huì)為嵌套函數(shù)調(diào)用消耗資源。

另一方面，遞歸解法更簡(jiǎn)潔，有時(shí)更容易理解。

---

反向輸出單鏈表

重要程度: 5

反向輸出前一個(gè)任務(wù) 輸出一個(gè)單鏈表 中的單鏈表。

使用兩種解法：循環(huán)和遞歸。

---

解決方案

使用遞歸

遞歸邏輯在這稍微有點(diǎn)兒棘手。

我們需要先輸出列表的其它元素，然后 輸出當(dāng)前的元素：

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

使用循環(huán)

循環(huán)解法也比直接輸出稍微復(fù)雜了點(diǎn)兒。

在這而沒(méi)有什么方法可以獲取 ?list? 中的最后一個(gè)值。我們也不能“從后向前”讀取。

因此，我們可以做的就是直接按順序遍歷每個(gè)元素，并把它們存到一個(gè)數(shù)組中，然后反向輸出我們存儲(chǔ)在數(shù)組中的元素：

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

請(qǐng)注意，遞歸解法實(shí)際上也是這樣做的：它順著鏈表，記錄每一個(gè)嵌套調(diào)用里鏈表的元素（在執(zhí)行上下文堆棧里），然后輸出它們。