> **GESP等级：四级 | 考级考点：GESP Python 四级**

# 第11节：递推算法——从已知推出未知

---

## 一、课程概览

| 项目 | 内容 |
|------|------|
| 课程名称 | 递推算法——兔子生兔子&爬楼梯 |
| 课程时长 | 60分钟 |
| 教学形式 | 故事导入（兔子数列）+ 身体动作（斐波那契手势）+ turtle螺旋线 + 动手编程 |
| 核心目标 | 理解递推思想：从已知条件一步步推出后面的结果 |

### 教学目标

| 维度 | 目标描述 |
|------|----------|
| 知识目标 | 理解递推的概念，掌握斐波那契数列的规律和公式 |
| 技能目标 | 能用代码实现斐波那契数列、爬楼梯等经典递推问题 |
| 思维目标 | 建立"找规律→列公式→循环实现"的递推思维 |
| 情感目标 | 感受数学在编程中的美妙应用，欣赏斐波那契螺旋线的美 |

### 教学重点与难点

| 类型 | 内容 |
|------|------|
| 重点 | 递推公式f(n)=f(n-1)+f(n-2)的理解和应用 |
| 难点 | 把实际问题转化为递推公式 |
| 易错点 | 边界条件f(1)=1, f(2)=1；循环初始值设置 |

---

## 二、教学准备

### 教具准备
1. 电脑+Python环境（已安装turtle库）
2. 投影仪/大屏幕（展示斐波那契螺旋线动画）
3. 兔子图片（公兔、母兔、小兔的图片）
4. 方格纸（画斐波那契正方形）
5. 楼梯示意图（画n阶楼梯）
6. 斐波那契螺旋线海报

### 课前准备
- 测试斐波那契螺旋线代码
- 准备兔子繁殖动画
- 打印斐波那契数列卡片
- 准备"多米诺骨牌"（演示递推过程）

---

## 三、教学过程（60分钟）

---

### 第一部分：导入环节（10分钟）——兔子生兔子

#### 1.1 故事：神奇的兔子问题（5分钟）

**老师开始讲故事**：

"很久很久以前，有一个数学家叫斐波那契，他提出了一个有趣的问题——"

**故事设定**：
"在一个小岛上，有一对刚出生的兔子（一公一母）。"
"兔子需要一个月才能长大。"
"长大后的兔子，每个月都能生一对新兔子（一公一母）。"
"而且兔子永远不会死！"

**提问**："那么，第1个月有几对兔子？第2个月呢？第3个月呢？"

**师生互动一步步推**：

> **第1个月**：
> "刚出生的小兔，还没长大，不能生宝宝。"
> "所以第1个月：1对兔子" 🐰

> **第2个月**：
> "小兔长大了，变成大兔。但还没到生宝宝的时候。"
> "所以第2个月还是：1对兔子" 🐰

> **第3个月**：
> "大兔生了一对小小兔！"
> "所以第3个月：大兔1对 + 小兔1对 = 2对兔子" 🐰🐰

> **第4个月**：
> "原来的大兔再生一对新小兔。"
> "原来的小兔长大了。"
> "所以第4个月：原来的2对 + 新生1对 = 3对兔子" 🐰🐰🐰

> **第5个月**：
> "现在有2对大兔（各生1对）= 新生2对"
> "加上原来的3对 = 5对兔子" 🐰🐰🐰🐰🐰

**神奇发现**：
1, 1, 2, 3, 5, ...

"小朋友们发现规律了吗？"
"**每个月的兔子数 = 前两个月的兔子数加起来！**"

#### 1.2 多米诺骨牌类比（3分钟）

**老师拿出多米诺骨牌（或用手势）**：

"递推就像推倒多米诺骨牌——"
"第一块倒了（已知条件），第二块倒了（已知条件）..."
"每一块倒了，就会推倒下一块！"

"编程里也是一样："
"先知道 f(1) 和 f(2) —— 这就是前两块骨牌。"
"然后 f(3) = f(2) + f(1) —— 第三块被前两块推倒。"
"f(4) = f(3) + f(2) —— 第四块被推倒。"
"一直推下去..."

#### 1.3 身体游戏：斐波那契手势（2分钟）

**老师带全班做**：

1. 左手伸出1根手指："第1个月，1对兔子" ✌️（不对，是1）
2. 右手伸出1根手指："第2个月，1对兔子"
3. 双手合在一起，左手1右手1：一共2根手指："第3个月，2对！"
4. 再伸出2+1=3根："第4个月，3对！"
5. 再伸出3+2=5根："第5个月，5对！"
6. 再伸出5+3=8根："第6个月，8对！"

