---
marp: true
theme: kurzus
paginate: true
footer: 数据结构 · 第 12 周 · 递归
---

<!-- _class: cim -->
<!-- _paginate: false -->
<!-- _footer: "" -->

# 数据结构

## 第 12 周 – 递归：把问题归结为它自身的较小实例

Koczka Ferenc 博士 · 埃斯特哈齐·卡罗伊大学 · 2026

---

## 复习

- <strong>调用栈</strong>（第 7 周）：每次函数调用都把一个栈帧压入栈中，返回时弹出
- <strong>链表：</strong>一个结点 + 链表的其余部分（它也是一个链表！）
- <strong>二分查找：</strong>把问题缩小一半，然后用同样的方法继续

### 今天的问题

- 什么是递归？它在计算机中是怎样工作的？
- 怎样写出正确的递归函数？
- 什么时候适合用递归，什么时候递归很危险？

<!--
时间安排：概念、阶乘 20' · 工作原理、调用栈 15' · 斐波那契、效率 20' · 例子 25' · 递归与迭代 10'
旧课程第 10 周的内容（Factorial、Fibonacci、AddNumbers），有所扩充。
-->

---

<!-- _class: kicsi -->

## 什么是递归？

<strong>递归：</strong>函数在问题的<strong>较小</strong>实例上<strong>调用自身</strong>。

每个递归函数都由两部分组成：

1. <strong>基本情况（递归出口）：</strong>最简单的情况，直接求解 – 递归在这里<strong>停止</strong>
2. <strong>递归情况：</strong>把问题归结为同一问题的一个<strong>较小</strong>实例

<div class="doboz">

<strong>阶乘：</strong>n! = 1 · 2 · … · n

0! = 1 &nbsp;&nbsp;&nbsp;<em>（基本情况）</em>
n! = n · (n − 1)! &nbsp;&nbsp;&nbsp;<em>（递归情况）</em>

</div>

<div class="doboz tipp">

在数学中与之对应的是<strong>数学归纳法</strong>：如果基本情况成立，并且由较小的情况能推出较大的情况，那么对所有情况都成立。

</div>

---

<!-- _class: kicsi -->

## 阶乘

<div class="ket-hasab">
<div>

<span class="cimke pszeudo">伪代码</span>

```text
Function Fact(n)
  If n ≤ 1 then
    Return 1                  // 基本情况
  else
    Return n · Fact(n − 1)    // 递归情况
  End if
End function
```

<span class="cimke java">Java</span>

```java
static long fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}
```

</div>
<div>

<span class="cimke go">Go</span>

```go
func fact(n int) int64 {
    if n <= 1 {
        return 1
    }
    return int64(n) * fact(n-1)
}
```

<strong>程序的输出</strong>（`Factorial`）：

```text
fact(4) called
  fact(3) called
    fact(2) called
      fact(1) called
      fact(1) = 1
    fact(2) = 2
  fact(3) = 6
fact(4) = 24
```

</div>
</div>

---

## 它是怎样工作的？调用栈

![w:1000](kepek/h12_faktorialis.svg)

- 每次调用都有自己的<strong>栈帧</strong>：自己的参数 <em>n</em>、自己的返回地址
- 乘法只在<strong>返回的过程中</strong>（倒着）执行
- 空间：<strong>O(n)</strong> – 栈中有 n 个栈帧

---

## 正确的递归 – 三条规则

1. <strong>有基本情况</strong>，它不用递归就能给出结果
2. 每次递归调用都<strong>更接近</strong>基本情况（更小的 n、更短的链表、更小的范围）
3. <strong>相信递归：</strong>假定对较小的问题调用会返回正确的结果，只需考虑怎样由它构造出较大问题的解

<div class="doboz figyelem">

没有基本情况，或者不向它靠近：<strong>无穷递归</strong> → 栈被填满
Java:`StackOverflowError`（大约 10 000–30 000 次调用之后） · Go：栈会增长，但到 1 GB 时崩溃

</div>

---

## 递归的种类

| 种类 | 含义 | 例子 |
|---|---|---|
| <strong>直接递归</strong> | f 调用自身 | 阶乘 |
| <strong>间接递归</strong> | f 调用 g,g 调用 f | even(n) → odd(n − 1) |
| <strong>线性递归</strong> | 一次递归调用 | 阶乘、求和、链表长度 |
| <strong>树形（多重）递归</strong> | 多次递归调用 | 斐波那契、汉诺塔、树的遍历 |
| <strong>尾递归</strong> | 递归调用是最后一个操作 | `gcd(b, a mod b)` |

<span class="halvany">尾递归可以机械地改写成循环（有些编译器会自动这样做 – Java 和 Go 不会）。</span>

---

<!-- _class: fejezet -->

# 效率：斐波那契的例子

---

## 斐波那契数

<strong>定义：</strong>F(0) = 0,F(1) = 1,F(n) = F(n − 1) + F(n − 2)
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

<div class="ket-hasab">
<div>

```text
Function Fib(n)
  If n < 2 then
    Return n
  else
    Return Fib(n − 1) + Fib(n − 2)
  End if
End function
```

