• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

零基础C语言学习

互联网 diligentman 2周前 (02-19) 7次浏览

                  *c语言学习笔记(十三)*

今天继续学习函数递归部分的内容
一、练习
编写程序,不允许创建临时变量,打印字符串长度。(用递归解决)
首先在不考虑递归方法时,我们知道要想求字符串长度,可以有一下两种方式,第一种就是利用sizeof

char arr[] = "helloworld";
//int a = self - strlen(arr);
int a = sizeof(arr) / sizeof(arr[0]) - 1;
printf("数组长度为:%d", a);

由于字符串都是以结尾的,所以要在计算值后面再减一;
第二种是使用库函数strlen,可以直接获得字符串的长度

int a =strlen(arr);
printf("数组长度为:%d", a);     

今天根据题目要求,我们需要使用递归的方法创建一个自定义函数,来解决问题。下面为代码:

int self_strlen(char*str)
{
	if (*str != '')
	{
		return 1 + self_strlen(str+1);

	}
	else
		return 0;	

}
int main()
{

	char arr[] = "helloworld";
	int a = self_strlen(arr);
	//int a = sizeof(arr) / sizeof(arr[0]) - 1;
	printf("数组长度为:%d", a);
	return 0}

程序的大致原理就是判断指针str指向的地址里面存储的字符是否为字符串结束标志,如果不是,那么返回值+1,并且程序再次调用一次,此时地址指针指向字符串的下一位字符地址,诸如此循环,最后的返回值即为最终的字符串长度。
不考虑递归,本人觉得这段代码可能用一个循环语句更加方便,创建一个自增变量来存储字符串长度,并且程序可读性也更强一些。
注:这里数组arr作为传递参数,传过去的并不是整个数组,而是首元素的地址;
关于为什么下面这条语句可以实现:

return 1 + self_strlen(str+1);

因为我们定义了函数类型为int,故函数会返回一个整型的值,因此语句可以实现,大致结果为1+1+…+0(最后if判断为假,返回0).
之前做过一个计算n的阶乘的练习,当时的思路是把n和1之间所有的数字都乘起来最后输出,下面采用递归法写程序:

int JC(int pa)
{
	if (pa > 0)
	{
		return pa * JC(pa - 1);
	}
	else
		return 1;

}
int main()
{
	int a = JC(6);
	printf("%d ", a);
	return 0}

我写的是6的阶乘,运行结果为720,正确;这里使用递归法的优势就显现出来了,程序非常简单。
上面两个程序的基本思路是类似的。
二、递归和迭代
递归和迭代均为计算方法
练习:输出n个斐波那契数列
本人给出的代码,利用for循环;

int i = 0;
int j = 0;
int n = 1;
int k = 0;
for (i = 0; i <= 5; i++)
{
	k = n + j;
	n = j;
	j = k;


	printf("%d  ", k);
}

因为斐波那契数列的每一个数均为前两个数的和,故每次运算,将运算结果输出并存起来,将结果的上一位数字也存起来用作下一次运算即可。
下面采用递归法求斐波那契数列,代码如下:

int JC(int pa)
{
	if (pa > 2)
	{
		return JC(pa-1)+JC(pa-2);
	}
	else if(pa<=2)
		return 1;

}
int main()
{
	int i = 0;
	int j = 0;
	scanf("%d", &i);
	j = JC(i);
	printf("%d ", j);
	return 0}

这个程序明显要比本人写的上面的程序要简单很多,并且逻辑也更加清晰;**但是注意:**此段代码,当我们要计算较大位的斐波那契数列时,计算机的反应会很慢,这里同学可以试下求第五十个数,看看计算机要多久出结果;
但是用本人写的简陋代码求数列时,则很快就出结果了(虽然最后结果溢出了,这个暂时不用考虑)
零基础C语言学习

这里分析使用递归法程序执行慢的原因
从程序流程分析,若我们求第五十个斐波那契数,那么首先知道第49和48个数,而要知道第49和48,则分别需要知道第48、47和第47、46,诸如此类的一直循环,计算机很做很多很多重复的步骤,想象一棵大树,每个数都是大树的一个节点,每个节点均有两个分支,故最后的运算量是非常庞大的。这里使用一个测试,来看看机器运行重复的次数。
代码如下,首先定义一个全局变量,用来记录计算机重复计算第三个斐波那契数的次数;

int b = 0;
int JC(int pa)
{
	if (pa == 3)
	{
		b++;
	}
	if (pa > 2)
	{
		return JC(pa-1)+JC(pa-2);
	}
	else if(pa<=2)
		return 1;
}
int main()
{
	int i = 0;
	int j = 0;
	scanf("%d", &i);
	j = JC(i);
	printf("斐波那契数为:%d ", j);
	printf("计算次数:%d ", b);
	return 0}

运行结果如下:
零基础C语言学习
通过重复运算次数,可见计算机工作量的巨大无比!所以当考虑要执行较多次数递归运算是,建议使用循环代替。


程序员灯塔
转载请注明原文链接:零基础C语言学习
喜欢 (0)