> **身体锚点**：双手交替比划斐波那契数列，边比边念"1,1,2,3,5,8..."

---

### 第二部分：知识点讲解（20分钟）

---

#### 2.1 什么是递推？（3分钟）

**定义**：

> **递推 = 从已知条件出发，根据规律一步步推出后面的结果**

**比喻**：
- 像爬楼梯——从第1阶开始，一步步往上爬
- 像多米诺骨牌——前面倒下了，后面跟着倒
- 像传话游戏——第一个人说给第二个人，第二个人传给第三个人...

**递推需要两个东西**：
1. **初始条件**（边界值）——从哪里开始？
2. **递推公式**（规律）——每一步怎么推？

#### 2.2 斐波那契数列详解（5分钟）

**数列**：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...

**规律**：每个数 = 前两个数的和

**公式**：
- f(1) = 1 （第1个数）
- f(2) = 1 （第2个数）
- f(n) = f(n-1) + f(n-2) （对于 n > 2）

**验算**：
- f(3) = f(2) + f(1) = 1 + 1 = 2 ✅
- f(4) = f(3) + f(2) = 2 + 1 = 3 ✅
- f(5) = f(4) + f(3) = 3 + 2 = 5 ✅
- f(6) = f(5) + f(4) = 5 + 3 = 8 ✅
- f(7) = f(6) + f(5) = 8 + 5 = 13 ✅

**提问**：f(8) = ? f(9) = ?
- f(8) = 13 + 8 = 21
- f(9) = 21 + 13 = 34

**扩展到前10个**：

| n | f(n) | 怎么算的？ |
|:-:|:----:|:----------:|
| 1 | 1 | 初始条件 |
| 2 | 1 | 初始条件 |
| 3 | 2 | 1+1 |
| 4 | 3 | 2+1 |
| 5 | 5 | 3+2 |
| 6 | 8 | 5+3 |
| 7 | 13 | 8+5 |
| 8 | 21 | 13+8 |
| 9 | 34 | 21+13 |
| 10 | 55 | 34+21 |

> **口诀**：
> "斐波那契兔子数列，前两个一后面加前"
> "第三开始都是和，前两个数加一起"

#### 2.3 代码实现——递推法（3分钟）

```python
def fibonacci(n):
    """
    计算斐波那契数列的第n项（递推法）
    口诀：a和b是前两个，循环加出后面的
    """
    if n <= 0:
        return 0
    if n == 1 or n == 2:
        return 1

    a, b = 1, 1  # a = f(1), b = f(2)
    for i in range(3, n + 1):
        c = a + b  # c = f(i) = f(i-1) + f(i-2)
        a, b = b, c  # 往前推：a变成b，b变成c
    return b

# 测试
for i in range(1, 11):
    print(f"f({i}) = {fibonacci(i)}")
```

**运行结果**：
```
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
```

**代码讲解**：
- `a, b = 1, 1`：前两个数已知（"前两块骨牌"）
- `c = a + b`：当前数 = 前两个数的和（"后面的被前面的推倒"）
- `a, b = b, c`：往前推（"骨牌倒下去，准备推下一个"）

#### 2.4 爬楼梯问题（5分钟）

**问题**："小明爬楼梯，每次可以走1步或2步。请问走到第n阶台阶，有多少种不同的走法？"

**举例**：
- n=1：只有1种走法（1步）→ f(1) = 1
- n=2：有2种走法（1+1 或 2）→ f(2) = 2
- n=3：有3种走法（1+1+1, 1+2, 2+1）→ f(3) = 3
- n=4：有5种走法 → f(4) = 5

**发现规律**：
- 要走到第n阶，最后一步要么走1步（从n-1阶来），要么走2步（从n-2阶来）
- 所以：f(n) = f(n-1) + f(n-2) —— 这就是斐波那契！

**不同之处**：初始条件不同
- 斐波那契：f(1)=1, f(2)=1
- 爬楼梯：f(1)=1, f(2)=2

**爬楼梯代码**：

```python
def climb_stairs(n):
    """爬楼梯：每次走1或2步"""
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2

    a, b = 1, 2  # a = f(1), b = f(2)
    for i in range(3, n + 1):
        c = a + b
        a, b = b, c
    return b

# 测试
for i in range(1, 11):
    print(f"{i}阶楼梯有 {climb_stairs(i)} 种走法")
```

