C语言函数（四）：递归

1.什么是递归

在学习函数这一章节，递归是每个计算机语言绕不开的知识点，那什么是递归呢？
递归就是一种解决问题的方法，在C语言中，递归就是函数自己调用自己。

int main() {
	printf("haha\n");
	main();
	return 0;
}

上述代码就是一个简单的递归程序，只不过它只是演示了递归的基本作用，不是为了解决问题，这不是一个正确的递归程序，代码最终会陷入死循环，导致栈溢出。
递归的思想：
把一个大型的复杂的问题层层转化为一个与原问题相似，但规模较小的子问题来求解，直到子问题不能再被拆分，递归就结束了。所以递归的思考方式就是将大事化小的过程。
递归中的递就是递推的意思，归就是回归的意思。

2.递归的限制条件

递归存在限制，当满足这个限制条件时，递归就不再继续
每次递归调用之后越来越接近这个限制条件

3.递归举例

3.1 举例一：求n的阶乘

计算n的阶乘，就是1~n的数字累积相乘
n的阶乘公式： n!=n * (n-1)!
在这里插入图片描述
代码实现：

int Fact(int n) {
	if (n <= 0) {
		return 1;
	}
	else {
		return n * Fact(n - 1);
	}
}

int main() {
	int n = 0;
	scanf("%d", &n);

	printf("%d\n", Fact(n));

	return 0;
}

在这里插入图片描述
解题过程：

4.递归与迭代

递归可以直接方便直观的解决问题，但是他也有不小的缺点，那就是系统开销大，容易造成栈溢出

在C语言的每一次函数调用中，都需要为本次函数调用在栈区申请一块内存空间来保存函数调用期间的各种局部变量的值，这块空间被称为运行时堆栈，或者函数栈帧。
函数不返回，函数对应的栈帧空间就一直被占用，所以如果函数调用中存在递归调用的话，每一次递归调用都会开辟属于自己的栈帧空间，直到函数递归不再继续，开始回归，才逐层释放栈帧空间。
所以函数采用递归的方式完成代码，递归层次太深，就会浪费太多的栈帧空间，可能会引起栈溢出的问题。

比如：

4.1 求第n个斐波那契数

计算斐波那契数的公式：
在这里插入图片描述
测试代码：

int Fib(int n) {
	if (n <= 2) {
		return 1;
	}
	else {
		return Fib(n - 1) + Fib(n - 2);
	}
}
int main() {
	int n = 0;
	scanf("%d", &n);
	printf("%d\n", Fib(n));
	return 0;
}

在这里插入图片描述
这个问题使用递归来解决是非常低效的，那是因为会占用过多的栈帧空间。

其中FIb（48）以下的元素都将被计算两次，而且分支越来越多，系统消耗量就越来越大。

其实用循环的方式来解决这个问题更好

int method(int n) {
	int a = 1, b = 1, c = 1;
	while (n > 2) {
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}
int main() {
	int n = 0;
	scanf("%d", &n);
	int ret = method(n);
	printf("%d\n", ret);
	return 0;
}