蓝桥备赛（七）- 函数与递归（上）

一、函数是什么

数学中，我们其实就见过函数的概念，比如 : 一次函数 y = kx + b ， k 和 b 都是常数 ，给一个任意的x 就得到一个 y 值。其实C/C++语言中就引入了函数(function）的概念，有些翻译成：子程序；子程序这种翻译较为准确一些。函数就是一个完成某项特定任务的一小段代码 ；这段代码是有特殊写法和调用方法的。

在前面学习的时候，其实就已经见到函数了 --> main函数、scanf函数、 printf函数、pow函数等

C/C++语言程序其实就是由若干个小的函数组合而成的，也可以说一个大的计算任务可以分解成若干个较小的函数完成 。同时如果一个函数如果能完成某项特定任务的话，这个函数也是可以复用的，提高了开发软件的效率。

下面举个例子：

如果我们希望完成以下的任务：

#include <iostream>
#include <cstdio>
using namespace std;int main()
{int arr[10] = {0};//打印数组的内容//给数组的元素赋值为1~10//打印数组 return 0;
}

按照以前的思路：

#include <iostream>
#include <cstdio>
using namespace std;int main()
{int arr[10] = {0};//打印数组的内容for(int i = 0;i < 10; i++){cout << arr[i] << " ";	} //给数组的元素赋值为1~10for(int i = 0 ; i < 10 ; i++){arr[i] = i + 1;	}	cout << endl;//打印数组 for(int i = 0;i < 10; i++){cout << arr[i] << " ";	} return 0;
}

所以如果我们能把这部分封装成一个函数，在需要的时候调用，就会方便很多 ，看如下代码：

#include <iostream>
#include <cstdio>
using namespace std;void print_arr(int arr[])
{for(int i = 0;i < 10; i++){cout << arr[i] << " ";	} cout << endl;
}int main()
{int arr[10] = {0};//打印数组的内容print_arr(arr);//给数组的元素赋值为1~10for(int i = 0 ; i < 10 ; i++){arr[i] = i + 1;	}	cout << endl;//打印数组 print_arr(arr);
}

以上print_arr 就是我们自己定义的一个函数，使用函数能有什么好处呢？

1） 模块化开发， 一个大的功能，总能拆分成各种子功能，每个子功能都可以设计成一个函数，每个函数都可以作为一个独立的模块存在，程序的逻辑更加清晰，逻辑关系更加明确。（大问题化若干个小问题）

2 ）代码可以复用， 只需要根据需要定义出一个函数，需要这个功能的地方，直接调用函数就行了， 降低了代码的冗余，提升了开发效率。

3 ) 方便了多个程序员之间协作开发，方便程序的多个模块之间互相交互。

4 . 熟悉函数使用后，代码的编写、阅读、调试、维护都变得更加容易。

二、函数的分类

在C/C++中，函数一般分为库函数和自定义函数，接下来介绍， show time ~ ：

2.1 库函数

2.1.1库函数介绍

printf , scanf 等 ---> 库函数， 即标准库中提供了现成的函数 ，我们只需要学习函数的功能，就能直接使用 ，有了库函数，一些常见的功能不需要程序员自己实现了 ，一定程度上提升了效率，同时库函数的质量和执行效率都有更高的保证。

---> 很方便，我们只需要知道，会用，就可以了。就不需要从零开始造函数。

编译器的标准库中提供了一系列的库函数，这些库函数根据功能划分，都在不同的头文件中进行了声明 ; 不着急一次性全部学会，慢慢学习，多查文档，孰能生巧。

C/C++官方参考手册：https://zh.cppreference.com/w/cpp/header

C/C++第三方网站：Reference - C++ Reference

C++是兼容C语言，所以在C++也包含了一些来自C语言的头文件，这些头文件的后缀是 .h , 如果需要也可以直接包含使用 ；有一些来自C语言的头文件，在C++中会在原来C语言的头文件进行了封装，在C++程序中国，更推荐C++头文件的写法！

2.1.2库函数使用举例：

sqrt sqrt - C++ Reference

double sqrt (double x);

1 . sqrt 是函数名

2 . x 是函数的参数，表示调用 sqrt 函数需要传递⼀个 double 类型的值

3 . double 是返回值类型，表示函数计算的结果是 double 类型的值

使用某一个函数的时候，一定要记得包含其对应的头文件。因为库函数是在标准库对应的头文件中声明的。不包含的话，则使用不了对应函数。

一定要包含头文件！！！

2.2 自定义函数

库函数的功能是有限的， 实际开发过程中， 需要将代码封装成自定义函数 ；自定义函数就是自己设计和实验的函数 。

