10. 递归
递归 是指在函数内部直接或间接调用自身的函数。
递归不是 C 语言的语法，而是函数的一种特殊用法。使用递归可以很方便地解决很多复杂问题。
递归通过将问题分解为更小的同类子问题来解决问题，直到达到一个终止条件，从而避免循环和当前数据压栈、弹栈等操作。
递归的作用 是简化特殊场合的编程难度，如：遍历二叉树、快速排序等场景。
在理解递归之前我们先复习前面讲过的函数一些概念。
函数在每一次调用时会在栈上开辟一段内存空间用来保存此次函数调用时的局部变量、返回地址等信息。此局部变量直到函数返回后才弹栈销毁。当此函数没有退出时又再次调用进入下一个函数调用时，也同样会为下一个函数调用在栈上开辟新的空间来保存这次调用的局部变量，即便是当前函数在调用同名的函数自身时也是如此。
递归解决问题是分为两个阶段：
- 递进：是指函数逐次调用，一层层进入的过程。
- 回归：是指深层的函数逐次返回到上一次调用的地方的过程。
下面我们用递归求阶乘来说明递归的运行原理。
在数学中，n 的阶乘表示为 n!，含义是 1 * 2 * 3 * ... * n 的乘积的结果。如 3! 等于 1 * 2 * 3 等于 6。
在写递归函数之前假设我们已经完成了这个递归求阶乘的函数为 int factorial(int n)，这个函数传入 n 返回 n!。
求5! 递归示意
5! = 5 * 4! 表示为 factorial(5) = 5 * factorial(5-1);
4! = 4 * 3! 表示为 factorial(4) = 4 * factorial(4-1);
3! = 3 * 2! 表示为 factorial(3) = 3 * factorial(3-1);
2! = 2 * 1! 表示为 factorial(2) = 2 * factorial(2-1);
1! = 1 表示为 factorial(1) = 1;
可见求 1! 时，结果就一定是 1, 但在求 2! 时我们不知道 2! 是多少，但我们知道 2! 等于 2 * 1!，从而也可以求出 2!，同理 3! 等于 3 * 2! 那我也可以求出 3!。这样我们就可以求出 5! 是 5 * 4！ 以此类推。
根据以上分析。我们来用递归的方法实现 factorial 函数如下:
int factorial(int n) {
if (n == 1)
return 1;
return n * factorial(n-1);
}
在上述函数中，调用时如果 n 为 1 则直接返回 1，如果 n 不为 1 则 先 递进调用 factorial(n-1)，待 factorial(n-1) 返回后再乘以 n 再返回，至此达到了求阶乘的目的。至于 factorial 函数会递进多少次，这要看参数 n 的值是多少了。这种方法就是递归。
完成测试程序如下：
// filename: factorial.c
#include <stdio.h>
int factorial(int n) {
if (n == 1)
return 1;
return n * factorial(n-1);
}
int main(int argc, char * argv[]) {
printf("5! 等于 %d\n", factorial(5));
printf("4! 等于 %d\n", factorial(4));
printf("1! 等于 %d\n", factorial(1));
return 0;
}
运行结果如下：
weimingze@mzstudio:~$ ./factorial
5! 等于 120
4! 等于 24
1! 等于 1
可见，上述函数 factorial 实现了求阶乘的算法。如果您不了解程序调用的过程，你可以尝试在 factorial 函数内部添加 printf 打印 n 的值，在研究调用次序就可以明白了。
递归的优缺点
优点
- 代码简洁：适合解决分治问题（如快速排序、树的遍历等操作）。
- 更符合数学定义：如阶乘、斐波那契数列的数学描述直接对应递归代码。
缺点
- 栈溢出风险：深层递归可能导致调用栈溢出。
- 性能问题：可能存在重复计算导致性能下降。
练习：
- 使用循环写一个函数
int sum1_to_n(int n)求1 + 2 + 3 + ... + n的和。 如：sum1_to_n(4)的返回值是10,sum1_to_n(10)的返回值是55。 - 将上述函数改为递归实现。