斐波那契数列多种算法实现

斐波那契数列是一个经典的数学序列，其中每个数字是前两个数字之和，通常从0和1开始，即F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)，对于n > 1。有多种算法可以计算斐波那契数列：

1. **递归**：
Python示例：

   def fibonacci_recursive(n):
       if n <= 0:
           return []
       elif n == 1:
           return [0]
       elif n == 2:
           return [0, 1]
       else:
           fib_seq = fibonacci_recursive(n - 1)
           fib_seq.append(fib_seq[-1] + fib_seq[-2])
           return fib_seq

这种方法直观简洁，但对于大数值会非常慢，因为存在大量的重复计算。

2. **动态规划（迭代）**：

   def fibonacci_iterative(n):
       fib_seq = [0, 1]
       for i in range(2, n+1):
           fib_seq.append(fib_seq[i-1] + fib_seq[i-2])
       return fib_seq[:n+1] if n >= 0 else []

这种方法避免了重复计算，效率更高，但仍然线性时间复杂度。

3. **矩阵快速幂**（适合大数计算）：
使用矩阵乘法性质优化递推过程，利用分治策略降低时间复杂度至O(log n)。这个方法较为复杂，但在处理大数时效果显著。