亲宝软件园·资讯

展开

C语言递归

沙漠下的胡杨 人气:0

递归的认识

基本认识:

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;
}

我们可以看出第42个时就已经10秒了,这个很长时间啦。我们用全局变量接收下次数,那我们看看他计算了多少次第3个菲波那切数计算了几次? 计算了大概1亿多次,所以递归的重

复计算是非常多的。

我们看个图示:

其中单单是第六个菲波那切数就计算了3次,这个就很夸张啦。

所以递归的特点是代码简单,但是调用上可能会有大的成本。

最后一点就是:循环和递归是一定可以相互转化的。只不过有些时候转化会比较麻烦。

加载全部内容

相关教程
猜你喜欢
用户评论