C语言--递归

曾经有一个段子：上大学时，我们的c语言老师说：学c时，如果有50%的同学死在了循环上面，那么就有90%的同学死在了递归上面。接下来，就来看看递归是怎么个事？

一.递归的介绍

递归是指一个函数直接或间接调用自身的过程。在编程中，递归通常用于解决可以被分解为相似子问题的任务。

1. 基本原理：递归函数通过反复调用自身来解决问题，每次调用都会解决一个规模较小的子问题，直到达到递归的终止条件。

2. 递归函数的结构：

   • 基本情况（终止条件）：递归函数需要定义一个或多个基本情况，这些情况下递归调用不再发生，避免无限循环。
   • 递归情况：在递归情况下，函数调用自身来解决同一问题的子问题。

3. 递归与循环：递归和迭代循环（for、while循环）都可以实现相同的算法，但递归通常更简洁，易于理解，有时更符合问题的自然表达方式。

4. 递归的应用：递归广泛用于数据结构==（如树、图等）的遍历和搜索==，例如深度优先搜索（DFS）和快速排序算法。

5. 性能考虑：递归可能会消耗大量的栈空间，因为每次函数调用都会在栈上分配一个新的栈帧。这在处理大规模问题时需要注意，可以通过优化算法或者尾递归优化来减少内存消耗。

6. 递归的优缺点：

   • 优点：简洁、清晰表达某些问题的解决方式。
   • 缺点：可能会因为调用层次过深导致栈溢出，性能上可能不如迭代循环。

二.什么是栈帧

栈帧（Stack Frame），也称为活动记录（Activation Record）或者帧（Frame），是在函数调用过程中在程序运行时栈上的一个特定区域，用于存储与当前函数调用相关的信息和数据。每当一个函数被调用时，系统就会为该函数在栈上分配一个新的栈帧，用于管理函数的局部变量、参数、返回地址以及其他执行上下文信息。

栈帧通常包括以下主要部分：

1. 局部变量：函数内部声明的局部变量会被存储在栈帧中。这些变量的生命周期与函数的调用周期相关联，在函数调用结束时，这些变量的存储空间也会自动释放。

2. 参数：调用函数时传递的参数值被存储在栈帧中，供函数体内部使用。

3. 返回地址：函数调用完成后，程序需要返回到调用该函数的下一条指令的地址。返回地址存储在栈帧中，使得程序可以正确地返回到调用点继续执行。

4. 其他管理信息：栈帧还可能包括调试信息、异常处理信息等，这些信息有助于程序的正确执行和调试。

栈帧的创建和销毁遵循后进先出（LIFO）原则，即最后进入栈的栈帧最先被释放。这种机制保证了函数调用的嵌套顺序正确，同时也控制了函数调用过程中的内存管理。

理解和正确使用栈帧是编写函数式程序的关键，尤其是在处理递归函数或者多层函数调用时，对栈帧的合理利用可以提高程序的效率和可靠性。

举例说明

有 5 个学生坐在一起, 问第 5 个学生多少岁？他说比第 4 个学生大 2岁,问第 4 个学生岁数，他说比第 3 个学生大 2 岁,问第 3 个学生，又说比第 2个学生大 2 岁,问第 2 个学生，说比第 1 个学生大 2 岁,最后问第 1 个学生，他说是 10 岁,请问第 5 个学生多大。
该问题如果使用非递归,代码如下:

//非递归求年龄
int Age1(int n)
{
	int tmp = 10; //第一个人年龄
	for(int i=1;i<n;i++)
	{
		tmp += 2;//后面的人比前一个多 2 岁
	}
		return tmp;
}

那么递归该如何处理呢?我们先分析一下:
如果 Age 函数是用来求年龄的,那么
Age(1)表示第一个人的年龄;
Age(2)表示第二个人的年龄;
…
Age(n-1)表示第 n-1 个人的年龄;
Age(n)表示第 n 个人的年龄。
上面的这些能理解,下面的程序就好理解了

//递归求年龄
int Age(int n)
{
	int tmp;//保存年龄
	if (n == 1)
		tmp = 10;
	else
		tmp = Age(n - 1) + 2;//当前第 n 个比第 n-1 个年龄多 2
	return tmp;
}

上图中的红色表示函数的调用过程,在这个过程中每个函数都还没有执行完成,那么每个函数占用的内存空间都不能释放,函数的调用都需要占用一定的栈空间(一个栈帧),而栈的空间是非常小的(在动态内存章节讲过栈 1M),当递归次数非常多时有可能出现栈空间不足

// 递归求年龄
int Age(int n)
{
	int tmp;//保存年龄
	if (n == 1)
		tmp = 10;
	else
		tmp = Age(n - 1) + 2;//当前第 n 个比第 n-1 个多 2
	return tmp;
	//return n == 1 ? 10 : Age(n - 1) + 2;//等同上面的代码
}
 //递归调用次数太多, 程序崩溃
int main()
{
	printf("%d\n", Age1(5000));//可以.利用循环求解
	//printf("%d\n",Age(5000));//崩溃,栈溢出,递归次数太多,超过栈容量
	return 0;
}

例2.求阶乘

利用递归求阶乘 n!
算法分析:可以利用下面公式求阶乘

long long Fac(int n)
{
	if (n == 0 || n == 1)
		return 1;
	return n * Fac(n - 1);
}