**身体锚点**：让孩子做爬楼梯的动作
- "一步1阶" → 走一步
- "一步2阶" → 跨两步
- 边做边念："到第n阶，要么从n-1跨一步，要么从n-2跨两步"

#### 2.5 递推 vs 递归（2分钟）

| 对比项 | 递推 | 递归 |
|:------:|:----:|:----:|
| 方向 | 从前往后（1→n） | 从后往前（n→1） |
| 方式 | 循环 | 函数自己调自己 |
| 速度 | 快（没有重复计算） | 慢（有重复计算） |
| 代码 | 稍微长一点 | 代码短但慢 |
| 比喻 | 像往前走路 | 像往后倒车 |

**递归代码（做对比）**：

```python
def fibonacci_recursive(n):
    """递归版——慢！"""
    if n <= 0:
        return 0
    if n == 1 or n == 2:
        return 1
    return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)
```

**速度对比**：

```python
import time

# 递推法
start = time.time()
print(fibonacci(30))  # 瞬间出结果
print(f"递推耗时：{time.time() - start:.6f}秒")

# 递归法
start = time.time()
print(fibonacci_recursive(30))  # 慢很多！
print(f"递归耗时：{time.time() - start:.6f}秒")
```

**为什么递归慢？**
- 计算f(5)要算f(4)和f(3)
- 算f(4)又要算f(3)和f(2)
- 同一个f(3)被算了两次！
- 随着n增大，重复计算次数指数增长

> **口诀**：
> "递推往前推，递归往回拆"
> "递推快如飞，递归慢慢来"

---

### 第三部分：演示环节（10分钟）——turtle画斐波那契螺旋线

#### 3.1 斐波那契螺旋线原理（3分钟）

"斐波那契数列不仅是一个数列，它还能画出一条非常美丽的螺旋线！
这条螺旋线在大自然中随处可见——海螺壳、向日葵、台风..."

**画法**：
1. 先画一个1×1的正方形
2. 在旁边再画一个1×1的正方形
3. 接着画一个2×2的正方形
4. 再画一个3×3的正方形
5. 然后5×5、8×8、13×13...
6. 在每个正方形里画四分之一圆弧，连起来就是螺旋线！

#### 3.2 动画演示（5分钟）

**老师操作**：
1. 运行turtle斐波那契螺旋线代码
2. 屏幕上慢慢画出一个接一个的正方形
3. 每个正方形的边长是斐波那契数
4. 弧线连接起来，形成完美螺旋

**引导观察**：
- "看！第一个正方形边长1，第二个边长1，第三个边长2..."
- "正方形越画越大！"
- "弧线连起来成了螺旋线，好漂亮！"

#### 3.3 扩展展示（2分钟）

展示斐波那契数列在自然界的应用：
- 向日葵的螺旋排列（顺时针34条，逆时针55条）
- 海螺壳的螺旋
- 树枝的分叉
- 菠萝的鳞片排列

---

### 第四部分：实操环节（15分钟）

#### 4.1 任务1：运行斐波那契代码（3分钟）

1. 打开老师给的代码文件
2. 运行代码，看到斐波那契数列输出
3. 运行螺旋线代码，看到图形

#### 4.2 任务2：修改代码获取不同项数（3分钟）

```python
# 要求：打印斐波那契数列的前20项
for i in range(1, 21):
    print(f"第{i}个月：{fibonacci(i)}对兔子")

# 要求：打印前50项
for i in range(1, 51):
    print(f"f({i}) = {fibonacci(i)}")
```

**观察**：第50个月的兔子数量有多大？——巨大！

#### 4.3 任务3：完成爬楼梯代码（4分钟）

```python
def climb_stairs(n):
    """
    爬楼梯问题
    每次可以走1步或2步
    返回走到第n阶有多少种走法
    """
    if n == 1:
        return _____
    if n == 2:
        return _____

    a, b = _____, _____  # 初始值
    for i in range(_____, n + 1):
        c = _____ + _____
        _____, _____ = _____, _____
    return _____

# 测试
print(f"5阶楼梯：{climb_stairs(5)}种走法")  # 应该输出8
print(f"10阶楼梯：{climb_stairs(10)}种走法")  # 应该输出89
```

#### 4.4 任务4：新增台阶步数（5分钟）

**挑战**：
"如果小明每次可以走1步、2步或3步，求走到第n阶有多少种走法？"