2.2.1函数的语法形式

其实自定义函数和库函数是一样的，形式如下：

1 . ret_type 是用来表示函数计算结果的类型，有时候返回类型可以是 void ，表示什么都不返回

2 . fun_name 是为了方便使用函数；函数有了名字就方便调用，所以函数名尽量要根据函数的功能起的有意义。

3 . 函数的参数就相当于工厂加工需要的原材料，函数的参数也可以是 void ，明确表示函数没有参数。如果有参数，多个参数用逗号隔开，每个参数要分别交代清楚参数的类型和名字。

4 . {} 括起来的部分被称为函数体，函数体就是完成计算的过程。

我们可以把函数想象成一个小型的加工厂，工厂需要输入原材料，经过工厂加工才能生产出产品，那函数也是一样，函数一般会输入一些值（可以是 0 个，也可以是多个），经过函数内部计算，得到结果。

2.2.2函数定义

如何定义一个函数呢 ?

需求：写一个加法函数，完成两个整型变量的加法操作。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;int main()
{int a = 0;int b = 0;//输入cin >> a >> b;//调用加法函数，a + b = ?//输出 return 0;
}

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;int Add(int x , int y)
{int z = 0;z = x + y ;return z;	
} 
int main()
{int a = 0;int b = 0;//输入cin >> a >> b;//调用加法函数，a + b = ?int ret = Add(a , b);//输出 cout << ret << endl;return 0;
}

函数的参数部分需要交代清楚：参数的个数，每个参数是什么，形参的名字是什么；

未来我们需要根据实际需求来设计函数，函数名、参数、返回类型，这些都是可以灵活变化的。 函数的实现就是函数的定义。

三、函数参数和返回值

3.1 实参和形参

3.1.1 实参

真实传递给函数的参数。

3.1.2 形参

在上面代码中， Add后面的括号中写的 x 和 y ，称为形式参数，简称形参。

----> 如果只是定义Add 函数，不去调用， Add函数和参数 x 和 y 只是形式上存在的，不会向内存申请空间，不会真实存在，所以叫形式参数。形式参数只有在函数被调用的过程中未来存放实参传递过来的值，才向内存申请空间，这个过程就是形式的实例化。

3.1.3 实参和形参的关系

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;int Add(int x , int y)
{int z = 0;z = x + y ;return z;	
} 
int main()
{int a = 0;int b = 0;//输入cin >> a >> b;//调用加法函数，a + b = ?int ret = Add(a , b);//输出 cout << ret << endl;return 0;
}

Dve-C++调试查看地址：

在调试的时候， x 和 y 确实是得到了 a 和 b 的值，但是 x 和 y 的地址与 a 和 b 的地址是不一样的，当 a 和 b 传参给形参 x 和 y 的时候， x 和 y 只是得到了 a 和 b 的值，他们有自己独立的空间， 所以我们可以理解为形参是实参的一份临时拷贝。

3.2 函数传参

3.2.1数组做函数参数

在使用函数解决问题的时候，也许会需要数组作为参数传递给函数，在函数内部对数组进行操作

比如：写一个函数将整型数组的内容全部置为 -1 ，然后再写一个函数打印数组的内容

---> 函数大体大概如下

int main()
{int arr[] = {1,2,3,4,5,6,7,8,9,10};set_arr;//将数组置为-1 print_arr;//打印数组return 0; 
}

把数组的值置为-1 ，打印数组都涉及数组遍历，需要知道数组的长度 sz，然后传参

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;void set_arr(int arr[],int sz)
{for(int i = 0;i< sz;i++)arr[i] = -1;
}
void print_arr(int arr[],int sz)
{for(int i = 0;i< sz;i++)cout << arr[i] << " ";cout << endl;
}
int main()
{int arr[] = {1,2,3,4,5,6,7,8,9,10};int sz = sizeof(arr)/sizeof(arr[0]); set_arr(arr,sz);//将数组置为-1 print_arr(arr,sz);//打印数组return 0; 
}

通过调试，查看数组传参时，形参的数组和实参的数组是否是同一个数组；

#define _CRT_SECURE_NO_WARNINGS 1
#include <cstdio>
#include <iostream>
using namespace std;void set_arr(int arr1[], int sz1)
{for (int i = 0; i < sz1; i++){arr1[i] = -1;}
}
void print_arr(int arr2[], int sz2)
{for (int i = 0; i < sz2; i++){cout << arr2[i] << " ";}cout << endl;
}
int main(){int arr[] = { 1,2,3,4,5,6,7,8,9,10 };int sz = sizeof(arr) / sizeof(arr[0]);print_arr(arr, sz);//打印数组set_arr(arr, sz);//置为-1cout << endl;print_arr(arr, sz);return 0;
}

