Javascript 遞歸和堆棧

2023-02-17 10:50 更新

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

我們的第一個主題是 遞歸(recursion)。

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

遞歸是一種編程模式,在一個任務可以自然地拆分成多個相同類型但更簡單的任務的情況下非常有用?;蛘撸谝粋€任務可以簡化為一個簡單的行為加上該任務的一個更簡單的變體的時候可以使用?;蛘撸拖裎覀兒芸鞎吹降哪菢?,處理某些數(shù)據(jù)結(jié)構(gòu)。

當一個函數(shù)解決一個任務時,在解決的過程中它可以調(diào)用很多其它函數(shù)。在部分情況下,函數(shù)會調(diào)用 自身。這就是所謂的 遞歸

兩種思考方式

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

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

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

  1. 迭代思路:使用 for 循環(huán):
  2. 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
  3. 遞歸思路:簡化任務,調(diào)用自身:
  4. function pow(x, n) {
      if (n == 1) {
        return x;
      } else {
        return x * pow(x, n - 1);
      }
    }
    
    alert( pow(2, 3) ); // 8

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

當 ?pow(x, n)? 被調(diào)用時,執(zhí)行分為兩個分支:

              if n==1  = x
             /
pow(x, n) =
             \
              else     = x * pow(x, n - 1)
  1. 如果 ?n == 1?,所有事情都會很簡單,這叫做 基礎 的遞歸,因為它會立即產(chǎn)生明顯的結(jié)果:?pow(x, 1)? 等于 ?x?。
  2. 否則,我們可以用 ?x * pow(x, n - 1)? 表示 ?pow(x, n)?。在數(shù)學里,可能會寫為 ?xn = x * xn-1?。這叫做 一個遞歸步驟:我們將任務轉(zhuǎn)化為更簡單的行為(x 的乘法)和更簡單的同類任務的調(diào)用(帶有更小的 n 的 ?pow? 運算)。接下來的步驟將其進一步簡化,直到 ?n? 達到 ?1?。

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


比如,為了計算 pow(2, 4),遞歸變體經(jīng)過了下面幾個步驟:

  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)用簡化為一個更簡單的函數(shù)調(diào)用,然后再將其簡化為一個更簡單的函數(shù),以此類推,直到結(jié)果變得顯而易見。

遞歸通常更短

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

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

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

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

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

這就限制了遞歸的應用,但是遞歸仍然被廣泛使用。有很多任務中,遞歸思維方式會使代碼更簡單,更容易維護。

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

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

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

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

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

當一個函數(shù)進行嵌套調(diào)用時,將發(fā)生以下的事兒:

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

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

pow(2, 3)

在調(diào)用 pow(2, 3) 的開始,執(zhí)行上下文(context)會存儲變量:x = 2, n = 3,執(zhí)行流程在函數(shù)的第 1 行。

我們將其描繪如下:


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

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

alert( pow(2, 3) );

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


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

pow(2, 2)

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

這里我們調(diào)用相同的函數(shù) pow,但這絕對沒問題。所有函數(shù)的處理都是一樣的:

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

下面是進入子調(diào)用 pow(2, 2) 時的上下文堆棧:


新的當前執(zhí)行上下文位于頂部(粗體顯示),之前記住的上下文位于下方。

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

請注意:

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

因此,更準確地說,執(zhí)行是“在子調(diào)用之后立即恢復”的。

pow(2, 1)

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

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


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

出口

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

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

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

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


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

然后,前一個上下文被恢復:


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

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

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

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

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

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

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

  return result;
}

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

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

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

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

遞歸遍歷

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

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

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

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

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

現(xiàn)在,如果我們需要一個函數(shù)來獲取所有薪資的總數(shù)。我們該怎么做?

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

我們試試遞歸吧。

我們可以看到,當我們的函數(shù)對一個部門求和時,有兩種可能的情況:

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

第一種情況是由一數(shù)組的人組成的部門,這種情況很簡單,是最基礎的遞歸。

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

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

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

// 用來完成任務的函數(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)用所有子部門,對結(jié)果求和
    }
    return sum;
  }
}

alert(sumSalaries(company)); // 7700

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

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


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

請注意,該代碼使用了我們之前講過的智能特性(smart features):

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

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

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

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

一個公司的 部門 是:

  • 一數(shù)組的人。
  • 或一個 部門 對象。

對于 Web 開發(fā)者而言,有更熟知的例子:HTML 和 XML 文檔。

在 HTML 文檔中,一個 HTML 標簽 可能包括以下內(nèi)容:

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

這又是一個遞歸定義。

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

鏈表

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

正常的選擇會是一個數(shù)組:

let arr = [obj1, obj2, obj3];

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

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

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

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

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

例如:

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

鏈表的圖形表示:


