Tips. 本文的所有代码请各位编译并运行后观察运行结果。

无返回值函数的定义

在之前的学习中，我们知道了 C++ 的程序入口是 main()，即主函数，那么我们除了 main() 函数外是否可以定义其他的函数呢？答案是肯定的。

我们先来看一段定义函数的格式。

返回值类型 函数名(参数类型1 参数1, 参数类型2 参数2, ...) {
    函数体
}

首先，我们介绍一下函数体。函数体是调用函数所执行的语句。注意，与我们之前讲过的 if 等不同，此处大括号不可以省略。

返回值是调用函数后执行完所有语句返回的值（也可以理解为这整个函数代表的值的数据类型），如果没有返回值，必须要写 void（也就是英文中的空白）。

参数是函数要进行操作的东西，可以在函数体中使用。

我们先来看个例子：

void print() {
    cout << "Hello, world!" << endl;
}

调用一次这个函数可以输出一次 Hello, world!。

如果我们写一个这样的程序：

#include <iostream>
using namespace std;

void print() {
    cout << "Hello, world!" << endl;
}

int main() {
    int n = 10;
    for (int i = 1; i <= n; ++i) print();
    return 0;
}

请自行编译并运行这份代码，查看输出结果。可以发现，程序输出了 $10$ 行 $\texttt{Hello, world}!$。

但是，如果我们想判断改变输出的字符串应该怎么办呢？

我们重新定义 print 函数。

#include <iostream>
using namespace std;

void print(string text) {
    cout << text << endl;
}

int main() {
    int n = 3;
    for (int i = 1; i <= n; ++i) print("Hello, world!");
    for (int i = 1; i <= n; ++i) print("Fuck CCF.");
    return 0;
}

请同学们编译这段代码，查看输出结果。可以发现，程序输出了 $3$ 行 $\texttt{Hello, world!}$ 和 $3$ 行 $\texttt{Fuck CCF}$。

这样一来，我们的函数通过传参（传递参数）就有了灵活性。

一般函数的定义

我们继续拓展深度。

int add(int a, int b) {
    return a + b;
}

这个函数是一个具有 int 函数的返回值，它返回了 $a + b$ 的值。

我们可以测试一下：

#include <iostream>
using namespace std;

int add(int a, int b) {
    return a + b;
}

int main() {
    int a = 10, b = 20;
    cout << add(a, b) << endl;
    return 0;
}

得到了结果：

30

这样，我们的函数就不必更改函数的内容，而只更改参数就好了。

观察下面这段代码，我们有这样一段函数：

void add(int a, int k) {
    a += k;
}

我们知道 a += k 的含义，于是我们兴高采烈地运行这段代码：

int main() {
    int a = 1;
    add(a, 1);
    cout << a << endl;
}

运行后得到了如下结果：

1

可以发现，函数并没有实现 a += 1 这一个操作。我们来究其根本。

传参的一个重要特性是：大多数传参方式在对参数进行操作时，事实上，不会真正改变参数的值。

但是有两种方式例外（其实还有一些没什么必要的方式，这里不再赘述）：

• 传用数组。
• 传引用类型的参数。

我们说一下引用类型的参数的写法：

void add(int &a, int k) {
    a += k;
}

我们将 add 函数换成这样的形式再运行一遍，得到如下结果：

2

结果和我们预想的相同了。

函数的返回

在循环中，我们知道我们可以使用 break 终止循环。如果我们想终止函数运行，应该怎么办呢？

我们可以使用 return 来结束一个循环。

void print(){
    cout << "before" << endl;
    return;
    cout << "after" << endl;
}

运行后，我们发现，程序只输出了 before。

在有返回值的函数中，也可以使用 return 语句中止函数，只需要在 return 后加上要返回的值即可：

bool judge(int k) {
    for (int i = 1; i <= 10; ++i)
        if (i == k) return true;
    return false;
}

显然地，这个函数的作用是判断传入的 $k$ 是否在 $[1 , 10]$ 的范围内，如果是则返回 true，否则返回 false。

变量的作用域

$n$（$n \le 100$）名同学参加歌唱比赛，并接受 $m$（$m \le 20$）名评委的评分，评分范围是 $0 \sim 10$ 分。每名同学的得分就是这些评委给分中去掉一个最高分，去掉一个最低分，剩下 $m-2$ 个评分的平均数。

求得分最高的同学分数是多少。

本题的思路很简单，抽出每名同学得分中的最大、最小评分，去掉后求平均值，然后再取最大值。

观察如下代码：

#include <iostream>
using namespace std;

int s[25], n, m, maxsum;

void stat(int a[], int m) {
    int maxscore = 0, minscore = 10, sum = 0;
    for (int i = 1; i <= m; ++i) {
        maxscore = max(maxscore, a[i]);
        minscore = min(minscore, a[i]);
        sum += a[i];
    } maxsum = max(maxsum, sum - maxscore - minscore);  // 计算评分总和，并更新最大值
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) cin >> s[j];
        stat(s, m);
    } cout << double(maxsum) / (m - 2) << endl;  // 最后再计算平均值
    return 0;
}