**提示**：
- 到第n阶可以从n-1（走1步）、n-2（走2步）、n-3（走3步）来
- 公式：f(n) = f(n-1) + f(n-2) + f(n-3)
- 初始条件：f(1)=1, f(2)=2, f(3)=4

```python
def climb_stairs_3(n):
    """每次可以走1、2、3步"""
    if n == 1:
        return 1
    if n == 2:
        return 2
    if n == 3:
        return 4

    a, b, c = 1, 2, 4
    for i in range(4, n + 1):
        d = a + b + c
        a, b, c = b, c, d
    return c
```

---

### 第五部分：小测环节（5分钟）

#### 5.1 选择题（3题）

**第1题**：斐波那契数列的第7项是多少？（1,1,2,3,5,8,13...）
- A. 8
- B. 13 ✅
- C. 21
- D. 5

**第2题**：爬楼梯问题中，到第4阶有几种走法（每次1或2步）？
- A. 3
- B. 4
- C. 5 ✅
- D. 8

**第3题**：递推和递归相比，哪个更快？
- A. 递推 ✅（没有重复计算）
- B. 递归（代码短所以快）
- C. 一样快
- D. 看情况

#### 5.2 填空题（2题）

**第4题**：斐波那契数列的递推公式是：f(n) = ________ + ________

**第5题**：递推需要的两个条件是：①________ ②________

#### 5.3 思维题（1题）

**第6题**：前两个月是1和1，斐波那契数列就是1,1,2,3,5,8,13...
如果前两个月是2和1，数列会变成什么？写出前6个。

> **答案**：
> f(1)=2, f(2)=1
> f(3)=2+1=3, f(4)=3+1=4
> f(5)=4+3=7, f(6)=7+4=11
> 数列：2, 1, 3, 4, 7, 11

---

## 四、课后延伸

### 生活中的斐波那契
- 向日葵：种子排列成螺旋，顺时针34条，逆时针55条（斐波那契数列相邻项！）
- 海螺壳：完美的斐波那契螺旋线
- 人的手指：3节指骨、2节指骨（3,2,5,8...)
- 花瓣数量：百合3瓣，玫瑰5瓣，雏菊13瓣...

### 更多递推问题
- 汉诺塔问题
- 杨辉三角
- 上台阶（每次走1步或2步）

### 下节预告
"今天我们学了递推——从已知推出未知。下节课我们学**算法复杂度**——比一比，到底哪种算法跑得更快？"

---

## 五、板书设计

```
╔══════════════════════════════════════════════╗
║          递 推 算 法                          ║
║                                              ║
║  递推 = 已知→未知                            ║
║                                              ║
║  斐波那契数列：                               ║
║  f(1)=1, f(2)=1                              ║
║  f(n)=f(n-1)+f(n-2)                          ║
║                                              ║
║  1,1,2,3,5,8,13,21,34,55...                  ║
║                                              ║
║  爬楼梯：                                     ║
║  f(1)=1, f(2)=2                              ║
║  f(n)=f(n-1)+f(n-2)                          ║
║                                              ║
║  递推 vs 递归：                               ║
║  递推→快（无重复计算）                        ║
║  递归→慢（重复计算多）                        ║
║                                              ║
║  口诀：                                       ║
║  斐波那契兔子数列                             ║
║  前两个一后面加前                             ║
║  递推往前推，递归往回拆                       ║
║  递推快如飞，递归慢慢来                       ║
╚══════════════════════════════════════════════╝
```

---

## 六、课程反思

### 教师自评要点
1. 孩子是否理解"前两个数的和"这个规律？
2. 兔子故事是否引起兴趣？
3. 螺旋线动画是否震撼？
4. 爬楼梯问题是否理解？
5. 能否区分递推和递归？

### 常见问题应对
- **不理解递推公式**：用积木搭塔来解释——"叠第3块积木时，要放在第1块和第2块上面"
- **困惑爬楼梯和斐波那契的区别**：强调初始条件不同，但递推公式相同
- **递归vs递推分不清**：用"上楼梯"比喻——递推是从1楼往上爬，递归是从n楼往下走

### 教学调整建议
- 时间充裕：可以展示更多自然界的斐波那契实例（视频/图片）
- 时间紧张：跳过递归vs递推对比，直接讲递推
- 年龄偏小（7-8岁）：只讲斐波那契数列，不涉及爬楼梯泛化
- 数学兴趣浓：可以展示斐波那契的黄金比例（相邻项比值≈1.618）