一段用來創(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;

在這兒我們可以清楚地看到,這里有很多個對象,每一個都有 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?,F(xiàn)在值 1 就被從鏈表中移除了。如果它沒有被存儲在其它任何地方,那么它會被自動從內(nèi)存中刪除。

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

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

鏈表主要的缺點就是我們無法很容易地通過元素的編號獲取元素。但在數(shù)組中卻很容易:arr[n] 是一個直接引用。而在鏈表中,我們需要從起點元素開始,順著 next 找 N 次才能獲取到第 N 個元素。

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

鏈表可以得到增強:

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

總結(jié)

術(shù)語:

  • 遞歸 是編程的一個術(shù)語,表示從自身調(diào)用函數(shù)(譯注:也就是自調(diào)用)。遞歸函數(shù)可用于以更優(yōu)雅的方式解決問題。
  • 當一個函數(shù)調(diào)用自身時,我們稱其為 遞歸步驟。遞歸的 基礎 是函數(shù)參數(shù)使任務簡單到該函數(shù)不再需要進行進一步調(diào)用。

  • 遞歸定義 的數(shù)據(jù)結(jié)構(gòu)是指可以使用自身來定義的數(shù)據(jù)結(jié)構(gòu)。
  • 例如,鏈表可以被定義為由對象引用一個列表(或 null)而組成的數(shù)據(jù)結(jié)構(gòu)。

    list = { value, next -> list }

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

    就像我們在示例 sumSalary 中看到的那樣,可以使用遞歸函數(shù)來遍歷它們。

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

任務


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

重要程度: 5

編寫一個函數(shù) 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

用三種方式實現(xiàn):

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

結(jié)果示例:

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

alert( sumTo(100) ); // 5050

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

P.P.S. 我們可以使用遞歸來計算 ?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. 當然是公式解法最快。對任何數(shù)字 n,只需要進行 3 次運算。數(shù)學大法好!

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

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


計算階乘

重要程度: 4

自然數(shù)的 階乘 是指,一個數(shù)乘以 數(shù)字減去 1,然后乘以 數(shù)字減去 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

任務是編寫一個函數(shù) factorial(n) 使用遞歸調(diào)用計算 n!。

alert( factorial(5) ); // 120

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


解決方案

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

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

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

alert( factorial(5) ); // 120

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

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

alert( factorial(5) ); // 120

斐波那契數(shù)

重要程度: 5

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

前兩個數(shù)字是 1,然后是 2(1+1),然后 3(1+2),5(2+3) 等:1, 1, 2, 3, 5, 8, 13, 21...

斐波那契數(shù)與 黃金比例 以及我們周圍的許多自然現(xiàn)象有關。

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

工作示例:

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

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

P.S. 函數(shù)運行速度要快,對 fib(77) 的調(diào)用不應該超過幾分之一秒。


解決方案

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

斐波那契數(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); // 超級慢!

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

因為函數(shù)產(chǎn)生了太多的子調(diào)用。同樣的值被一遍又一遍地計算。

例如,我們看下計算 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 來講,計算量就是巨量的。

我們可以通過記錄已經(jīng)計算過的值來進行優(yōu)化:如果一個值比如 fib(3) 已經(jīng)被計算過一次,那么我們可以在后面的計算中重復使用它。

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

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

下面是新算法的細節(jié)步驟:

開始:

// 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)。

我們移動變量: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
*/

下一步得到另一個序列數(shù):

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

/* 現(xiàn)在序列是(又加了一個數(shù)):
      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

循環(huán)從 i=3 開始,因為前兩個序列值被硬編碼到變量 a=1,b=1

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


輸出一個單鏈表

重要程度: 5

假設我們有一個單鏈表(在 遞歸和堆棧 那章有講過):

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

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

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

哪個更好:用遞歸還是不用遞歸的?


解決方法

循環(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);

請注意,我們使用了一個臨時變量 tmp 來遍歷鏈表。從技術(shù)上講,我們可以使用函數(shù)的入?yún)?nbsp;list 來代替:

function printList(list) {

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

}

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

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

從另一個方面來說,tmp 是充當了完全遍歷鏈表的角色,就像 for 循環(huán)中的 i 一樣。

遞歸解法

printList(list) 的遞歸實現(xiàn)遵循一個簡單的邏輯:為了輸出鏈表,我們應該輸出 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);

哪個更好呢?

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

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


反向輸出單鏈表

重要程度: 5

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

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


解決方案

使用遞歸

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

我們需要先輸出列表的其它元素,然后 輸出當前的元素:

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)解法也比直接輸出稍微復雜了點兒。

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

因此,我們可以做的就是直接按順序遍歷每個元素,并把它們存到一個數(shù)組中,然后反向輸出我們存儲在數(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);

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


以上內(nèi)容是否對您有幫助:
在線筆記
App下載
App下載

掃描二維碼

下載編程獅App

公眾號
微信公眾號

編程獅公眾號