在这份代码中，我们使用了一个 stat() 函数处理一个给定的数组评分信息， 然后更新最高分的同学分数。

本例的 stat() 函数中，接收的参数列表中的 int a[] 是指可以接收一个 int 类型的数组名。在函数中单个变量是可以传递实际参数的，但是传递数组名作为参数可不会把数组的所有信息当作实际参数传入函数，而只是传递数组在内存中的地址。

就像在操作厨房自制机器时，可以把一个土豆、一个番茄放入机器中，但是如果有一排碗的食材，则只能告诉机器那一排碗的第一个碗在什么位置，让机器自己去指定位置找食材。

因此在函数 stat() 中，数组 a[] 其实就是全局变量 s[] 的别名，如果在函数中改变 a[] 中的一项值，s[] 也会相应地改变。

和全局变量对应的，在 stat() 函数中的变量 $m$、$maxscore$、$sum$ 等，都是在函数中定义的、在机器内部的变量，因此被称为局部变量。

在函数中无论怎么改变这些局部变量，都不会影响到函数外面（函数里的 $m$ 变量和外面的 $m$ 没有关系了，也就是说函数外面的变量 $m$ 被屏蔽了）。也就是说，这些局部变量只能在这个函数中作用，因此这个函数是这些变量的作用域。

类似地，我们常在 for 循环中定义的循环变量 $i$，它的作用域是整个循环，在循环之外无法调用这个变量。

在程序设计竞赛中，建议大数组（超过 $1000$）作为全局变量定义。一是方便程序所有地方都可以访问到这个数组，二是有些评测环境栈空间（就是每个函数被分配到的内存空间）有限，可能会造成栈溢出。不过现在大多数比赛的评测环境下，栈空间可以达到要求的内存上限了。

函数递归

函数其实还可以调用它本身，也就是「递归」。

值得注意的是，高中数学不区分递归和递推，但这在代码上有本质的区别，请注意区分。

求 $n!$（$n \le 12$），也就是 $1 \times 2 \times 3 \times \cdots \times n$。请注意，你在本题中不被允许使用循环语句。

计算阶乘很简单，但如果不允许使用循环语句，那么得想想别的办法。

假设 $f(n)$ 代表 $n$ 的阶乘，那么阶乘还有另外一种表示方法：$f(1)=1$，$f(n) = n \times f(n-1)$。当想求 f(n) 时，就可以调用 f(n-1) 进而调用 f(n-2)……直到调用 f(1) 为止。

像这样将规模大的问题转化成形式相同，但是规模更小的问题，就称为子问题。代码如下:

#include <iostream>
using namespace std;

int n;

int f(int n) {
    if (n == 1) return 1;  // 如果 n 为 1，则返回 1
    return n * f(n - 1);  // 否则计算 (n - 1)!，并将其乘上 n 返回，得到 n!
}

int main() {
    cin >> n;
    cout << f(n) << endl;
    return 0;
}

一个函数不仅可以调用其他的函数，甚至还能调用自己，这种自己调用自己被称为递归。

根据题意和上述思路，可以写出上面的递归做法。假设输入是 $3$，那么函数执行的步骤如下图所示：

程序计算步骤如下：

1. 进入 main() 函数，收集到了参数 $3$，传递参数给 f() 函数，也就是调用 f(3)。
2. 进入第 $1$ 层 f() 函数，需要接收一个 int 类型的变量 $n$。传递进来了 $3$，所以这里的 $n=3$。现在需要知道 $f(3-1)$ 的值。因此传递参数 $2$ 给 f() 函数，调用 f(2)。
3. 进入第 $2$ 层 f() 函数（别忘了第一层 f() 函数还没结束，在等待答案呢），这里的 $n=2$。现在又要知道 f(2-1) 的值，因此再次传递参数 $1$ 给 f() 函数，调用 f(1)。
4. 进入第 $3$ 层 f() 函数。发现当 $n$ 等于 $1$ 时就返回 $1$，返回到第 $2$ 层 f() 函数，得到 f(2-1) 的值就是 $1$，继续进行运算。
5. 返回结果$2 \times 1=2$，返回到第 $1$ 层 f() 函数，得到 f(3-2) 的值就是 $2$，继续进行运算。
6. 返回结果 $3 \times 2=6$，返回到 main() 函数，得到 f(3) 的值是 $6$，输出这个结果。

显然，虽然递归函数可以自己调用自己，但是不能无限制调用下去，所以必须要设置递归终止条件。上述代码的递归终止条件是 $f(1)=1$。

递归函数有点类似于剥洋葱，一层套着一层，直到掰到最里层。读读下面的故事，或许可以进一步了解递归。

从前有座山，山中有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：“从前有座山，山中有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：‘从前有座山，山中有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：“从前有座山，山中有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：‘太困了不讲了不讲了’，于是都回去睡觉了。”于是都回去睡觉了。’于是都回去睡觉了。”于是都回去睡觉了。

这样的故事可以抽象成：

void 讲故事() {
    if (困了) return;
    讲故事;
    回去睡觉;
}

函数几乎可以算是最难的基础内容，但是也是以后深入学习算法的必要条件，更是复杂算法的根本。请各位认真钻研，尽可能理解并掌握函数的用法。