📘斐波那契递归

2026-08-30
⭐⭐ GESP 3级

📖概念讲解

斐波那契数列是经典的递归入门题：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)。每项等于前两项之和，天然适合用递归来写。

但朴素递归有个大坑：重复计算。算 F(5) 时，F(3) 会被算 2 次，F(2) 会被算 3 次，指数级爆炸。考试中 n 稍大就超时。

核心易错点：①忘记写终止条件（F(0)=0, F(1)=1），导致无限递归栈溢出；②暴力递归效率太低，实际做题要用记忆化或循环。

💻代码示例

1#include <iostream>
2using namespace std;
3
4// 朴素递归：简单但慢，适合理解概念
5int fib(int n) {
6 if (n <= 1) return n; // 终止条件：F(0)=0, F(1)=1
7 return fib(n - 1) + fib(n - 2); // 递归公式：F(n)=F(n-1)+F(n-2)
8}
9
10// 循环写法：高效，O(n)时间 O(1)空间
11int fibLoop(int n) {
12 if (n <= 1) return n;
13 int a = 0, b = 1, c; // a=F(i-2), b=F(i-1), c=F(i)
14 for (int i = 2; i <= n; i++) { // 从第2项递推到第n项
15 c = a + b; // 当前项 = 前两项之和
16 a = b; // 滚动：a往前挪一位
17 b = c; // 滚动：b往前挪一位
18 }
19 return b;
20}
21
22int main() {
23 for (int i = 0; i <= 10; i++)
24 cout << "F(" << i << ")=" << fibLoop(i) << " ";
25 return 0;
26}

# 输出: F(0)=0 F(1)=1 F(2)=1 F(3)=2 F(4)=3 F(5)=5 F(6)=8 F(7)=13 F(8)=21 F(9)=34 F(10)=55

🧩互动小测

❓ fib(5) 朴素递归会被调用多少次？

❓ 下面代码的输出是什么？
int f(int n){ return n<=1?n:f(n-1)+f(n-2);} cout<

🏋️动手练一练

📝 编程练习

题目：给定整数 n（0 ≤ n ≤ 40），输出斐波那契数列第 n 项。
提示：用循环写法，注意 n=0 和 n=1 是特殊情况。
进阶：如果要求用记忆化递归（数组存已算过的值），怎么改？
参考答案（循环法）： 
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    if (n <= 1) { cout << n; return 0; }
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    cout << b;
    return 0;
}

要点：循环只需要 O(n) 时间 O(1) 空间。朴素递归是 O(2^n)，n=40 会很慢。如果用记忆化，开一个 memo 数组，递归前先查表就行。

📝易错点提醒

⚠️ 易错点 1：忘记终止条件 n<=1，直接导致无限递归栈溢出。
⚠️ 易错点 2：朴素递归效率极低，O(2^n)。考试中 n>30 就会超时，必须用循环或记忆化。
⚠️ 易错点 3：循环写法中变量滚动顺序不能反！必须先算 c=a+b，再 a=b，最后 b=c。顺序反了结果就错了。
← 2026-08-29 2026-08-30 2026-08-31 →
学完这个知识点后点一下