728 lines
17 KiB
Markdown
728 lines
17 KiB
Markdown
# 4.1 自定义函数和递归
|
||
|
||
---
|
||
|
||
## 一、这一节到底学什么？
|
||
|
||
这一节不要求你一下子把函数和递归全背下来。
|
||
|
||
你只要先抓住下面 4 件事就够了：
|
||
|
||
1. 知道什么时候要把一段代码单独写成函数。
|
||
2. 会写最基础的自定义函数定义。
|
||
3. 能顺着流程图读懂“函数被调用时发生了什么”。
|
||
4. 初步看懂递归是怎样一层一层调用、再一层一层返回的。
|
||
|
||
整份讲义里，我们会尽量用能直接代数字的小例子来讲，不走太空的定义路线。
|
||
|
||
---
|
||
|
||
## 二、为什么要写函数，而不是一直往下写？
|
||
|
||
先看一种很常见的情况：
|
||
|
||
- 你要多次做同一件事。
|
||
- 这件事本身可以起一个名字。
|
||
- 把它拆出去以后，主程序会更清楚。
|
||
|
||
比如你要处理一张全班成绩表。
|
||
|
||
题目要求你完成下面这些事：
|
||
|
||
- 读入每个同学的语文、数学、英语成绩。
|
||
- 计算每个同学的总分。
|
||
- 计算每个同学的平均分。
|
||
- 判断每个同学是否及格。
|
||
- 最后输出全班总分前 3 名。
|
||
|
||
如果你完全不用函数，程序很可能会变成这样：
|
||
|
||
- 主程序里一大段是在算总分。
|
||
- 后面又来一大段是在算平均分。
|
||
- 再后面又来一大段是在判断是否及格。
|
||
- 如果输出前 3 名时还要反复比较、交换，主程序会更长。
|
||
|
||
这样写会有几个明显问题：
|
||
|
||
- 主程序会越来越像一团挤在一起的步骤，不容易看出主线。
|
||
- 同样的计算规则如果写了好几次，改错时很容易漏掉某一处。
|
||
- 过几天再回头看，你很难一下分清哪一段在“算分数”，哪一段在“判及格”，哪一段在“排前 3 名”。
|
||
|
||
这时如果把任务拆开：
|
||
|
||
- 写一个函数专门求总分。
|
||
- 写一个函数专门求平均分。
|
||
- 写一个函数专门判断是否及格。
|
||
|
||
主程序就会清楚很多。
|
||
|
||
所以你可以把“一段完成固定任务的代码”单独拿出来，给它起个名字，这就是函数。
|
||
|
||
你可以先把函数理解成：
|
||
|
||
> 一个能完成某项任务的小工具。
|
||
|
||
主程序需要它时，就“叫它来做事”。
|
||
|
||
---
|
||
|
||
## 三、最基础的函数长什么样？
|
||
|
||
最常见的写法是：
|
||
|
||
```cpp
|
||
返回值类型 函数名(参数列表)
|
||
{
|
||
函数体
|
||
}
|
||
```
|
||
|
||
先不用被名字吓住，直接把这 3 部分拆开看：
|
||
|
||
先配一个很具体的例子：
|
||
|
||
```cpp
|
||
int total_score(int chinese, int math, int english)
|
||
{
|
||
int sum = chinese + math + english;
|
||
return sum;
|
||
}
|
||
```
|
||
|
||
这个函数做的事非常明确：
|
||
|
||
- 给它语文、数学、英语 3 个分数。
|
||
- 它帮你算出总分。
|
||
- 最后把总分交回来。
|
||
|
||
### 1. 返回值类型
|
||
|
||
表示这个函数做完以后，要交回什么类型的结果。
|
||
|
||
例如：
|
||
|
||
- `int`：交回一个整数。
|
||
- `double`：交回一个小数。
|
||
- `bool`：交回真或假。
|
||
- `void`：不交回结果。
|
||
|
||
在刚才那个例子里：
|
||
|
||
- `total_score` 最后交回来的是总分。
|
||
- 总分通常是整数。
|
||
- 所以这里写 `int`。
|
||
|
||
### 2. 函数名
|
||
|
||
就是这个函数的名字。
|
||
|
||
名字最好能让人一眼看出用途，比如：
|
||
|
||
- `add`
|
||
- `is_even`
|
||
- `sum_to_n`
|
||
|
||
如果是给六年级同学自己写，名字能看懂比“高大上”更重要。
|
||
|
||
像：
|
||
|
||
- `total_score`
|
||
- `print_line`
|
||
- `sum_to_n`
|
||
|
||
都比随便写成 `f1`、`abc` 更容易读。
|
||
|
||
### 3. 参数列表
|
||
|
||
表示调用这个函数时，要给它哪些数据。
|
||
|
||
例如前面的成绩函数：
|
||
|
||
```cpp
|
||
int total_score(int chinese, int math, int english)
|
||
```
|
||
|
||
意思就是：
|
||
|
||
- 这个函数叫 `total_score`。
|
||
- 它需要 3 个整数，分别叫 `chinese`、`math`、`english`。
|
||
- 它最后会返回一个整数，也就是总分。
|
||
|
||
如果把真实数字代进去，比如：
|
||
|
||
- 语文 92 分
|
||
- 数学 87 分
|
||
- 英语 95 分
|
||
|
||
那么这个函数的任务就是算：
|
||
|
||
$$
|
||
92 + 87 + 95 = 274
|
||
$$
|
||
|
||
---
|
||
|
||
## 四、函数的意义：同一件事，只写一次
|
||
|
||
先看一个场景。
|
||
|
||
你需要算 3 个同学各自的总分：
|
||
|
||
- 小明：语文 92，数学 87，英语 95
|
||
- 小红：语文 78，数学 85，英语 80
|
||
- 小刚：语文 88，数学 90，英语 76
|
||
|
||
如果不用函数，主程序会这样写：
|
||
|
||
```cpp
|
||
int sum1 = 92 + 87 + 95; // 小明的总分
|
||
int sum2 = 78 + 85 + 80; // 小红的总分
|
||
int sum3 = 88 + 90 + 76; // 小刚的总分
|
||
```
|
||
|
||
如果有 30 个同学，就要写 30 行。
|
||
|
||
而且"加 3 个数"这件事，每次都要重复写一遍。
|
||
|
||
这时可以定义一个函数，把"怎么加"这件事单独写好：
|
||
|
||
```cpp
|
||
int total_score(int chinese, int math, int english)
|
||
{
|
||
int sum = chinese + math + english;
|
||
return sum;
|
||
}
|
||
```
|
||
|
||
然后在主函数里，每个同学用一行搞定：
|
||
|
||
```cpp
|
||
int sum1 = total_score(92, 87, 95); // 小明的总分，得到 274
|
||
int sum2 = total_score(78, 85, 80); // 小红的总分，得到 243
|
||
int sum3 = total_score(88, 90, 76); // 小刚的总分，得到 254
|
||
```
|
||
|
||
"怎么算总分"只定义了一次，却被叫了 3 次。
|
||
|
||
这就是函数最核心的意义：
|
||
|
||
> 把一件事的做法写一次，想用多少次就叫多少次。
|
||
|
||
### 用流程图看清楚"调用"发生了什么
|
||
|
||
下面这张图展示的是：主函数叫了 `total_score` 两次，每次都跳出去执行函数，结束后再回来继续。
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
subgraph M["主函数 main"]
|
||
A([开始]) --> B["准备小明的分数\n92, 87, 95"]
|
||
B --> C["调用①"]
|
||
C --> H["sum1 = 274"]
|
||
H --> I["准备小红的分数\n78, 85, 80"]
|
||
I --> J["调用②"]
|
||
J --> K["sum2 = 243"]
|
||
K --> L[/输出 sum1, sum2/]
|
||
L --> Z([结束])
|
||
end
|
||
|
||
subgraph F["函数 total_score（只写了一次）"]
|
||
D["收到参数"] --> E["sum = chinese + math + english"]
|
||
E --> G["return sum"]
|
||
end
|
||
|
||
C -- "传入 92,87,95" --> D
|
||
G -- "返回 274" --> H
|
||
J -- "传入 78,85,80" --> D
|
||
G -- "返回 243" --> K
|
||
```
|
||
|
||
注意流程图里的关键点：
|
||
|
||
- 每次调用，都会"跳进"函数那个框里执行。
|
||
- 函数执行完以后，再"跳回"主函数继续往下走。
|
||
- 函数本身的代码只写了一份，但被用了两次。
|
||
|
||
---
|
||
|
||
## 五、值传递到底是什么意思？
|
||
|
||
这是这一节最重要的基础概念。
|
||
|
||
看下面这组代码：
|
||
|
||
```cpp
|
||
int add_bonus(int score)
|
||
{
|
||
score = score + 10;
|
||
return score;
|
||
}
|
||
|
||
int main()
|
||
{
|
||
int math = 87;
|
||
int new_score = add_bonus(math);
|
||
}
|
||
```
|
||
|
||
很多同学第一眼会担心：
|
||
|
||
- 函数里把 `score` 改了，那外面的 `math` 会不会也变？
|
||
|
||
这一节里，答案是：
|
||
|
||
> 不会。
|
||
|
||
因为我们现在只讲值传递。
|
||
|
||
调用 `add(x, y)` 时，发生的是：
|
||
|
||
调用 `add_bonus(math)` 时，发生的是：
|
||
|
||
- 把 `math` 当前的值 87 交给函数里的 `score`。
|
||
- 函数内部拿到的是一份新的 87。
|
||
|
||
所以：
|
||
|
||
- `score` 和 `math` 不是同一个变量。
|
||
|
||
你可以把它理解成：
|
||
|
||
- 主程序把这个分数抄了一份给函数。
|
||
- 函数只是在自己的小房间里处理这份副本。
|
||
- 函数结束以后，主程序里的原变量不受影响。
|
||
|
||
### 用一组数据走一遍
|
||
|
||
当 `math = 87` 时：
|
||
|
||
- 进入函数时，`score = 87`。
|
||
- 执行 `score = score + 10` 后，`score = 97`。
|
||
- 返回 97。
|
||
|
||
但主函数里的：
|
||
|
||
- `math` 还是 87。
|
||
|
||
最后会变成：
|
||
|
||
- `math = 87`
|
||
- `new_score = 97`
|
||
|
||
也就是说：
|
||
|
||
- 原来的分数没被直接改掉。
|
||
- 只是函数帮你算出了“加 10 分以后”的新结果。
|
||
|
||
这一点一定要和“函数内部变量的变化”区分开。
|
||
|
||
---
|
||
|
||
## 六、函数调用时，流程图应该怎么看？
|
||
|
||
先看一个非常基础的例子：主函数调用 `total_score(chinese, math, english)`。
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
A([开始]) --> B["chinese = 92, math = 87, english = 95"]
|
||
B --> C["调用 total_score(chinese, math, english)"]
|
||
C --> D["把 92, 87, 95 交给函数里的 3 个参数"]
|
||
D --> E["sum = 92 + 87 + 95"]
|
||
E --> F["return 274"]
|
||
F --> G["ans 得到返回值"]
|
||
G --> H[/输出 ans/]
|
||
H --> I([结束])
|
||
```
|
||
|
||
这张图里最重要的是中间 3 步：
|
||
|
||
1. 调用函数。
|
||
2. 把实参的值交给形参。
|
||
3. 函数算完以后，把结果返回。
|
||
|
||
### 这里有两个名字要分清
|
||
|
||
- 实参：调用时真正传进去的东西，比如 `chinese`、`math`、`english`。
|
||
- 形参：函数定义里接收数据的变量，比如 `chinese`、`math`、`english` 这 3 个参数名。
|
||
|
||
你不需要死背这两个词，但一定要明白它们不是同一个层面的名字。
|
||
|
||
---
|
||
|
||
## 七、把“主函数”和“被调用函数”分开看，会更清楚
|
||
|
||
如果你总觉得函数调用时会乱，可以把它想成两块：
|
||
|
||
- 主函数负责“发任务”。
|
||
- 被调用函数负责“做任务”。
|
||
|
||
看这张图：
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
subgraph M[主函数 main]
|
||
A[准备 3 个分数] --> B["调用 total_score(...)"]
|
||
C[接住返回值 ans] --> D[/输出 ans/]
|
||
end
|
||
|
||
subgraph F[函数 total_score]
|
||
E[收到 3 个分数] --> F1[把 3 个分数加起来]
|
||
F1 --> G[返回总分]
|
||
end
|
||
|
||
B --> E
|
||
G --> C
|
||
```
|
||
|
||
这样看会更像真实过程：
|
||
|
||
- 主函数把任务送进去。
|
||
- `add` 做完再把结果送回来。
|
||
|
||
> 函数不是“贴在原地执行的一行代码”，而是一次完整的小过程。
|
||
|
||
---
|
||
|
||
## 八、什么时候用 `void` 函数？
|
||
|
||
不是所有函数都一定要“返回一个结果”。
|
||
|
||
比如下面这个函数：
|
||
|
||
```cpp
|
||
void print_line()
|
||
{
|
||
cout << "----------" << endl;
|
||
}
|
||
```
|
||
|
||
它的任务只是输出一行分隔线。
|
||
|
||
所以：
|
||
|
||
- 它做事。
|
||
- 但它不需要交回一个数。
|
||
|
||
这时就可以写成 `void`。
|
||
|
||
你可以把它理解成：
|
||
|
||
> `void` 函数负责“做动作”，不负责“交答案”。
|
||
|
||
如果把它放进主函数里：
|
||
|
||
```cpp
|
||
print_line();
|
||
cout << "欢迎来到成绩统计程序" << endl;
|
||
print_line();
|
||
```
|
||
|
||
它的作用就很直观：
|
||
|
||
- 不是算分数。
|
||
- 不是算答案。
|
||
- 只是帮你把输出排得更整齐。
|
||
|
||
---
|
||
|
||
## 九、递归到底是什么？
|
||
|
||
递归只有一句核心定义：
|
||
|
||
> 函数在自己的函数体里调用自己。
|
||
|
||
第一次看到这句话，很多同学会立刻觉得：
|
||
|
||
- “那不是会一直套下去吗？”
|
||
|
||
所以学递归时，最关键的不是先背代码，而是先抓住两件事：
|
||
|
||
1. 一定要有“停止条件”。
|
||
2. 每次递归都要朝着停止条件靠近。
|
||
|
||
如果没有停止条件，函数就会没完没了地继续调用。
|
||
|
||
如果虽然有停止条件，但每次都没有更接近它，那也一样会出问题。
|
||
|
||
---
|
||
|
||
## 十、先看一个最简单的递归函数
|
||
|
||
题目：求 1 到 n 的和。
|
||
|
||
我们把它写成：
|
||
|
||
```cpp
|
||
int sum_to_n(int n)
|
||
{
|
||
if (n == 1)
|
||
{
|
||
return 1;
|
||
}
|
||
return n + sum_to_n(n - 1);
|
||
}
|
||
```
|
||
|
||
这段代码可以读成：
|
||
|
||
- 如果 `n == 1`，那答案就是 1，直接返回。
|
||
- 如果 `n > 1`，那么
|
||
`1 + 2 + ... + n`
|
||
就等于
|
||
`n + (1 + 2 + ... + (n - 1))`。
|
||
|
||
所以它把原问题拆成了一个更小的问题：
|
||
|
||
- `sum_to_n(n)`
|
||
- 变成
|
||
- `n + sum_to_n(n - 1)`
|
||
|
||
这就是递归最常见的思路：
|
||
|
||
> 大问题，拆成一个同类但更小的问题。
|
||
|
||
你可以把它想成一堆叠起来的小卡片：
|
||
|
||
- 要算前 4 张卡片上的数字和。
|
||
- 可以先拿最上面这一张 4。
|
||
- 剩下的问题就变成“前 3 张卡片的和是多少”。
|
||
|
||
这样就从“4 张”慢慢变成“3 张”“2 张”“1 张”。
|
||
|
||
---
|
||
|
||
## 十一、递归流程图怎么画？
|
||
|
||
先看结构图：
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
A(["进入 sum_to_n(n)"]) --> B{n == 1 吗？}
|
||
B -- 是 --> C[return 1]
|
||
B -- 否 --> D["计算 sum_to_n(n - 1)"]
|
||
D --> E[返回 n + 子问题结果]
|
||
C --> F([结束本层调用])
|
||
E --> F
|
||
```
|
||
|
||
这张图里，你必须抓住两条路：
|
||
|
||
- 一条是“直接结束”的路，也就是停止条件。
|
||
- 一条是“继续缩小问题”的路，也就是递归调用。
|
||
|
||
没有前者，停不下来。
|
||
|
||
没有后者，就不是递归。
|
||
|
||
---
|
||
|
||
## 十二、拿 `sum_to_n(4)` 手推一遍，最重要
|
||
|
||
只看代码，很多同学会晕。
|
||
|
||
这时最稳的方法就是：
|
||
|
||
> 拿一个很小的数，自己顺着调用过程走一遍。
|
||
|
||
### 第一步：往下调用
|
||
|
||
```text
|
||
sum_to_n(4)
|
||
= 4 + sum_to_n(3)
|
||
|
||
sum_to_n(3)
|
||
= 3 + sum_to_n(2)
|
||
|
||
sum_to_n(2)
|
||
= 2 + sum_to_n(1)
|
||
|
||
sum_to_n(1)
|
||
= 1
|
||
```
|
||
|
||
看到这里，终于碰到了停止条件。
|
||
|
||
### 第二步：往回返回
|
||
|
||
```text
|
||
sum_to_n(1) = 1
|
||
sum_to_n(2) = 2 + 1 = 3
|
||
sum_to_n(3) = 3 + 3 = 6
|
||
sum_to_n(4) = 4 + 6 = 10
|
||
```
|
||
|
||
所以最后答案是 10。
|
||
|
||
### 再用表格看一遍
|
||
|
||
| 这一层在算谁？ | 它先等谁？ | 等到以后自己返回多少？ |
|
||
|:---:|:---:|:---:|
|
||
| `sum_to_n(4)` | 等 `sum_to_n(3)` | `4 + 6 = 10` |
|
||
| `sum_to_n(3)` | 等 `sum_to_n(2)` | `3 + 3 = 6` |
|
||
| `sum_to_n(2)` | 等 `sum_to_n(1)` | `2 + 1 = 3` |
|
||
| `sum_to_n(1)` | 不用再等 | `1` |
|
||
|
||
这张表很重要，因为它把“先等谁、再返回多少”写得很清楚。
|
||
|
||
---
|
||
|
||
## 十三、递归最容易绕晕的地方，不在“往下”，而在“往回”
|
||
|
||
很多同学能接受：
|
||
|
||
- `sum_to_n(4)` 去叫 `sum_to_n(3)`。
|
||
- `sum_to_n(3)` 再去叫 `sum_to_n(2)`。
|
||
|
||
但一到返回时就乱了。
|
||
|
||
原因通常是没有意识到：
|
||
|
||
> 每一层函数调用，都在等自己的“下一层”先把结果交回来。
|
||
|
||
也就是说：
|
||
|
||
- `sum_to_n(4)` 不能立刻算完。
|
||
- 它必须先等 `sum_to_n(3)` 返回。
|
||
- `sum_to_n(3)` 又得先等 `sum_to_n(2)`。
|
||
- 一直等到最小那层先返回。
|
||
|
||
所以递归过程常常像两段：
|
||
|
||
1. 一层一层往下走。
|
||
2. 一层一层往上交答案。
|
||
|
||
---
|
||
|
||
## 十四、把递归看成“排队等结果”，会更好懂
|
||
|
||
再看一张图：
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
A["sum_to_n(4)"] --> B["等待 sum_to_n(3)"]
|
||
B --> C["等待 sum_to_n(2)"]
|
||
C --> D["等待 sum_to_n(1)"]
|
||
D --> E["sum_to_n(1) 返回 1"]
|
||
E --> F["sum_to_n(2) 返回 3"]
|
||
F --> G["sum_to_n(3) 返回 6"]
|
||
G --> H["sum_to_n(4) 返回 10"]
|
||
```
|
||
|
||
这张图要表达的重点不是代码细节，而是“顺序”：
|
||
|
||
- 先不断往下等。
|
||
- 再从最底层开始往回交结果。
|
||
|
||
你甚至可以把它读成下面这几句话：
|
||
|
||
- 4 这一层先别急，先去问 3。
|
||
- 3 这一层也先别急，先去问 2。
|
||
- 2 这一层再去问 1。
|
||
- 1 最简单，直接回答：我是 1。
|
||
- 然后答案一层一层往回传。
|
||
|
||
如果你能把这张图说顺，说明你已经抓住递归最核心的运行过程了。
|
||
|
||
---
|
||
|
||
## 十五、值传递放到递归里，还是一样的
|
||
|
||
递归虽然看起来更复杂，但参数传递规则没有变。
|
||
|
||
例如：
|
||
|
||
- 调用 `sum_to_n(4)` 时，这一层的 `n` 是 4。
|
||
- 它再调用 `sum_to_n(3)` 时，下一层会有一个新的 `n`，值是 3。
|
||
- 再下一层调用 `sum_to_n(2)` 时，又会有一个新的 `n`，值是 2。
|
||
|
||
所以：
|
||
|
||
- 每一层都有自己的 `n`。
|
||
- 它们不是同一个变量。
|
||
- 只是名字都叫 `n` 而已。
|
||
|
||
这也是值传递的一部分：
|
||
|
||
> 每次调用，都会得到这一层自己的那份参数值。
|
||
|
||
---
|
||
|
||
## 十六、写递归时，先问自己这两个问题
|
||
|
||
在真正动手写递归前，最好先问：
|
||
|
||
### 1. 什么时候停？
|
||
|
||
也就是停止条件是什么。
|
||
|
||
例如：
|
||
|
||
- `n == 1` 时停。
|
||
- `n == 0` 时停。
|
||
|
||
### 2. 怎么把问题变小？
|
||
|
||
也就是下一次调用时，参数怎么变化。
|
||
|
||
例如：
|
||
|
||
- `n - 1`
|
||
- `n / 2`
|
||
|
||
如果这两个问题答不出来，递归代码通常也写不稳。
|
||
|
||
---
|
||
|
||
## 十七、最常见的错误
|
||
|
||
下面这些错非常常见：
|
||
|
||
1. 写了递归调用，却没有停止条件。
|
||
2. 虽然写了停止条件，但永远到不了它。
|
||
3. 只会往下套，不会分析怎么往回返回。
|
||
4. 把“这一层的参数”和“下一层的参数”混成同一个东西。
|
||
5. 以为函数里的参数改了，主函数里的变量也会跟着改。
|
||
|
||
第 5 条在这一节里尤其要避免，因为本节只讲值传递。
|
||
|
||
---
|
||
|
||
## 十八、这一节最该记住的几句话
|
||
|
||
1. 函数就是把一段固定任务单独拿出来，起个名字反复用。
|
||
2. 最基础的函数定义要看清：返回值类型、函数名、参数列表。
|
||
3. 调用函数时，主程序是“发任务”，函数是“做任务”。
|
||
4. 本节只讲值传递，所以函数拿到的是一份新的值，不会直接改掉外面的原变量。
|
||
5. 递归就是函数调用自己。
|
||
6. 递归必须同时具备两件事：停止条件、缩小问题。
|
||
7. 读递归最稳的方法，是拿小数据手推，先看往下调用，再看往回返回。
|
||
|
||
---
|
||
|
||
## 十九、课堂练习
|
||
|
||
### 练习 1
|
||
|
||
写一个函数 `int square(int x)`，返回 `x * x`。
|
||
|
||
要求：
|
||
|
||
- 先说清楚参数是什么。
|
||
- 再说清楚返回值是什么。
|
||
|
||
### 练习 2
|
||
|
||
主函数中有 `a = 6`，调用 `triple(a)`，其中函数内部把形参乘以 3。
|
||
|
||
问题：
|
||
|
||
- 函数返回什么？
|
||
- 主函数里的 `a` 会不会变？
|
||
|
||
### 练习 3
|
||
|
||
把 `sum_to_n(5)` 的递归调用过程手写出来，写清楚：
|
||
|
||
- 往下调用到了哪一层。
|
||
- 往回返回时每层结果是多少。
|
||
|
||
如果这 3 题都能自己说顺，这一节就算真正入门了。 |