斐波那契数列：从递归到迭代的算法优化实践

1. 斐波那契数列与兔子繁殖问题解析

斐波那契数列是计算机科学和数学中一个经典的问题序列，它以意大利数学家列昂纳多·斐波那契命名。这个数列在自然界中广泛存在，比如植物的叶序、花瓣数目等。而最著名的应用场景之一，就是描述兔子繁殖问题的数学模型。

这个数列的定义很简单：前两个数都是1，从第三个数开始，每个数都是前两个数之和。用数学表达式表示就是：
F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2) (n≥3)

在兔子繁殖问题中，假设：

• 初始有一对新生的兔子（第1个月）
• 兔子从出生后第三个月开始每月生一对新兔子
• 兔子永远不会死亡

这种情况下，每个月的兔子总数恰好就是斐波那契数列。让我们看看前几个月的情况：

第1个月：1对（新生）
第2个月：1对（未成熟）
第3个月：2对（原对成熟并繁殖）
第4个月：3对（原对继续繁殖，新生对未成熟）
第5个月：5对（两对成熟兔子各自繁殖）

2. 递归实现及其问题分析

2.1 基础递归实现

递归是最直观的实现方式，因为它直接反映了斐波那契数列的数学定义：

c复制#include<stdio.h>

int fib(int n) {
    if (n <= 2) return 1;
    return fib(n-1) + fib(n-2);
}

int main() {
    for (int i = 1; i <= 40; i++) {
        printf("%d ", fib(i));
    }
    return 0;
}

这个实现简洁明了，但存在严重的效率问题。计算fib(40)时，需要进行大量的重复计算。

2.2 递归的时间复杂度分析

递归实现的时间复杂度是指数级的O(2^n)。这是因为：

• 每个fib(n)调用会产生两个子调用：fib(n-1)和fib(n-2)
• 调用树呈指数级增长
• 计算fib(40)需要进行约2^40次操作（约1万亿次）

这种实现方式对于n=40还能勉强运行（现代计算机约需几秒），但对于更大的n值就完全不实用了。

2.3 递归的优化思路

虽然基础递归效率低下，但我们可以通过一些技术来优化：

1. 记忆化(Memoization)：存储已经计算过的结果
2. 尾递归优化：