11-函数

函数基础

与数学不同，在编程中，函数是一个被包装起来的代码块，它可以用来执行特定的任务，调用这个函数就相当于在执行里面的代码。

例如：假如我们定义了一个函数，它的功能是 传入一个数字 $n$ ，计算出 $1 - n$ 的总和，并输出总和，它的名字叫做 $g e t_s u m$ ，那么你可以这样理解调用函数的过程：

你说：“get_sum，告诉我 1-100 的总和。”

get_sum：“好的主人，1-100的总和是 5050”。

你说：“get_sum，告诉我 1-1000的总和。”

get_sum：“好的主人，1-1000的总和是 500500”。

有没有一种钢铁侠中 “Hey, 贾维斯” 的感觉？函数的作用就是如此，你调用函数，给它指定的数据，它就可以给你想要的结果。

1.定义函数

一个典型的函数应该包括：返回值类型、函数名、参数列表、具体代码，如下所示：

返回类型 函数名(参数类型1 参数1, 参数类型2 参数 2 ...) {
    // 函数主体，此处编写具体的代码
    // 可以包含各种语句，如定义变量、分支、循环等等。。
    
    return 返回值;  // 如果函数有返回值的话。
}

发现了吗？我们一直写的主函数其实就是一个函数。

那么如何编写自定义函数呢？让我们从一个最简单的函数开始：

int add(int a, int b) {
    int sum = a+b;  // 当然，这里也可以直接写 return a+b;
    return sum;
}

这段代码的作用是，定义了一个函数名为 add 的函数，返回值类型为 int，具备两个 int 类型的参数 a 和 b ，函数中代码执行逻辑为，计算两个参数的和，并把结果返回。

2.调用函数

定义函数之后，如何使用呢？首先，函数在代码的任何地方都可以被调用（当然，我们一般习惯于把函数放在调用之前，放在之后也能调用，不过需要先声明，在我们算法竞赛当中，习惯把函数放在调用之前）。

而我们调用函数，主要就做对两件事：1.叫对名字，2.给够它需要的数据。

下面这段代码演示了上面定义的 add 函数的使用：

#include <bits/stdc++.h>
using namespace std;

// 定义函数
int add(int a, int b) {
    int sum = a+b;  // 当然，这里也可以直接写 return a+b;
    return sum;  // 返回求和结果，同时结束函数的执行
}

int main() {
    // 调用函数
	int x = add(10, 20);  // 有返回值时，可以定义一个变量来接收返回值 
	cout << x << '\n';
	cout << add(11, 4) + add(51, 4) << '\n';  // 也可以直接使用 
    int a=1, b=2;
    cout << add(a, b) << '\n';  // 传数据时，也可以传变量进去
	return 0;
}

这段代码执行时，当执行到调用函数的部分时，每次调用就是把两个数字分别传到参数 a 和 b 中，然后执行 add 函数中的代码，最后把结果重新传回到调用处。

大家可以尝试自己写几个自定义函数，例如判断两个变量的大小、求和、求阶乘、判断质数等等。。

3.函数的应用场景

在编程过程中，函数主要的作用有：

模块化：按照程序的某些功能划分成为各个独立的函数，使得代码更加清晰易读，并让程序的结构更加有序。
代码复用：有些需要重复使用的功能放到函数中，就只用一行调用函数即可，不需要重复编写代码。
实现某些特定的算法：比如深度优先搜索算法，需要通过函数的递归来实现。

4. 课上例题

函数进阶

上面对函数的定义与使用进行了最基本的尝试，下面来进行更详细的了解。

1.函数返回值类型

除了数组之外，其他我们学习过的变量类型都可以作为函数的返回值，例如 long long、double、char，而数组可以通过指针来进行返回，不过也比较麻烦，在大多数情况下，我们可以直接在函数中修改数组中的值，就不需要返回了。这就涉及到 全局变量和局部变量 或者 引用传参 的概念，在下面我们会进行说明。

另外还有一个特殊的返回值类型 void，它表示这个函数不用返回值，例如：

void show() {
    cout << "我在show函数里面" << '\n';
    return ;  // 返回类型为 void 时，return 后面不能写任何数据，只用于结束函数的执行。
}

对于 void 类型的函数，return 语句可以省略不写，会在函数末尾自动结束，而对于其他返回类型的函数，return 语句是必须要写的，因为其他类型都需要返回数据。

2.函数的参数

基本概念

参数是函数调用时比较难理解的一部分，其实大家可以类比平时做题目的时候，每个题都会有输入，我们如何接收题目的输入呢？定义了变量，然后通过 cin 来输入，在写代码的时候，我们是 不知道 这几个变量里实际存储的数据的。

函数的参数也是类似，如果这个函数想实现的功能需要接收输入，比如 求 1~n 的总和、判断一个数字是否是质数 等，需要我们给函数提供数据，那么函数就需要定义对应的参数，来接收我们的输入，那函数是通过什么来输入数据的呢？在 调用函数 时，我们会在括号里面写上数据，它们会输入到函数当中，并完成这一次函数的执行。

对于一个函数，我们最少可以不定义参数，最长你想写多少写多少，当然也不推荐定义太多参数，这样并没有什么意义，同时，一个函数里面的参数的类型是可以不同的，比如：

void foo(int a, long long b, double c, string d) {
    cout << "我是 int 参数：" << a << '\n';
    cout << "我是 long long 参数：" << b << '\n';
    cout << "我是 double 参数：" << c << '\n';
    cout << "我是 string 参数" << d << '\n';
}

需要注意的是，每一个参数都应该单独进行参数类型的声明，比如下面这个例子就是错误的写法：

void foo(int a, b, c) {  // 错误的写法！！
    // ...
}

