在 JavaScript 中實作斐波那契數列：常見方法和變體

作為開發人員，您可能遇到過編寫函數來計算斐波那契數列中的值的任務。這個經典問題經常出現在程式設計面試中，通常要求遞歸實現。然而，面試官有時可能會要求具體的方法。在本文中，我們將探討 JavaScript 中最常見的斐波那契數列實作。

什麼是斐波那契數列？

首先，讓我們回顧一下。斐波那契數列是一系列數字，其中每個數字都是前兩個數字的總和。以 0 和 1 開頭：

0、1、1、2、3、5、8、13、21、34、55、…

常見的實施方法

1。遞歸方法

最傳統的請求是遞歸實作：

function fibonacciRecursive(n) {
  if (n < 1) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }
  return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

雖然簡單，但這種方法對於較大的 n 值來說表現不佳。在配備 16 GB RAM 的 MacBook Pro i9 上，計算第 40 個斐波那契數大約需要 1.5 秒：

console.time('Recursive');
fibonacciRecursive(40);
console.timeEnd('Recursive');

VM379:3 Recursive: 1521.569091796875 ms

嘗試計算第 50 個數字導致 Chrome 標籤頁無回應。

2。有緩存的遞歸方法（記憶）

這個問題的下一個變體是透過在我們的遞歸實作中加入快取機制來提高效能：

function fibonacciCached(n, cached = {[0]: 0, [1]: 1}) {
  if (n < 1) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }

  if (cached[n]) {
    return cached[n];
  }

  cached[n] = 
    fibonacciCached(n - 1, cached) + fibonacciCached(n - 2, cached);

  return cached[n];
}

這種方法引入了一個初始值為 0 和 1 的快取物件。對於任何給定的數字，我們首先檢查是否已經計算了其斐波那契值。如果是這樣，我們返回快取的結果而不是重新計算它。否則，我們計算該值並將其儲存在快取中。

效能提升非常顯著（當然是因為使用了額外的記憶體）。計算第 40 個斐波那契數大約需要 0.02 毫秒：

console.time('Recursive, with caching');
fibonacciCached(40);
console.timeEnd('Recursive, with caching');

VM382:3 Recursive, with caching: 0.01806640625 ms

3。使用 for 迴圈的迭代方法

另一個常見的變體是使用 for 迴圈實作斐波那契數列：

function fibonacciWithIteration(n) {
    if (n <= 0) {
        return 0;
    }
    if (n === 1) {
        return 1;
    }

    let prev = 0;
    let next = 1;
    let result = 1;

    for (let i = 2; i <= n; i++) {
        result = prev + next;
        [prev, next] = [next, prev + next];
    }
    return result;
}

這種方法比基本的遞歸方法（沒有快取的方法）快得多：

console.time('With iteration');
fibonacciWithIteration(40);
console.timeEnd('With iteration');

VM44:22 With iteration: 0.10107421875 ms

迭代方法可以有效處理非常大的輸入值：

console.time('With iteration');
const result = fibonacciWithIteration(1400);
console.log(result);
console.timeEnd('With iteration');

VM325:22 1.7108476902340223e+292
VM325:23 With iteration: 0.5830078125 ms

獎勵：以數組形式傳回斐波那契數列

面試官也可能要求您以數組的形式返回直到第 n 個數字的整個斐波那契數列。讓我們使用遞歸和迭代方法來實現這一點。

遞歸方法

function fibonacciSequence(n) {
  if (n === 0) {
      return [0];
  }
  if (n === 1) {
      return [0, 1];
  }

  const arr = fibonacciSequence(n - 1);
  const currentValue = arr[n - 1] + arr[n - 2];

  return [...arr, currentValue];
}

console.log(fibonacciSequence(5)); // [0, 1, 1, 2, 3, 5]

函數的工作原理如下：

1. 對於 0 和 1，我們傳回硬編碼數組。
2. 其他情況：

• 我們取得前一個數字的序列並將其儲存在 arr 中。
• 我們透過將 arr 的最後兩個值相加來計算 currentValue。
• 我們將 arr 和 currentValue 合併到一個新陣列中並傳回它。

迭代方法

function fibonacciSequenceWithIteration(n) {
  if (n < 1) {
    return [0];
  }

  let prev = 0;
  let next = 1;
  const arr = [prev, next];

  for (let i = 2; i <= n; i++) {
    arr.push(prev + next);
    [prev, next] = [next, prev + next];
  }
  return arr;
}

console.log(fibonacciSequenceWithIteration(5)); // [0, 1, 1, 2, 3, 5]

函數的工作原理如下：

1. 如果輸入為 0，我們傳回一個僅包含元素 0 的陣列。
2. 其他情況：

• 我們初始化 prev 和 next 變數來儲存前一個和下一個值。
• 我們建立初始值為 [0, 1] 的 arr。
• 我們從 2 迭代到 n，在每次迭代中將 prev 和 next 的總和推入 arr。
• 我們更新上一個和下一個值並繼續下一個迭代。

結論

雖然本文涵蓋了幾種常見的斐波那契數列實現，但它並不是詳盡的列表。如果您在採訪或工作中遇到其他變化，請在評論中分享！

隨時了解最新的 JavaScript 和軟體開發新聞！加入我的 Telegram 頻道以獲取更多見解和討論：TechSavvy：前端和後端。

以上是在 JavaScript 中實作斐波那契數列：常見方法和變體的詳細內容。更多資訊請關注PHP中文網其他相關文章！