c语言基础知识帮助理解（函数递归详解）

是Nero哦

发布于 2024-01-18 18:12:36

1590

发布于 2024-01-18 18:12:36

"从前有座山，山里有座庙，庙里有个老和尚和一个小和尚。有一天老和尚对小和尚说:“从前有座山.山里有座庙，庙里有个老和尚和一个小和尚，有一天老和尚对小和尚说：“从前有座山.山里有座庙，庙里有个老和尚和一个小和尚......" （虽能体现递归特点，但又不是递归）

1.什么是递归

当一个函数在其定义中调用自身的过程称为递归。递归是一种强大的编程技巧，可以解决许多问题，特别是那些可以被分解为相同问题的子问题的情况

递归的主要思考方式在于：把大事化小。 在C语言中，函数递归的基本原理是将一个大问题分解为一个或多个更小的问题，然后通过调用自身来解决这些更小的问题，直到达到基本情况，即不再需要递归调用的情况

2.递归的两个必要条件

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

试想如若没有限制条件，那便无限循环，真就成了上面的“从前有座山山里有座庙” 的故事了。

3.事例和讲解

用递归来实现求n的阶乘（factorial）：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int factorial(int n)
{
	if (n > 1)//递归终止的条件
	{
		return n * factorial(n - 1);
	}
	else
	{
		return 1;
	}
}

int main()//递归实现求n的阶乘
{
	int n = 0;
	scanf("%d", &n);
	int n_factorial = factorial(n);
	printf("%d", n_factorial);
	return 0;
}

下面是一个示例的递归树，用于说明计算4的阶乘的过程： 4! = 4 * 3! | 3! = 3 * 2! | 2! = 2 * 1! | 1! = 1

下面讲解一下思路：

最基本便是：n！=n*（n-1）！——让我们有了返回n * factorial(n - 1)的想法
当n=1时，便是终止条件——返回1 ，使用factorial(n - 1)也是为了更加靠近n=1的终止条件

4.递归原理讲解

当一个函数被调用时，会在内存中分配一个称为函数栈帧（Function Stack Frame）的数据结构。函数栈帧用于存储函数的局部变量、函数的参数、函数的返回地址等信息。下面是一个示意图，展示了函数栈帧的结构：

Return Address：保存着函数调用结束后需要返回的地址，即函数调用的下一条指令的地址。当函数执行完毕后，CPU会根据该地址跳转到正确的位置继续执行
Previous Stack Frame：指向调用函数的函数栈帧的地址，用于在函数返回时恢复调用函数的上下文
Local Variables：存储函数的局部变量。每个函数栈帧都有自己的一块内存空间，用于存储局部变量的值
Parameters：存储函数的参数。参数在函数调用时被传递给函数，并存储在函数栈帧中

在递归函数中，每次递归调用都会生成一个新的函数栈帧，这些函数栈帧会按照一定的顺序依次排列在内存中：先调用的函数先进入栈中，后销毁

5.递归弊端

5.1利用计算斐波那契数列来引入

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

int main()
{
	int n = 3;
	printf("第三个斐波那契数%d\n", Fib(n));

	int x = 50;
	printf("第五十个斐波那契数%d", Fib(x));
	return 0;
}

我们会发现，第三个斐波纳契数立马就出来了，而第五十个迟迟不出来。

这就暴露了问题：

这个函数的时候如果我们要计算第 50 个斐波那契数字的时候特别耗费时间
函数求 10000 的阶乘（不考虑结果的正确性），程序会崩溃（我已经为各位试过了，不要再试了），也就是栈溢出了

这也说明：有时递归的效率不是很高，而且不得不说有时递归代码的可读性是不及循环的

5.2如何改进

那我们如何改进呢？

将递归改写成非递归。
使用static对象替代 nonstatic 局部对象。在递归函数设计中，可以使用 static 对象替代nonstatic 局部对象（即栈对象），这不仅可以减少每次递归调用和返回时产生和释放 nonstatic 对象的开销，而且 static 对象还可以保存递归调用的中间状态，并且可为各个调用层所访问

下面便用循环来改写求斐波那契数列：

int Fib(int n)
{
	int n1 = 1;
	int n2 = 1;
	int result = 0;
	while (n > 2)
	{n--;
		result = n1 + n2;
		n1 = n2;
		n2 = result;
		
	}
	return result;
}

int main()
{
	int n = 3;
	printf("第三个斐波那契数%d\n", Fib(n));

	int x = 30;
	printf("第三十个斐波那契数%d", Fib(x));
	return 0;
}