在 JavaScript 中實作斐波那契數列：常見方法和變體-js教程-PHP中文網

Implementing the Fibonacci Sequence in JavaScript: Common Approaches and Variations

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

登入後複製

函數的工作原理如下：

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

我們取得前一個數字的序列並將其儲存在 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]

登入後複製

函數的工作原理如下：