函数
我们之前已经提过 main 函数了，对吧？那你应该已经理解了函数的基本结构了，我们这里再回顾一下。
函数是 C 语言中非常重要的一个概念，它允许我们将代码模块化，从而提高代码的可读性和可维护性。
函数的定义格式如下：
返回类型 函数名(参数列表) {
// 函数体
}
其中，返回类型是函数返回值的类型，函数名是函数的名称，参数列表是函数的参数，函数体是函数的具体实现。
提示
和变量命名一样，函数名也建议使用 snake_case 命名法。
函数的调用
函数的调用格式如下：
函数名(参数列表);
其中，参数列表是函数的参数，可以是一个或多个。
例如，我们定义了一个函数 add，它接受两个整数作为参数，并返回它们的和：
int add(int a, int b) {
return a + b;
}
注意
即使多个传入参数的类型是相同的，你也不能把它们写在一起！你必须挨个为它们指定名称
因为参数的位置顺序决定了调用时的顺序，所以参数的顺序非常重要。
我们可以通过以下方式调用这个函数：
int result = add(1, 2);
提示
函数也可以先声明，再在之后给出定义，而函数在声明后就可以被使用：
int add(int a, int b); // 函数声明
int main() {
int result = add(1, 2); // 函数调用
return 0;
}
int add(int a, int b) { // 函数定义
return a + b;
}
递归
既然函数在声明后就可以被调用，而在函数定义之前（{} 之前），函数的声明就已经完成了，那我们能在函数中调用它自己吗？
答案自然是可以的，而这种在自己的函数体求解过程中使用自己得出的结果的方法，就是递归。
听起来可能有一些绕，但我们可以通过一个简单的例子来理解它。
例如，我们需要计算斐波那契数列的第 n 项，假设我们定义了它的结果由函数 f(n) 得出
我们也知道，斐波那契数列的前两项是 1，后面的每一项都是前两项的和
因此，f(n) 应当等于 f(n-1) + f(n-2)，而 f(1) 和 f(2) 都等于 1
所以，我们可以写出以下代码：
int f(int n) {
if (n == 1 || n == 2) {
return 1;
}
return f(n-1) + f(n-2);
}
注意
对于递归的编写，需要注意两个关键点：
- 递归的终止条件
我们需要在递归的过程中设置一个终止条件，以防止递归无限进行下去。在上面的例子中，我们设置了 n == 1 || n == 2 作为终止条件。
- 对于当前问题，如何拆分子问题
我们需要找到一个方法，将当前问题拆分为更小的子问题，并在子问题的解中找到当前问题的解。在上面的例子中，我们将 f(n) 拆分为 f(n-1) 和 f(n-2)。
提示
这里还有一个更难的例子：汉诺塔问题
我们先来找边界条件：
当起始柱子上只有一个盘子的时候，直接把它挪到终点柱子就好了。
然后我们来找盘子为 n 层时的处理方法：
实际上我们可以把 n 层抽象成两层：最底下的一层和上面 n - 1 层，以方便我们将 n 的问题拆分成更小的同时又能方便解决的问题。
然后考虑两层：我们得先把上面那个盘子移到中间柱子上面，再把下面一个盘子移到终点柱子上，最后把中间柱子上的那个盘子移到终点柱子上，完成汉诺塔的位移。
所以我们怎么具体构造这个递归呢？先给代码后解释：
void hanoi(int n, char a, char b, char c) {
if (n == 1) {
printf("%d:%c->%c", n, a, c);
}
else {
hanoi(n - 1, a, c, b);
printf("%d:%c->%c", n, a, c);
hanoi(n - 1, b, a, c);
}
}
先解释一下这个函数中各个参数的含义， n 自然不用说，表示 n 层，但是如果你将 a，b，c 认作是一柱二柱三柱那格局就小了，它们应该被称作起始柱子，中间柱子和终点柱子。在递归的过程中，这三个变量的表示的柱子实际上会不断变化，因为你在一些步骤中终点柱并不是最开始的那个终点柱：比如说两层的时候，你第一步是要移到中间柱上，而不是终点柱上，中间柱才是你这一步的终点柱。
首先用 if 特判解决掉最小的问题，我们直接输出移动方式就行了。
然后关键的在下面，对于 n 层，我们先将 n - 1 层从起始柱子通过终点柱子的帮助移到中间柱子去，这之后我们将最底下的那一层移到终点柱子上，这一步可以直接输出，最后我们将这 n - 1 层从中间柱子通过起点柱子的帮助，移到终点柱子上，这就是抽象为两层的汉诺塔问题的处理方法。
通过这样的处理，我们将 n 层的问题，转化成了一次移动和两次 n - 1 层的问题，这样层层缩小，最终变成一层的可以直接解决的问题。
实际上递归就是一种量变引起质变的方式，通过不断地解决小问题，总有一天你会发现，欸，大问题好像也就这么简简单单的解决了。
搜搜你的
听说过二维迷宫吗？就那种一个方格里到处都是 0 和 1 的那种？
现在有一个二维迷宫，你需要从起点 (1, 1) 出发，找到一条路径，使得你能够到达终点 (n, m)，其中 n 和 m 是迷宫的大小。
你只能向右或向下移动，不能向上或向左移动。
请你编写一个程序，输出一条路径，使得你能够到达终点。
如果没有路径，则输出 No Solution。
输入格式：
第一行包含两个整数 n 和 m，表示迷宫的大小。
接下来 n 行，每行包含 m 个整数，表示迷宫的布局。
输出格式：
一行一个整数，表示需要走多少步到达终点
如果没有路径，则输出 -1。
输入样例：
3 3
0 1 0
0 0 0
0 1 0
输出样例：
4
这道题该怎么解决呢？完全没办法啊？
实际上，它也可以用递归解决，要得到从起点到终点的路径，那我只需要知道终点可以从哪些地方到达就可以咯？
那终点可以从哪里来呢？从终点左边一格或者从终点上边一格来，那这两格又从哪里来呢？显然是从它们左边一格或者上边一格来，以此类推，直到起点。
我们也可以从起点反过来推，从起点开始，选择方向一路走到撞墙，如果某一步所有方向都走不通，就回到上一步，再选择一个方向走，直到走到终点。
同时，由于走到终点可能不止有一条路径，因此我们需要找到其中步数最短的那条路径
于是很轻松地就能写出以下代码：
// 如果是常量数组，可以不指定大小，编译器会自动计算大小
const int dx[] = {0, 1, 0, -1, 0};
const int dy[] = {0, 0, 1, 0, -1};
int best_steps = 2147483647; // 最大的 int 值，因为此时还没有找到路径
void dfs(int x, int y, int steps) {
// 边界条件：超出范围或者是已经走过
if (x < 0 || y < 0 || x > n || y > m || vis[x][y] == 1) {
return;
}
// 如果到达终点，输出结果
if (x == n && y == m) {
best_steps = steps > best_steps ? best_steps : steps;
return;
}
// 向四个方向搜索
for (int i = 1; i <= 4; i++) {
// 将当前点标记为走过
vis[x][y] = 1;
dfs(x + dx[i], y + dy[i], steps + 1);
// 还原现场，走不通，无事发生，继续尝试其他方向
vis[x][y] = 0;
}
}
int main() {
// 输入迷宫大小
scanf("%d%d", &n, &m);
// 输入迷宫
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &maze[i][j]);
}
}
// 从起点开始搜索
dfs(1, 1, 0);
// 输出结果
if (best_steps == 2147483647) {
printf("-1");
} else {
printf("%d", best_steps);
}
return 0;
}
很简单吧？但是想想这样找要找多久……
你会发现，这个代码的时间复杂度是指数级的，因为每一步都有四个方向可以选择，所以大概会有 4^n 种可能的情况。
而计算机在 1 秒之内最多只能执行 10^8 次运算，所以这个代码最多只能处理 n 小于等于 8 的情况。而 n 在这道题的数据范围可以达到 100，这显然是不合适的
因此，我们需要找到削减搜索空间的方法，来降低时间复杂度。
我们先给出答案，再来理解：
void dfs(int x, int y, int steps) {
// 边界条件：超出范围或者是已经走过
if (x < 0 || y < 0 || x > n || y > m || vis[x][y] == 1) {
return;
}
// ①
if (steps > best_steps) {
return;
}
// ②
if (ans == n + m - 2) {
return;
}
// 如果到达终点，输出结果
if (x == n && y == m) {
best_steps = steps > best_steps ? best_steps : steps;
return;
}
// 向四个方向搜索
for (int i = 1; i <= 4; i++) {
// 将当前点标记为走过
vis[x][y] = 1;
dfs(x + dx[i], y + dy[i], steps + 1);
// 还原现场，走不通，无事发生，继续尝试其他方向
vis[x][y] = 0;
}
}
我们添加了两个判断条件，分别是 ① 和 ②。
① 的作用是，如果当前已经走过的步数已经超过了之前找到的最短路径，那么就没有必要继续搜索了，因为无论如何，我们也不可能找到更短的路径。
② 的作用是，如果当前已经走过的步数已经超过了从起点到终点的最短路径，那么就没有必要继续搜索了，因为无论如何，我们也不可能找到一条路径。
这两个判断条件可以大大削减搜索空间，从而降低时间复杂度。
提示
另外，调转搜索方向的顺序也能削减搜索空间，因为理论上向右和向下走更多的路径更容易最短，所以可以优先搜索向右和向下走的情况，这样能更快地找到最短路径。
注意
递归是一种非常强大的算法思想，它可以用来解决很多复杂的问题，但是需要注意递归的边界条件和时间开销。
递推
递归是将大问题拆分为小问题，而递推是将小问题合并为大问题，实际上就是递归的反向
相对于递归的抽象，递推更加具体，反而更好理解，它是一种通过迭代的方式，逐步求解问题的方法，是一种正向的过程。
例如，我们要求解斐波那契数列的第 1 ~ n 项，我们可以从 f(1) 和 f(2) 开始，逐步计算 f(3)、f(4)、f(5) 等等，直到 f(n)。
int main() {
int n;
scanf("%d", &n);
int f[1005];
f[1] = f[2] = 1;
for (int i = 3; i <= n; i++) {
f[i] = f[i-1] + f[i-2];
}
// ...
}
提示
递推和递归是两种不同的算法思想，它们各有优缺点，具体使用哪种方法，需要根据问题的性质和需求来决定。
一般来说，递归在处理一些具有递归性质的问题时，如树、图等，会显得更加简洁和直观，而递推在处理一些具有迭代性质的问题时，如数列、动态规划等，会显得更加高效和直接。
树和图看不明白是什么意思的话，在学完语言开始将算法之后会详细讲解。
试一试！
DotOJ 补完计划 - 南哪 2022-5-function
DotOJ 补完计划 - 南哪 2022-6-recursion
DotOJ 补完计划 - 南哪 2022-6-recursion EX