C语言递归

沙漠下的胡杨 2022-06-18 我要评论

递归的认识

基本认识：

1.首先递归的本质还是函数调用，也要形成和释放栈帧。

2.函数的调用是有成本的，这个成本在时间和空间上表现为函数栈帧的形成和销毁。

3.递归就是不断形成栈帧和销毁的过程。

理论认识：

1.内存和cpu中的资源有限，也就决定啦，合理的递归是绝对不可以无限递归下去的。

2.递归不是什么时候都可以使用的，而是要满足自身的场景，即目标函数的子问题可以用该算法解决，本质是分治的思想。

3.递归的核心：大事化小，递归出口。

main函数可以递归吗

相信有些读者就在疑惑啦？main函数是主函数呀，这个怎么可以自己调用自己呢？

实际上，main函数本质也是函数，所以也就会形成栈帧，所以是可以自己调用自己的。

代码和运行结果如下：

int main()
{
	printf("胡杨树下\n");
	Sleep(100);//睡眠0.1秒
	main();
	return 0;
}

结果显示是可以调用的，那么我们也能过看出来，这个main函数的递归是不会自动停止的，停止时就是发生栈溢出，那么函数的栈帧是怎么形成的呢？

是最下面的main函数进行调用自身形成栈帧，如图示，我们可以看出，这些函数调用都开辟了空间，所以要占用内存，而且形成栈帧后需要释放，形成和释放过程中有时间消耗。这也就是递归有成本的原因。

递归核心思想讲解

我们在平时中见过这个题目，叫做求字符串长度。

这个我们可以用递归的写法求解，顺带我们看下递归的核心。

首先假设我们求的字符为 "abcdefg123"，我们用递归的解法可以转化为，1+"bcdefg123"，把"bcdefg123"进而再转化为1+"cdefg123"，进行求解，如图示：

经过一次次的大事化小，我们最后把问题变成了，求1+空字符串的长度，这个其实也就是我们想要的递归出口，当没有字符时我们就该结束啦。

代码如下：

int My_strlen(const char *str)
{
	if (*str == '\0')//函数出口
	{
		return 0;
	}
	return 1 + My_strlen(str + 1);//继续
}
int main()
{
	int len = My_strlen("abcdefg123");
	printf("len = %d\n", len);
	return 0;
}

递归的缺点

我们来看下递归的另外一个经典例子，第n个菲波那切数列的实现

首先菲波那切数列是前两个数之和等于第三个数，第一个和第二个我们设定为1，那么这个数列为 1,1,2,3,5,8,13....等等，那我们要求第n个斐波那契数列的话，只要转化为求前两个数的和就好了，最后的递归出口为第一个或者第二个数时停止，结束函数。

代码如下：求第十个菲波那切数

int fib(int n)
{
	if (n == 1 || n == 2)
	{
		return 1;
	}
	return fib(n - 1) + fib(n - 2);
}
int main()
{
	printf("fib(%d) = %d\n", 10, fib(10));
	return 0;
}

我们如果求的 n 的数字比较大就会非常慢。这个本质就是上述说的成本问题。

如果求的是第42个菲波那切数呢？这次我们把时间也计算上。

int fib(int n)
{
	if (n == 1 || n == 2)
	{
		return 1;
	}
	return fib(n - 1) + fib(n - 2);
}
int main()
{
	int n = 42;
	double start = GetTickCount();
	int x = fib(n);
	double end = GetTickCount();
	printf("fib(%d) = %d count = %.1f S\n", n,x,(end - start)/1000);
	return 0;
}