面試官：用“尾遞歸”優化斐波那契函數

1 前言

程式設計題：輸入一個整數n，輸出斐波那契數列的第n項

有些面試官喜歡問這道題。可能你覺得這太簡單了，用遞歸或遞推一下子就實作了。

正當你信心滿滿用了兩種方式實作的時候...

面試官：現在請用“尾遞歸”優化你的遞歸實作，用“ES6解構指派”優化你的遞推實作

...

這時候如果你的基本功不紮實，可能你就懵了。

就是這麼簡單的一道題，包含着相當多的JS知識點，尤其是它的優化過程可以看出你的基本功紮不紮實，是以有些面試官喜歡問這道題。

下面我們來看遞歸和遞推這兩種實作以及它們各自的優化過程

2 遞歸和尾遞歸

2.1 遞歸實作

先來看遞歸實作：

function fibonacci(n) {
  if (n === 0 || n === 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}
           

來看看這段代碼有什麼問題

第一個問題很容易看出來，就是當

n

非常大的時候，遞歸深度過大導緻棧記憶體溢出，即“爆棧”

第二個問題就是有相當多的重複計算，比如：

fibonacci(7)
= fibonacci(6) + fibonacci(5) // 這裡計算了f(5)，下面又計算了一次f(5)
= (fibonacci(5) + fibonacci(4)) + (fibonacci(4) + fibonacci(3)) // 這裡計算了兩次f(5)
...
           

2.2 尾調用

在解決上面兩個問題之前，先來了解一下什麼是尾調用

尾調用：一個函數裡的最後一個動作是傳回一個函數的調用結果，即最後一步新調用的傳回值被目前函數傳回

比如：

function f(x) {
  return g(x)
}
           

下面這些情況不屬于尾調用：

function f(x) {
  return g(x) + 1 // 先執行g(x)，最後傳回g(x)的傳回值+1
}

function f(x) {
  let ret = g(x) // 先執行了g(x)
  return ret // 最後傳回g(x)的傳回值
}
           

2.3 尾調用消除（尾調用優化）

一個函數調用時，JS引擎會建立一個新的棧幀并将其推入調用棧頂部，用于表示該次函數調用

當一個函數調用發生時，計算機必須“記住”調用函數的位置——傳回位置，才可以在調用結束時帶着傳回值回到該位置，傳回位置一般儲存在調用棧上。

在尾調用這種特殊情形中，計算機理論上可以不需要記住尾調用的位置，而從被調用的函數直接帶着傳回值傳回目前函數的傳回位置（相當于直接連續傳回兩次）

如下圖：由于尾調用，理論上可以不記住位置2，而從函數g直接帶着傳回值傳回到位置1（即函數f的傳回位置）

由于尾調用之前的工作已經完成了，是以目前函數幀（即調用時建立的棧幀）上包含局部變量等等大部分的東西都不需要了，目前的函數幀經過适當的變動以後可以直接當做尾調用的函數的幀使用，然後程式就可以跳到被尾調用的函數。

用上圖中的例子來解釋就是，函數

f

尾調用函數

g

之前的工作已經完成了，是以調用函數

f

時建立的函數幀直接給函數

g

用了，就不需要重新給函數

g

建立棧幀。

這種函數幀變動重複使用的過程就叫做尾調用消除或尾調用優化

2.4 尾遞歸

如果函數在尾調用位置調用自身，則稱這種情況為尾遞歸。尾遞歸是一種特殊的尾調用，即在尾部直接調用自身的遞歸函數

由于尾調用消除，使得尾遞歸隻存在一個棧幀，是以永遠不會“爆棧”。

ES6

規定了所有

ECMAScript

的實作都必須部署“尾調用消除”，是以在

ES6

中隻要使用尾遞歸，就不會發生棧溢出

2.5 尾遞歸優化斐波那契函數

回到

2.1

中斐波那契函數存在的兩個問題，可以使用尾遞歸來解決“爆棧”的問題

需要注意的是：ES6的尾調用消除隻在嚴格模式下開啟

為了讓原來的遞歸函數變成尾遞歸，需要改寫函數，讓函數最後一步調用自身

// 原遞歸函數
function fibonacci(n) {
  if (n === 0 || n === 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

// 修改後
'use strict'
function fibonacci(n, pre, cur) {
  if (n === 0) {
    return n;
  }
  if (n === 1) {
    return cur;
  }
  return fibonacci(n - 1, cur, pre + cur);
}
// 調用
fibonacci(6, 0, 1)
           

修改後的計算邏輯是這樣的：

f(6, 0, 1) 
= f(5, 1, 0 + 1) 
= f(4, 1, 1 + 1) 
= f(3, 2, 1 + 2) 
= f(2, 3, 2 + 3)
= f(1, 5, 3 + 5)
= 8
           

你可能已經發現了，事實上這就是遞推，從

0 + 1

開始計算，一直到第

n

項

另外，可以使用

ES6

的預設參數來讓函數隻傳入一個參數

n

即可

'use strict'
function fibonacci(n, pre = 0, cur = 1) {
  if (n === 0) {
    return n;
  }
  if (n === 1) {
    return cur;
  }
  return fibonacci(n - 1, cur, pre + cur);
}
fibonacci(6)
           

此外，由于函數改成了尾遞歸的形式，第

f(n)

隻與

f(n-1)

有關，大量重複計算的問題也得到了解決

3 遞推

遞推實作

function fibonacci(n) {
  let cur = 0;
  let next = 1;
  for (let i = 0; i < n; i++) {
    let temp = cur;
    cur = next;
    next += temp;
  }
  return cur;
}
           

遞推在性能上沒啥好優化的，但是我們可以在形式上進行優化

利用

ES6

的解構指派可以省去中間變量

function fibonacci(n) {
  let cur = 0;
  let next = 1;
  for (let i = 0; i < n; i++) {
    [cur, next] = [next, cur + next]
  }
  return cur;
}