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

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

Tags: javascript 前端開發前端面試前端面試手寫代碼尾遞歸