arr 和 arr1 和 arr2 的地址相同，表明，形参操作的数组和实参操作的数组是同一个数组！

3.2.2字符串做函数参数

用字符串做函数参数，直接在形参的部分使用字符串来接收就可以。但是这里的形参s 是实参s 的一份临时拷贝，形参的改变不能影响实参

#define _CRT_SECURE_NO_WARNINGS 1
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;void test(string s1)
{cout << s1 << endl;
}
int main()
{string s = "Hello World!";test(s);return 0;
}

3.2.3全局变量不用传参

全局变量的作用域很大，在整个程序中都可以使用，那么只要把变量、数组等定义成全局变量，在函数中使用，是可以不用传参。在竞赛中经常会使用，因为方便、快；但是在软件工程中很少这么用，都是使用局部变量的。

#define _CRT_SECURE_NO_WARNINGS 1
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;int arr[] = { 1,1,1,1,1,1,1,1,1,1};
int sz = sizeof(arr) / sizeof(arr[0]);
void print_arr()
{for (int i = 0; i < sz; i++){cout << arr[i] << " ";}cout << endl << endl;
}
void set_arr()
{for (int i = 0; i < sz; i++){arr[i] = i + 1;}
}
int main()
{print_arr();set_arr();print_arr();return 0;
}

当然，不能因为全局变量很方便，上来就定义一个全局变量；还需要具体情况具体分析。有些变量或者数组定义成全局的时候，并不能解决问题，比如：递归等，这时候，就需要考虑传参的问题。

3.3 返回值

对函数返回值的设置，有时候需要带回一些计算好的数据，这时候往往使用return 来返回

1）return 后面可以是一个数值，也可以是一个表达式。如果是表达式则先执行表达式，再饭hi表达式的结果。函数返回的值，可以使用变量来接收，如果不需要这个返回值，那就不接收。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;int Add(int x,int y)
{int z = x + y;return z; 
}
int main()
{int a,b;cin >> a >> b;int ret = Add(a,b);cout << ret << endl;	return 0;
}

当然，在这里我们也可以设置，不用变量接收Add 的返回值，直接打印

2）return 后面也可以什么都没有，直接写return , 这种写法适合函数返回类型是void 的情况


void test(n)
{if(n == 2)return;cout << n << endl;
}

这里的return 是指，只要 n 为 2 ，函数就提前返回，不再执行下一条语句。

3）return 返回的值和函数返回类型不一致，系统会自动将返回的值的类型隐式转换为函数的返回类型。

4 ）return 语句执行后，函数就彻底返回，后边得到代码不执行

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;void print_arr(int arr[], int n){int i = 0;for(i=0; i<n; i++){cout << arr[i] << " ";}cout << endl;cout << "打印完毕" << endl;
}int main(){int arr[10] = {1,2,3,4,5,6,7,8,9,10};print_arr(arr, 10);return 0;}

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;void print_arr(int arr[], int n){int i = 0;for(i=0; i<n; i++){if(i == 5)return; cout << arr[i] << " ";}cout << endl;cout << "打印完毕" << endl;
}int main(){int arr[10] = {1,2,3,4,5,6,7,8,9,10};print_arr(arr, 10);return 0;}

如果把 return 换成 break , 情况会是什么样？

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;void print_arr(int arr[], int n){int i = 0;for(i=0; i<n; i++){if(i == 5)break; cout << arr[i] << " ";}cout << endl;cout << "打印完毕" << endl;
}int main(){int arr[10] = {1,2,3,4,5,6,7,8,9,10};print_arr(arr, 10);return 0;}

四、函数的声明和调用

4.1 函数声明

一般再使用函数的方式写代码的时候， 函数定义好后，在后续的代码中对函数进行调用 ，例如以下代码：

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;//函数定义
int Add(int x ,int y)
{int z = x + y;return z;
}
int main()
{int a,b;cin >> a >> b;int ret = Add(a,b);cout << ret << endl;return 0;
}

但是有时候我们会把，函数定义放在函数调用的后面，例如下面的代码，会有警告出现（如下图），提示这个函数可能不存在。未来消除这种警告，我们一般在函数调用之前就声明函数。函数声明就是为了告诉编译器，有一个函数名字叫什么，参数是什么，返回类型是什么，至于这个函数是否真的存在，就是要看编译器了。函数调用必须满足先声明后使用。