</div>
<div>

```java
static long fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}
```

简单，而且完全遵循定义 – 但是…

</div>
</div>

---

## 朴素斐波那契的调用树

![w:900](kepek/h12_fib_fa.svg)

---

## 实测结果

| n | fib(n) | 朴素调用次数 | 记忆化 | 时间（朴素） |
|---|---|---|---|---|
| 10 | 55 | 177 | 19 | 0.0 ms |
| 20 | 6 765 | 21 891 | 39 | 0.1 ms |
| 30 | 832 040 | 2 692 537 | 59 | 2.6 ms |
| 40 | 102 334 155 | <strong>331 160 281</strong> | 79 | <strong>320 ms</strong> |

- 朴素版本是<strong>指数级</strong>的：O(φⁿ) ≈ O(1.618ⁿ) – n = 50 时要几分钟，n = 100 时要几百万年
- <strong>记忆化：</strong>把已经算出的值存放在<strong>哈希表</strong>中 → <strong>O(n)</strong>
- <strong>迭代：</strong>用两个变量，O(n) 时间，<strong>O(1)</strong> 空间

---

<!-- _class: kicsi -->

## 改进的版本

<div class="ket-hasab">
<div>

<span class="cimke java">记忆化（Java）</span>

```java
static HashMap<Integer, Long> memo = new HashMap<>();

static long fibMemo(int n) {
    if (n < 2) return n;
    Long cached = memo.get(n);
    if (cached != null) return cached;
    long r = fibMemo(n - 1) + fibMemo(n - 2);
    memo.put(n, r);
    return r;
}
```

</div>
<div>

<span class="cimke go">迭代（Go）</span>

```go
func fibIter(n int) int {
    a, b := 0, 1
    for i := 0; i < n; i++ {
        a, b = b, a+b
    }
    return a
}
```

</div>
</div>

<div class="doboz tipp">

记忆化是<strong>动态规划</strong>的基本思想：每个子问题只求解一次。

</div>

---

<!-- _class: fejezet -->

# 经典例子

---

<!-- _class: kicsi -->

## 递归思维：“第一个 + 其余部分”

<div class="ket-hasab">
<div>

<strong>数组求和：</strong>第一个元素 + 其余部分的和

```java
static int sum(int[] a, int from) {
    if (from == a.length) return 0;
    return a[from] + sum(a, from + 1);
}
```

<strong>字符串逆序：</strong>其余部分逆序 + 第一个字符

```java
static String reverse(String s) {
    if (s.isEmpty()) return s;
    return reverse(s.substring(1)) + s.charAt(0);
}
```

</div>
<div>

<strong>回文：</strong>第一个 = 最后一个，并且中间部分也是回文

```go
func isPalindrome(r []rune) bool {
    if len(r) < 2 {
        return true
    }
    return r[0] == r[len(r)-1] &&
        isPalindrome(r[1:len(r)-1])
}
```

<strong>链表长度：</strong>1 + 其余部分的长度

```go
func length(p *Node) int {
    if p == nil {
        return 0
    }
    return 1 + length(p.Next)
}
```

</div>
</div>

---

## 快速幂 – 分治

计算 x¹³，而不用 12 次乘法：

- x¹³ = (x⁶)² · x &nbsp;&nbsp; x⁶ = (x³)² &nbsp;&nbsp; x³ = (x¹)² · x &nbsp;&nbsp; → 总共 <strong>5</strong> 次乘法

```text
Function Power(x, n)
  If n = 0 then Return 1
  half ← Power(x, n div 2)
  If n mod 2 = 0 then Return half · half
  else Return half · half · x
End function
```

- 每次调用都把 n <strong>减半</strong> → <strong>O(log n)</strong> 次调用（和二分查找一样）
- 同样的模式：<strong>递归的二分查找</strong>、归并排序、快速排序（第 13 周）

---

## 汉诺塔

![w:900](kepek/h12_hanoi.svg)

<div class="ket-hasab">
<div>

```text
Procedure Hanoi(n, from, to, via)
  If n > 0 then
    Hanoi(n − 1, from, via, to)
    Move(from, to)
    Hanoi(n − 1, via, to, from)
  End if
End procedure
```

</div>
<div>

- 移动次数：<strong>2ⁿ − 1</strong> → O(2ⁿ)
- n = 3:7 次 · n = 20:1 048 575 次
- n = 64：每秒移动一次，大约需要 <strong>5850 亿年</strong>

用迭代来写要难得多！

</div>
</div>

---

## 回溯：全排列

`A, B, C` 的所有排列：ABC、ACB、BAC、BCA、CAB、CBA

```java
static void permute(List<Character> prefix, boolean[] used, char[] items) {
    if (prefix.size() == items.length) { print(prefix); return; }  // 基本情况
    for (int i = 0; i < items.length; i++) {
        if (used[i]) continue;
        used[i] = true;  prefix.add(items[i]);         // 做出选择
        permute(prefix, used, items);                  // 递归处理其余部分
        prefix.remove(prefix.size() - 1);  used[i] = false;   // 回溯
    }
}
```