void oof(int a, int b, int c) {  // 正确的写法
    // ...
}

值传参与引用传参

在定义参数时，根据方式的不同，分为了 值传参 和 引用传参 两种方式。

值传参 是最普遍的写法，这种方式在调用函数时，是 传递一个备份给参数，在函数中改变这个参数，并不会影响调用处的数据，前面演示的所有函数都是值传参的写法。

引用传参 在做题的层面上应用范围偏少，很多时候有替代的方案，它的作用是在函数中改变参数的值，会影响调用处的数据，另外，引用传参因为不需要备份数据，所以效率比 值传参 更快一些。下面演示了两者的区别：

#include <bits/stdc++.h>
using namespace std;

void foo1(int a) {  // 值传参 
    a = 10;
}

void foo2(int& a) {  // 引用传参 
	a = 10;
}

int main() {
	int x = 5;
	foo1(x);
	cout << "调用值传参函数后：" << x << '\n'; 
	foo2(x);
	cout << "调用引用传参函数后：" << x << '\n';
	return 0;
}

数组传参

数组一样可以作为参数传递到函数中，比较特殊的是，数组传参都是引用传参，即在函数中改变数组的值，会影响调用处的数组，传递数组可以这样写：

// 下面是三种方式都是定义了一个 int数组 类型的参数，第二种用得比较多。
void print(int* a) {/*...*/}
void print(int a[]) {/*...*/}
void print(int a[10]) {/*...*/}

示例：

#include <bits/stdc++.h>
using namespace std;

void print(int a[], int len) {
    // 需要注意的是，在函数中不知道数组的长度，一般要再定义一个参数来传递数组的长度。
	for (int i=1; i<=len; i++)
		cout << a[i] << '\n';
}

int main() {
	int a[10] = {0, 1, 1, 4, 5, 1, 4};
	print(a, 6);
	return 0;
}

另外，多维数组一样可以作为数组的参数进行传递，例如：

// 多维数组的第一维可以不声明大小，其他维都必须声明大小。
void print(int a[][15]) {/***/}

注意：因为平时都要求数组定义在外面(全局位置)，所以很多时候其实数组都是直接在函数里用，而不是作为参数传进来。

3.全局变量和局部变量

在C++中，变量一般分为 全局变量 和 局部变量，两者的区别主要在三个地方：

作用域：
- 全局变量：全局变量通常在代码文件的顶部声明，从声明的位置一直到最末尾，整个程序都可以使用这个变量。
- 局部变量：局部变量在某一个代码块中声明，例如函数、循环、分支，可以这样理解，一对 {} 就是一个小的局部，在这个局部里声明的变量只能在这个局部中使用，其他地方无法使用。
```
#include <bits/stdc++.h>
using namespace std;
int a;  // 可以在任何位置使用 

void print() {
	int b;  // 只能在 print函数 里使用 
}

int main() {
	int c;  // 只能在 main函数 里使用 
	return 0;
}
```
生命周期：
- 全局变量：程序启动时创建，程序结束后销毁
- 局部变量：函数被调用时创建，函数执行结束后销毁。也就是说，每次调用函数时都是创建一个新的局部变量。
赋值：
- 全局变量：全局变量会自动赋初始值，比如 int 类型会默认赋值为 0，数组中的值会默认都设为 0。
- 局部变量：不会自动赋初始值，如果不赋值就使用局部变量，可能会发生一些意料之外的错误！

4.递归函数

递归的概念很简单：在函数中再次调用这个函数。例如：

void show() {
    cout << "我调用我自己" << '\n';
    show();  // 再次调用这个函数
}

如果你尝试调用这个函数，你会发现程序不停的输出，然后突然结束，这是发生了 栈溢出错误，为什么这样呢，因为上面这个函数其实类似 死循环，但是调用函数时会把函数的状态存储到栈里面，存储得多了，超过了栈的内存限制，就出错了~

关于递归，这里暂时不做太多的扩充，在后面学习搜索时会再详细进行说明，各位可以通过下面这个例子先做简单了解，下面演示了一个 递归求阶乘 的递归函数：

#include <bits/stdc++.h>
using namespace std;

int fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}

int main() {
    int n;
    cin >> n;

    cout << fact(n) << endl;

    return 0;
}

5.课上例题

定义找数组最大值最小值函数

内置常用函数

1.sort

作用为对一个序列进行排序，语法格式为：sort(待排序序列开始点, 结束点, [比较器])，其中比较器是定义函数来设定比较规则，可以不写，若不写的话默认为从小到大排序。

使用示例：

const int N = 1e3+5;
int n, a[N], b[N];

cin >> n;
for (int i=1; i<=n; i++) cin >> a[i];
for (int i=0; i<n; i++) cin >> b[i];

sort(a+1, a+1+n);  // 代码中数组 a 从 1 开始使用，所以待排序的范围是从 a[1]~a[n]
// a+1 表示从 a[1] 开始排序，a+1+n 表示到 a[n+1] 就不排序了。

sort(b, b+n);  // 数组 b 的待排序范围是 b[0]~b[n-1]

如果需要自定义比较规则，则需要定义一个返回值为 bool 类型的函数来设定比较规则，先演示一下设定从大到小排序规则：

bool cmp(int a1, int a2) {
	return a1 > a2;
}

const int N = 1e3+5;
int n, a[N];

cin >> n;
for (int i=1; i<=n; i++) cin >> a[i];

sort(a+1, a+1+n, cmp);

函数 cmp 就是定义的比较函数，它固定定义两个参数，参数的类型是待排序数组的类型，第一个参数和第二个参数可以理解为是数组元素的映射，第一个参数在数组中的位置是在第二个参数之前的。当函数返回 false 时，这两个元素会交换位置，如果返回 true 则不会交换。