JavaScript實現(xiàn)斐波那契數(shù)列的多種方法(全網(wǎng)最全)
更新時間：2025年04月27日 09:13:19 作者：北辰alk
斐波那契數(shù)列是計算機(jī)科學(xué)和數(shù)學(xué)中的一個經(jīng)典問題,也是面試中經(jīng)常被問到的算法題目,本文將詳細(xì)介紹 JavaScript 中實現(xiàn)斐波那契數(shù)列的 8 種不同方法,并對它們的性能特點進(jìn)行分析比較,需要的朋友可以參考下
什么是斐波那契數(shù)列？
斐波那契數(shù)列是一個無限序列，其定義如下：
- F(0) = 0
- F(1) = 1
- F(n) = F(n-1) + F(n-2) （當(dāng) n ≥ 2 時）
數(shù)列的前幾項為：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144…
1. 遞歸實現(xiàn)（最基礎(chǔ)版本）
function fibonacciRecursive(n) {
if (n <= 1) return n;
return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}
// 測試
console.log(fibonacciRecursive(10)); // 55
console.log(fibonacciRecursive(20)); // 6765
// console.log(fibonacciRecursive(50)); // 非常慢，可能導(dǎo)致堆棧溢出
特點：
- 代碼簡潔直觀，直接反映數(shù)學(xué)定義
- 時間復(fù)雜度：O(2^n) — 指數(shù)級增長，極其低效
- 空間復(fù)雜度：O(n) — 由于遞歸調(diào)用棧
- 不適用于大數(shù)計算
2. 遞歸實現(xiàn)（帶備忘錄優(yōu)化）
function fibonacciMemoization(n, memo = {}) {
if (n <= 1) return n;
if (memo[n]) return memo[n];
memo[n] = fibonacciMemoization(n - 1, memo) + fibonacciMemoization(n - 2, memo);
return memo[n];
}
// 測試
console.log(fibonacciMemoization(10)); // 55
console.log(fibonacciMemoization(50)); // 12586269025
console.log(fibonacciMemoization(100)); // 354224848179262000000
特點：
- 使用備忘錄緩存已計算結(jié)果，避免重復(fù)計算
- 時間復(fù)雜度：O(n) — 線性時間
- 空間復(fù)雜度：O(n) — 存儲備忘錄和調(diào)用棧
- 相比基礎(chǔ)遞歸版本性能大幅提升
3. 迭代實現(xiàn)（循環(huán)）
function fibonacciIterative(n) {
if (n <= 1) return n;
let a = 0, b = 1, temp;
for (let i = 2; i <= n; i++) {
temp = a + b;
a = b;
b = temp;
}
return b;
}
// 測試
console.log(fibonacciIterative(10)); // 55
console.log(fibonacciIterative(50)); // 12586269025
console.log(fibonacciIterative(100)); // 354224848179262000000
特點：
- 使用循環(huán)代替遞歸
- 時間復(fù)雜度：O(n) — 線性時間
- 空間復(fù)雜度：O(1) — 常數(shù)空間，只需存儲幾個變量
- 性能優(yōu)異，是最常用的實現(xiàn)方式之一
4. 動態(tài)規(guī)劃實現(xiàn)
function fibonacciDP(n) {
if (n <= 1) return n;
const dp = [0, 1];
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// 測試
console.log(fibonacciDP(10)); // 55
console.log(fibonacciDP(50)); // 12586269025
console.log(fibonacciDP(100)); // 354224848179262000000
特點：
- 顯式使用數(shù)組存儲中間結(jié)果
- 時間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(n) — 存儲整個數(shù)組
- 比迭代版本占用更多內(nèi)存，但更直觀展示動態(tài)規(guī)劃思想
5. 矩陣冪實現(xiàn)（數(shù)學(xué)優(yōu)化）
基于矩陣冪運算的數(shù)學(xué)公式：
[ F(n) F(n-1) ] = [ 1 1 ] ^ (n-1) [ F(n-1) F(n-2) ] [ 1 0 ]
function matrixMultiply(a, b) {
return [
[a[0][0] * b[0][0] + a[0][1] * b[1][0],
a[0][0] * b[0][1] + a[0][1] * b[1][1]],
[a[1][0] * b[0][0] + a[1][1] * b[1][0],
a[1][0] * b[0][1] + a[1][1] * b[1][1]]
];
}
function matrixPower(mat, power) {
let result = [[1, 0], [0, 1]]; // 單位矩陣
while (power > 0) {
if (power % 2 === 1) {
result = matrixMultiply(result, mat);
}
mat = matrixMultiply(mat, mat);
power = Math.floor(power / 2);
}
return result;
}
function fibonacciMatrix(n) {
if (n <= 1) return n;
const matrix = [[1, 1], [1, 0]];
const resultMatrix = matrixPower(matrix, n - 1);
return resultMatrix[0][0];
}
// 測試
console.log(fibonacciMatrix(10)); // 55
console.log(fibonacciMatrix(50)); // 12586269025
console.log(fibonacciMatrix(100)); // 354224848179262000000
特點：
- 基于數(shù)學(xué)矩陣運算
- 時間復(fù)雜度：O(log n) — 使用快速冪算法
- 空間復(fù)雜度：O(1)
- 理論上最優(yōu)解，適合極大數(shù)計算
- 實現(xiàn)較復(fù)雜，常數(shù)因子較大，在普通應(yīng)用中可能不如迭代版本快
6. 閉包實現(xiàn)（生成器模式）
function createFibonacciGenerator() {
let a = 0, b = 1;
return function() {
const temp = a;
a = b;
b = temp + b;
return temp;
};
}
// 測試
const generateFibonacci = createFibonacciGenerator();
console.log(generateFibonacci()); // 0
console.log(generateFibonacci()); // 1
console.log(generateFibonacci()); // 1
console.log(generateFibonacci()); // 2
console.log(generateFibonacci()); // 3
console.log(generateFibonacci()); // 5
// 可以無限調(diào)用生成數(shù)列
特點：
- 使用閉包保存狀態(tài)
- 每次調(diào)用返回下一個斐波那契數(shù)
- 適合需要逐個生成數(shù)列的場景
- 時間復(fù)雜度：O(1) 每次調(diào)用
- 空間復(fù)雜度：O(1)
7. 生成器函數(shù)實現(xiàn)（ES6）
function* fibonacciGenerator() {
let a = 0, b = 1;
while (true) {
yield a;
[a, b] = [b, a + b];
}
}
// 測試
const fibGen = fibonacciGenerator();
console.log(fibGen.next().value); // 0
console.log(fibGen.next().value); // 1
console.log(fibGen.next().value); // 1
console.log(fibGen.next().value); // 2
console.log(fibGen.next().value); // 3
console.log(fibGen.next().value); // 5
// 可以無限調(diào)用
特點：
- 使用 ES6 生成器函數(shù)
- 惰性求值，按需生成
- 代碼簡潔優(yōu)雅
- 適合需要逐個獲取數(shù)列的場景
8. 通項公式實現(xiàn)（Binet公式）
斐波那契數(shù)列的通項公式（Binet公式）：
F(n) = (φ^n - ψ^n) / √5 其中 φ = (1 + √5)/2 ≈ 1.618（黃金比例） ψ = (1 - √5)/2 ≈ -0.618
function fibonacciFormula(n) {
const sqrt5 = Math.sqrt(5);
const phi = (1 + sqrt5) / 2;
const psi = (1 - sqrt5) / 2;
return Math.round((Math.pow(phi, n) - Math.pow(psi, n)) / sqrt5);
}
// 測試
console.log(fibonacciFormula(10)); // 55
console.log(fibonacciFormula(20)); // 6765
console.log(fibonacciFormula(50)); // 12586269025
console.log(fibonacciFormula(70)); // 190392490709135
特點：
- 直接使用數(shù)學(xué)公式計算
- 時間復(fù)雜度：O(1) — 理論上
- 實際受限于浮點數(shù)精度，n較大時會有精度誤差
- JavaScript中大約在n=75左右開始出現(xiàn)精度問題
- 適合中等規(guī)模n的計算
性能比較
下表比較了不同實現(xiàn)方式在計算F(40)時的性能表現(xiàn)（測試環(huán)境：Node.js 16.x）：
| 方法 | 時間復(fù)雜度 | 空間復(fù)雜度 | 計算F(40)時間(ms) |
|---|---|---|---|
| 基礎(chǔ)遞歸 | O(2^n) | O(n) | ~1100ms |
| 備忘錄遞歸 | O(n) | O(n) | ~0.05ms |
| 迭代 | O(n) | O(1) | ~0.02ms |
| 動態(tài)規(guī)劃 | O(n) | O(n) | ~0.03ms |
| 矩陣冪 | O(log n) | O(1) | ~0.1ms |
| Binet公式 | O(1) | O(1) | ~0.01ms |
最佳實踐建議
- 一般情況：使用迭代法，它在代碼簡潔性、性能和內(nèi)存使用之間取得了良好平衡
- 需要多次計算：使用備忘錄遞歸，可以緩存之前的結(jié)果
- 極大數(shù)計算：考慮矩陣冪方法，雖然實現(xiàn)復(fù)雜但時間復(fù)雜度最優(yōu)
- 按需生成數(shù)列：使用生成器函數(shù)或閉包實現(xiàn)
- 避免使用：基礎(chǔ)遞歸實現(xiàn)，性能極差
完整示例代碼
下面是一個完整的實現(xiàn)，包含所有方法并添加了性能測試：
// 1. 基礎(chǔ)遞歸
function fibonacciRecursive(n) {
if (n <= 1) return n;
return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}
// 2. 備忘錄遞歸
function fibonacciMemoization(n, memo = {}) {
if (n <= 1) return n;
if (memo[n]) return memo[n];
memo[n] = fibonacciMemoization(n - 1, memo) + fibonacciMemoization(n - 2, memo);
return memo[n];
}
// 3. 迭代
function fibonacciIterative(n) {
if (n <= 1) return n;
let a = 0, b = 1, temp;
for (let i = 2; i <= n; i++) {
temp = a + b;
a = b;
b = temp;
}
return b;
}
// 4. 動態(tài)規(guī)劃
function fibonacciDP(n) {
if (n <= 1) return n;
const dp = [0, 1];
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// 5. 矩陣冪
function matrixMultiply(a, b) {
return [
[a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
[a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]]
];
}
function matrixPower(mat, power) {
let result = [[1, 0], [0, 1]];
while (power > 0) {
if (power % 2 === 1) {
result = matrixMultiply(result, mat);
}
mat = matrixMultiply(mat, mat);
power = Math.floor(power / 2);
}
return result;
}
function fibonacciMatrix(n) {
if (n <= 1) return n;
const matrix = [[1, 1], [1, 0]];
const resultMatrix = matrixPower(matrix, n - 1);
return resultMatrix[0][0];
}
// 6. 閉包生成器
function createFibonacciGenerator() {
let a = 0, b = 1;
return function() {
const temp = a;
a = b;
b = temp + b;
return temp;
};
}
// 7. ES6生成器
function* fibonacciGenerator() {
let a = 0, b = 1;
while (true) {
yield a;
[a, b] = [b, a + b];
}
}
// 8. Binet公式
function fibonacciFormula(n) {
const sqrt5 = Math.sqrt(5);
const phi = (1 + sqrt5) / 2;
const psi = (1 - sqrt5) / 2;
return Math.round((Math.pow(phi, n) - Math.pow(psi, n)) / sqrt5);
}
// 性能測試函數(shù)
function testPerformance(fn, n, name) {
const start = process.hrtime.bigint();
const result = fn(n);
const end = process.hrtime.bigint();
console.log(`${name}(${n}) = ${result}, 耗時: ${(end - start) / 1000000n}ms`);
}
// 測試
const testNum = 40;
console.log('--- 性能測試 ---');
testPerformance(fibonacciRecursive, testNum, '基礎(chǔ)遞歸');
testPerformance(fibonacciMemoization, testNum, '備忘錄遞歸');
testPerformance(fibonacciIterative, testNum, '迭代');
testPerformance(fibonacciDP, testNum, '動態(tài)規(guī)劃');
testPerformance(fibonacciMatrix, testNum, '矩陣冪');
testPerformance(fibonacciFormula, testNum, 'Binet公式');
console.log('\n--- 生成器測試 ---');
const generateFibonacci = createFibonacciGenerator();
console.log('閉包生成器前10項:');
for (let i = 0; i < 10; i++) {
console.log(generateFibonacci());
}
const fibGen = fibonacciGenerator();
console.log('\nES6生成器前10項:');
for (let i = 0; i < 10; i++) {
console.log(fibGen.next().value);
}
總結(jié)
JavaScript 實現(xiàn)斐波那契數(shù)列有多種方法，每種方法都有其適用場景：
- 學(xué)習(xí)遞歸：基礎(chǔ)遞歸實現(xiàn)（但不要用于生產(chǎn)環(huán)境）
- 一般用途：迭代法或備忘錄遞歸
- 高性能需求：矩陣冪方法
- 數(shù)列生成：生成器函數(shù)或閉包實現(xiàn)
- 數(shù)學(xué)探索：Binet公式實現(xiàn)
在實際開發(fā)中，迭代法通常是最佳選擇，因為它具有優(yōu)秀的性能（O(n)時間，O(1)空間）和代碼簡潔性。對于需要多次計算不同斐波那契數(shù)的場景，備忘錄遞歸可以進(jìn)一步提高效率。
以上就是JavaScript實現(xiàn)斐波那契數(shù)列的多種方法(全網(wǎng)最全)的詳細(xì)內(nèi)容，更多關(guān)于JavaScript斐波那契數(shù)列的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
微信小程序?qū)崿F(xiàn)團(tuán)購或秒殺批量倒計時
這篇文章主要為大家詳細(xì)介紹了微信小程序?qū)崿F(xiàn)團(tuán)購或秒殺批量倒計時，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-07-07
今天小編就為大家分享一篇layer擴(kuò)展打開/關(guān)閉動畫的方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-09-09
下面小編就為大家?guī)硪黄鶭S獲取元素的位置與尺寸實現(xiàn)方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-10-10
JavaScript指定字段排序方法sortFun函數(shù)
這篇文章主要介紹了JavaScript指定字段排序方法sortFun函數(shù)，數(shù)組的排序方法是sort，但是它并不支持根據(jù)指定的字段進(jìn)行排序，而sortFun可以根據(jù)指定的字段進(jìn)行排序，需要的朋友可以參考下2023-05-05
這篇文章主要介紹了純JS代碼實現(xiàn)隔行變色鼠標(biāo)移入高亮的相關(guān)資料,非常不錯，具有一定的參考借鑒價值，需要的朋友可以參考下2016-11-11
這篇文章主要介紹了微信小程序使用npm支持踩坑，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-11-11
這篇文章主要介紹了web頁面和微信小程序頁面實現(xiàn)瀑布流效果，本文通過實例代碼圖文介紹，給大家介紹的非常詳細(xì)，具有一定的參考借鑒價值 ,需要的朋友可以參考下2018-09-09
這篇文章主要介紹了TypeScript中的函數(shù)，一般JavaScript中的函數(shù)定義常用的有使用function關(guān)鍵字聲明函數(shù)、使用字面量方式聲明函數(shù)、使用箭頭函數(shù)聲明函數(shù)等幾種函數(shù)，下面我們大家就一起進(jìn)入文章了解這些函數(shù)的具體定義吧,需要的朋友可以參考一下2021-12-12
用JavaScript腳本實現(xiàn)Web頁面信息交互
這篇文章主要介紹了用JavaScript腳本實現(xiàn)Web頁面信息交互2006-10-10
JavaScript實現(xiàn)將xml轉(zhuǎn)換成html table表格的方法
這篇文章主要介紹了JavaScript實現(xiàn)將xml轉(zhuǎn)換成html table表格的方法,實例分析了javascript操作XML文件與table表格的技巧,非常具有實用價值,需要的朋友可以參考下2015-04-04