##C语言——学习攻略：函数递归思想的解析及应用

前言：在前一章学习了函数的相关概念，在本章将会接上篇，分享函数中重要的部分——函数递归，一起加油吧！

1. 讲述递归的思想

1.1 递归是什么

--递归：递归是一种解决问题的方法，简单说，在C语言中就是函数自己调用自己。（并不常用）

--一个简单的例子来解释：

#include <stdio.h>
int main()
{
	printf("hehe\n");

	main();//调用main函数
	
	return 0;
}
//整体类似于迭代——循环

--通过上面的程序，可以直观地感受到递归是什么；但注意，上面的代码只是为了演示递归，本身没有意义，运行后会无限递归，导致“栈溢出”（Stack overflow）

1.2 递归思想

--递归，就是将问题逐步分解为与原始问题相似的更小规模的子问题，来解决原始问题；直到转化为最简单的子问题，递归调用结束，然后从最后逐级返回值返回给上一级调用者。

--因此，递归理解为“递推”、“回归”。

1.3 递归的限制条件

在书写递归时，必须包含两个条件：

• 基准条件：递归必须有一个终止条件，否则导致“栈溢出”；
• 递归条件：每次递归都要使问题缩小，让递归向着终止条件逼近；

--函数递归的核心原则之一就是确保每次递归调用都向终止条件逼近。

别急，在下面的例子中更好的理解一下。

2. 补充：栈溢出

--什么是栈溢出？

--栈溢出指程序在执行时，调用栈（Call Stack）的内存空间被耗尽，导致程序崩溃。在递归或深层函数调用时最常见。

--为什么发生？

--递归没有终止条件（无限递归）；

--递归深度太大（每次函数调用都会占用栈空间，超出限制后崩溃。）或局部变量过多或过大（栈内存有限（通常几MB），存储大量局部变量可能导致溢出。）

--调用栈的作用

--存储函数调用的返回地址、参数、局部变量。

--每调用一次函数，栈会新增一帧（Stack Frame）；函数返回时，该帧被弹出。

--栈的大小固定（不同系统/语言默认值不同），超出后触发 StackOverflowError。

3. 递归举例

3.1 递归求n的阶乘

解题思路——

--需求分析

--实现输出n的阶乘——n！；（注意0！=1）

--实现方案

• 变量设置

--定义变量n：用来接收屏幕输入；

--定义变量ret（return）：用来调用函数；

• 主体结构

--函数实现：定义函数Fact，实现阶乘功能；

--主函数对阶乘函数进行调用并打印结果；

--递归函数

--目标实现

5！=5*4*3*2*1=5*4！； 4！=4*3*2*1=4*3！...... 这样就把大问题转化成了与原问题相似的小问题。

--递归公式

Fact(n)
{
	if (n == 0)//当求0阶乘，因为由1！=1*0！=1，所以特殊，使0！=1
	{
		return 1;//不能由阶乘公式计算，单独
	}
	else
	{
		return Fact(n - 1)* n;//由公式递推下去，直到满足终止条件，跳出
	}
}
//函数递推完后，接着回归数字

int main()
{
	int n = 0;//定义变量接收输入
	scanf("%d", &n);

	int ret = Fact(n);//变量接收函数调用结果
	printf("%d\n", ret);//打印阶乘结果
	return 0;
}

--条件解释：

--终止条件：n == 0；

--递归条件：return Fact(n-1)*n; 就是递归条件。它的作用是将问题分解为更小的同类子问题，并通过调用自身逐步逼近终止条件。

--画图演示

3.2 递归实现顺序打印整数的每一位

解题思路——

--需求分析

--将整数如：521，正序打印每一位——5 2 1；

--实现方案

• 变量设置

--变量n接收输入；

• 主体结构

--设计函数：

--联想到之前实现过逆序打印整数的每一位——使用%10得到最低的位数、/10得到去掉最低位数的数值、再循环实现；

--设置终止条件，由n/10得到下一次递归的数值，则n要保证为两位数，即n>=9；

--因为最后的回归是从最后一次递推结束后将值返回上一级函数调用，所以直接用n%10进行倒序取余，回归后为正序；

void Print(int n)//定义打印函数print，n接收输入
{
	//Print(521)拆分成Print(52) printf(521/10)

	if (n > 9)//终止条件
	{
		Print(n / 10);//得到去掉最低位数的数值
	} 
	printf("%d ", n % 10);//得到最低位
}

//主体实现
int main()
{
	int n = 0;//变量接收键盘输入
	
	scanf("%d", &n);//输入整数

	Print(n);//调用函数，进行打印输出

	return 0;
}

--画图演示

4. 递归与迭代

--递归是一种很好的编程技巧，但是如果不能恰当地使用，有时候不如不用。

--就像求阶乘，可以很容易写出递归形式：

--但是弊端也很明显：

• 栈溢出风险（Stack Overflow）​​​​​​​：每次递归调用都会在调用栈上添加一个新的栈帧；
• 效率问题：递归涉及函数调用的开销（参数传递、栈帧创建等）比迭代实现效率低；
• 重复计算问题：在某些递归算法中（如斐波那契数列），会重复计算相同的子问题；

​​​​​​​等等......

--所以有时会考虑使用迭代的方式：这样实现阶乘的效率更高

int main()
{
	int Fact = 1;//定义递归变量
	int num = 0;//定义数值n

	printf("请输入要求阶乘的数值：");

	scanf("%d", &num);//屏幕输入
	//循环实现n的阶乘
	for (int i = 1; i <= num; i++)
	{
		Fact *= i;
	}
	printf("数值%d阶乘结果是：%d", num, Fact);
	return 0;
}

--何时使用递归？

• 问题本身具有递归性质（如树遍历）
• 递归使代码更清晰、更易理解
• 结合记忆化可以优化重复计算问题

4.1举例：求第n个数的斐波那契数

​​​​​​​--这就是一个很典型的例子，它不适合用递归求解，但通常使用递归形式描述——

--根据形式我们很容易写成：

int Fib(int n)
{
	if (n <= 2)
	{
		return 1;
	}
	else
	{
		return Fib(n - 1) + Fib(n - 2);
	}

}

//主体代码
int main()
{
	int num  = 0;
	printf("输入要求斐波那契数的数值：");
	scanf("%d", &num);
	int ret = Fib(num);
	printf("数值%d的斐波那契数是：%d", num, ret);
	return 0;
}

--我们发现，当输入数值较大时——50，程序要计算很长一段时间，这就显得效率低！

--这是因为，程序要一级一级地计算下去，并且会重复计算子问题。

--迭代的方式：

int Fib(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (n > 2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	//n<2直接返回c
	return c;
}


int main()
{
	int num = 0;
	printf("输入要求斐波那契数的数值：");
	scanf("%d", &num);
	int ret = Fib(num);
	printf("数值%d的斐波那契数是：%d", num, ret);
	return 0;
}

--直观的对比得出，有时候迭代确实比递归好使，但这方式根据场景需要，自行选择。

结语：本篇文章到此结束，主要讲了函数递归的相关知识，后续会继续学习C语言相关内容；如果这篇文章对你的学习有帮助的话，欢迎一起讨论学习，你这么帅给个三连吧~~~