1 ) 必须保证函数申明在函数定义之前

2 ）函数定义其实是一种特殊的函数声明

3 ）函数声明中，形参的变量名可以不写；

例如 : int Add(int , int )

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;//函数声明
int Add(int x,int y);
int main()
{int a,b;cin >> a >> b;int ret = Add(a,b);cout << ret << endl;return 0;
}
int Add(int x ,int y)
{int z = x + y;return z;
}

4.2 函数调用

4.2.1传值调用

案例一：写一个函数Max , 求两个整数的较大值

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;int Max(int x, int y)
{return x > y ? x : y;
}
int main()
{int a = 0;int b = 0;cin >> a >> b;//求两个数的较大值int m = Max(a, b);cout << m << endl;return 0;
}

调用Max 函数的时候，就是传值调用 ---> 就是将实参的数据直接传递给形参。这个过程其实就是将实参的值拷贝给 Max 函数使用。这时形参和实参是不同的变量，所以对形参的修改，不会影响实参。这种情况只能从实参到形参，也就是单向传递。

案例二：写一个函数Swap ，交换两个整型变量的值

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;void Swap(int x, int y)
{int z = x;x = y;y = z;
}
int main()
{int a = 0;int b = 0;cin >> a >> b;cout << "交换前，a = " << a << " b = " << b << endl;Swap(a, b);cout << "交换后，a = " << a << " b = " << b << endl;return 0;
}

这就是值传递的特点，形参和实参是不同的内存空间，对形参的修改不会影响实参，数据仍然是单向传递，所以交换的效果没有达到！

形参的改变影响实参 --> 指针 / 引用

不需要改变实参 --> 传值

4.2.2 引用

引用的概念

引用不是新定义的一个变量，而是给已经存在的变量取了一个别名，编译器不会为引用变量开辟空间，它和它引用的变量是同一块空间。如下：

引用的格式：

类型 & 引用变量名 = 引用实体

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;int main()
{int a = 10;int& ra = a;cout << a << endl;cout << ra << endl;return 0;
}

引用的特性

4.2.3 传址(引用)调用

那么我们可以使用引用来写Swap 函数了：

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;void Swap(int & x, int & y)
{int z = x;x = y;y = z;
}
int main()
{int a = 0;int b = 0;cin >> a >> b;cout << "交换前，a = " << a << " b = " << b << endl;Swap(a, b);cout << "交换后，a = " << a << " b = " << b << endl;return 0;
}

这种方式就是传引用调用 ， 本质是将实参的地址传递给了形参，而形参使用指针直接找到实参来进行操作。

拓展学习 : swap 函数

其实在C++的STL中提供了一个库函数swap , 这个函数可以用来交换变量，也可以交换两个数组（容器的值），如果掌握了，，我们就不需要自己再实现交换的逻辑，直接使用现成的函数。

swap 函数需要的的头文件 <utility>

#include <cstdio>
#include <iostream>
#include <utility>
using namespace std;int main()
{int a = 0;int b = 0;cin >> a >> b;cout << "交换前，a = " << a << " b = " << b << endl;swap(a, b);cout << "交换后，a = " << a << " b = " << b << endl;return 0;
}

使用swap 交换两个数据也是可以的：

#include <cstdio>
#include <iostream>
#include <utility>
using namespace std;int main()
{int a1[4];int a2[] = {6,6,6,6};swap(a1, a2);for (auto e : a1){cout << e << " ";}cout << endl;return 0;
}

字符串也可以用引用的方式传参：

#include <cstdio>
#include <iostream>
#include <utility>
using namespace std;void printString(string& s)
{cout << s << endl;s = "haha";
}int main()
{string s = "Hello";printString(s);cout << s << endl;return 0;
}

4.2.4 传值、传引用效率比较

定义一个全局字符串s , 然后以传值和传引用进行对比，看效率差异 :

#include<iostream>
#include<ctime>
using namespace std;//定义全局字符串s
string s("hello world");void TestFunc1(string s) {}
void TestFunc2(string& s) {}void Test()
{// 以值作为函数参数size_t begin1 = clock();for (size_t i = 0; i < 10000000; ++i){TestFunc1(s);}size_t end1 = clock();// 以引用作为函数参数size_t begin2 = clock();for (size_t i = 0; i < 10000000; ++i){TestFunc2(s);}size_t end2 = clock();// 分别计算两个函数运?结束后的时间cout << "TestFunc1(string)-time:" << end1 - begin1 << endl;cout << "TestFunc2(string&)-time:" << end2 - begin2 << endl;
}int main() 
{Test();return 0;
}