- n 个元素有 <strong>n!</strong> 个排列 – O(n · n!)
- 同样的模式：数独、迷宫、八皇后、子集

---

## 递归还是迭代？

| | 递归 | 迭代 |
|---|---|---|
| 代码 | 简短，遵循定义 | 通常更长 |
| 空间 | 栈中 O（深度） | 通常 O(1) |
| 速度 | 有函数调用的开销 | 更快 |
| 危险 | 栈溢出 | – |
| 自然的应用 | <strong>树</strong>、分治、回溯 | 简单循环、链表 |

<div class="doboz">

每个递归都可以改写成迭代（必要时使用自己的<strong>栈</strong>），反之亦然。
<strong>经验法则：</strong>如果问题是<strong>树形</strong>的（多次递归调用），递归要简单得多；如果是线性的，最好写成循环。

</div>

---

## 小结

- <strong>递归：</strong>函数在一个<strong>较小</strong>的问题上调用自身
- 需要：<strong>基本情况</strong> + 调用要<strong>接近</strong>基本情况
- 工作原理：<strong>调用栈</strong> – 每次调用都有自己的栈帧，空间 O（深度）
- <strong>树形递归</strong>很容易变成指数级（朴素斐波那契） → <strong>记忆化</strong>或迭代
- 经典例子：阶乘、快速幂（O(log n)）、汉诺塔（2ⁿ − 1）、全排列
- 是<strong>树</strong>（第 14–15 周）和快速排序算法（第 13 周）的自然工具

<strong>下周：</strong>排序 II – 归并排序和快速排序。

---

## 复习题

1. 调用 `Fact(5)` 时调用栈的最大深度是多少？
2. 有什么错误？`Function F(n): Return n + F(n − 1)`
3. 计算 `Fib(5)` 时，朴素的 `Fib` 函数被调用了多少次？
4. 输出什么？`Procedure P(n): If n > 0 then P(n − 1); Print(n)` – `P(3)`
5. 如果把 `Print(n)` 移到 `P(n − 1)` 之前呢？
6. 汉诺塔中移动 5 个盘子需要多少步？

<!--
答案：1. 5(Fact(5), Fact(4), …, Fact(1))
2. 没有基本情况 → 无穷递归（StackOverflowError）。
3. 15  4. 1 2 3  5. 3 2 1  6. 2^5 − 1 = 31
-->

---

<!-- _class: fejezet -->
<!-- _footer: "" -->

# 实践课

---

<!-- _class: gyak -->

## 示例程序

| 程序 | Java | Go | 演示内容 |
|---|---|---|---|
| 阶乘 | `Factorial.java` | `w12/factorial` | 缩进打印调用过程、溢出 |
| 斐波那契 | `Fibonacci.java` | `w12/fibonacci` | 调用次数、记忆化、时间 |
| 例子 | `RecursionExamples.java` | `w12/examples` | 求和、乘方、逆序、回文、二分查找 |
| 汉诺塔 | `Hanoi.java` | `w12/hanoi` | 打印移动步骤，2ⁿ − 1 |
| 栈深度 | `StackDepth.java` | `w12/stackdepth` | Java 中的 `StackOverflowError`,Go 中增长的栈 |
| 全排列 | `Permutations.java` | `w12/permutations` | 回溯 |

---

<!-- _class: gyak -->

## 练习

用<strong>递归</strong>（不用循环）求解！

1. <strong>数字和：</strong>`2026 → 10`
2. <strong>二进制表示：</strong>`50 → "110010"`（与第 7 周的栈比较！）
3. <strong>最大值：</strong>数组中最大的元素
4. <strong>计数：</strong><em>x</em> 在数组中出现了多少次？
5. <strong>反向输出链表：</strong>按相反的顺序输出链表的元素！
6. 递归求<strong>链表长度</strong>
7. <strong>二项式系数：</strong>C(n, k) = C(n − 1, k − 1) + C(n − 1, k) – 为什么 n 较大时很慢？

参考答案：`Exercises12.java`、`w12/exercises`

---

<!-- _class: gyak -->

## 课后作业

1. 用<strong>记忆化</strong>实现二项式系数，并测量计算 C(30, 15) 时的加速效果！
2. 编写递归函数，输出一个集合的<strong>所有子集</strong>！共有多少个？
3. <strong>迷宫：</strong>在字符地图上（`#` 表示墙，`.` 表示路），用回溯法找出从左上角到右下角的路径！
4. 用自己的栈把汉诺塔的解法改写成<strong>迭代</strong>形式！（提示：把“还需要完成的任务”压入栈中。）

<!--
解题思路：
1. memo[n][k] 数组或 map;C(30,15) 朴素约 3·10^8 次调用，记忆化约 225 次。
2. 每个元素两个分支：包含 / 不包含 → 2^n 个子集。
3. Solve(x, y)：如果是墙或已经走过 → false；如果是终点 → true；做标记；尝试 4 个方向；如果都不行 → 撤销标记。
4. 栈元素：（n, from, to, via，阶段）；或者把三个子任务按相反的顺序压入栈中。
-->