# 編程技術中求解斐波拉契數列的示例代碼
斐波那契數列（Fibonacci sequence）是計算機科學中經典的遞歸問題，其定義為：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)（n≥2）。本文將展示三種典型實現方式。
## 1. 遞歸實現
```python
def fib_recursive(n):
if n <= 1:
return n
return fib_recursive(n-1) + fib_recursive(n-2)
特點：代碼簡潔但存在重復計算，時間復雜度O(2^n)，僅適用于小規模計算。
def fib_dp(n):
if n == 0:
return 0
dp = [0] * (n+1)
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
優化：通過存儲中間結果避免重復計算，時間復雜度O(n)，空間復雜度O(n)。
def fib_iter(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
優勢：空間復雜度優化至O(1)，保持O(n)時間復雜度，是最常用的實踐方案。
| 方法 | 時間復雜度 | 空間復雜度 |
|---|---|---|
| 遞歸 | O(2^n) | O(n) |
| 動態規劃 | O(n) | O(n) |
| 迭代 | O(n) | O(1) |
實際開發中建議優先選擇迭代法，當需要記錄整個序列時可采用動態規劃實現。 “`
注：示例代碼使用Python語法，其他語言實現邏輯類似。對于超大規模計算（如n>1e6），可采用矩陣快速冪算法將時間復雜度優化至O(log n)。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
