数据结构：递归：斐波那契数列（Fibonacci Sequence）

目录

什么是斐波那契数列？

用递归推导Fibonacci

复杂度分析

 用迭代推导Fibonacci

 复杂度分析

 递归优化：记忆化递归（Memoized Recursion） 

复杂度分析

什么是斐波那契数列？

斐波那契数列（Fibonacci Sequence）是这样一个序列：

从第 2 项开始，每一项等于前两项之和。

F(0) = 0
F(1) = 1
F(2) = 1        ← 0 + 1
F(3) = 2        ← 1 + 1
F(4) = 3        ← 1 + 2
F(5) = 5        ← 2 + 3
F(6) = 8        ← 3 + 5
F(7) = 13       ← 5 + 8
F(8) = 21       ← 8 + 13
...

用递归推导Fibonacci

我们用自然语言重新表述递归的核心思想：

要计算第 n 项，只需递归调用第 n−1 项和第 n−2 项的计算，直到我们知道结果的那一刻（也就是 n==0 或 n==1）为止。

所以递归的思想是：

1. 边界条件（Base Case）：当 n == 0 或 n == 1，直接返回 n 本身。

2. 递归调用：否则，就返回 fib(n - 1) + fib(n - 2)。

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

复杂度分析

我们以 fib(5) 为例，画出调用树结构 

                      fib(5)
                     /      \
               fib(4)        fib(3)
              /     \        /     \
         fib(3)     fib(2)  fib(2)  fib(1)
        /     \     /   \   /   \
   fib(2)   fib(1) fib(1) fib(0) fib(1)
   /   \
fib(1) fib(0)

📈 时间复杂度 

T(n) = T(n-1) + T(n-2) + O(1)

其中：

• T(n-1)：递归求 fib(n-1)

• T(n-2)：递归求 fib(n-2)

• O(1)：加法操作 + 1 次返回 

 所以 T(n) 的增长趋势就是 Fibonacci 的大小增长趋势，即：

T(n) ≈ O(2ⁿ)

🔍 你可以这么理解这个复杂度

在最差情况下，调用树是一个二叉树：

• 高度：n

• 节点数 ≈ 2ⁿ（满二叉树）

• 每个节点代表一次函数调用 → 所以总时间就是 O(2ⁿ)

 故时间复杂度是 O(2ⁿ)

 用迭代推导Fibonacci

核心问题：如何“推进到下一步”？

我们写下第一项和第二项： 

step 0: 0   → 这是 F(0)
step 1: 1   → 这是 F(1)

从 step 2 开始，每一步我们都：

1. 把上面两个数加起来，得出当前项

2. 把这两个数“往前移动”，以备下一次使用

因此，我们要用变量表示这个“移动窗口”，让它们“滑动”到下一项：（有点类似于SQL中的窗口滑动）

我们只要两个变量：

a = 0;   // 表示 F(n - 2)
b = 1;   // 表示 F(n - 1)

我们用第三个变量：

next = a + b;  // 当前项 F(n)

之后我们把窗口向前滑动：

a = b;
b = next;

 这三步形成了一个“更新循环”。

完整代码：

思考逻辑结构

• 需要处理：

  • n == 0：返回 0

  • n == 1：返回 1

• 从 i = 2 开始循环，到 i == n

• 使用变量 a, b, next 来存储 F(n-2), F(n-1), F(n)

#include <iostream>
using namespace std;

int fib_iterative(int n) {
    if (n == 0) return 0;  // 基础情况
    if (n == 1) return 1;  // 基础情况

    int a = 0;  // 表示 F(0)
    int b = 1;  // 表示 F(1)
    int next;   // 用来存当前项 F(n)

    for (int i = 2; i <= n; ++i) {
        next = a + b;  // 当前项
        a = b;         // 向前滑动
        b = next;      // 向前滑动
    }

    return next;  // 最终 next 是 F(n)
}

 复杂度分析

⏱️时间复杂度（Time Complexity）

看看上面这段代码里，哪些操作会随着 n 增长而重复？

• for (int i = 2; i <= n; ++i)
  这个循环会执行 (n - 1) 次（从 i=2 到 i=n）

• 每次循环内，做了以下操作：

  • next = a + b;

  • a = b;

  • b = next;

这些都是常数时间操作，每次循环都执行固定次数。

✅ 结论：

• 循环执行 n - 1 次，每次是 O(1)

• 所以：时间复杂度为 O(n)

🗃️空间复杂度（Space Complexity） 

我们在函数中定义了：

• int a = 0;

• int b = 1;

• int next;

无论 n 多大，我们始终只使用这 3 个变量来计算 Fibonacci 数列。

我们没有使用数组、没有递归栈，也没有任何随着 n 增长而变大的数据结构。

✅ 结论：

• 内存使用是常数级别

• 所以：空间复杂度为 O(1)

 递归优化：记忆化递归（Memoized Recursion） 

在递归实现中，你会发现一个规律：很多调用是重复的！

例如在fib(5)中：

• fib(3) 被调用了 2 次

• fib(2) 被调用了 3 次

• fib(1) 被调用了 5 次

这就是递归 Fibonacci 的最大问题 —— 重叠子问题！这是一种指数级的浪费。

✅ 第一性解法：我们应该记住已经算过的结果。 

💡如何实现“记住”？

我们用一种最基本的数据结构 —— 数组，开一个数组 memo[] 存储结果。

逻辑流程：

我先检查 memo[n] 是否已经存有值：

• 如果有，就直接返回它；

• 如果没有，就计算出来，并把结果存进去。

一步一步改造原始递归函数

原始递归（无记忆）：

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

✅ 加入“备忘录数组”（记忆）

const int MAX = 1000;
int memo[MAX];  // 初始化为 -1 表示未计算

void init_memo() {
    for (int i = 0; i < MAX; ++i) {
        memo[i] = -1;
    }
}

int fib(int n) {
    if (memo[n] != -1) return memo[n];  // 如果已经算过了

    if (n == 0) return memo[0] = 0;
    if (n == 1) return memo[1] = 1;

    // 没算过，就递归计算，并存入 memo
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

刚刚实现的其实是“Top-Down 动态规划”

虽然我们没有提任何术语，但你用的是一种“从上往下递归，同时缓存子结果”的方法。

如果你用迭代而非递归，那就是“Bottom-Up 动态规划”。

复杂度分析