零基础C语言学习

                  *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；
}

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

这里分析使用递归法程序执行慢的原因
从程序流程分析，若我们求第五十个斐波那契数，那么首先知道第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；
}

运行结果如下：

通过重复运算次数，可见计算机工作量的巨大无比!所以当考虑要执行较多次数递归运算是，建议使用循环代替。